Parallel decoding of intra-encoded video

A video stream (for example, H.264 video) includes intra-encoded portions. Decoding an intra-encoded portion utilizes the result of decoding one or more other portions (called predecessors) in the frame. Frame reconstruction involves identifying a portion that has no predecessor portions that have not been decoded and then initiating decoding of the identified portion(s). When the decoding of a portion is substantially complete, then the remaining portions to be decoded are examined to identify portions that have no predecessors that have not been decoded. By carrying out this method, multiple portions may be decoded simultaneously. Each can be decoded on a different work entity, thereby increasing the rate of decoding of the overall frame. Because deblock filtering a predecessor destroys information needed in the intra-decoding of other portions, prefiltered predecessor information is stored in a buffer for subsequent use during intra-decoding, thereby facilitating simultaneous decoding of multiple portions.

BACKGROUND

The disclosed embodiments relate to video decoding.

2. Background Information

Cellular telephones provide their users more functionality than just an ability to make and receive wireless telephone calls. Cellular telephone manufacturers are incorporating more and more functionality into their cellular telephones in order to compete for user interest with other cellular telephone manufacturers. A cellular telephone manufacturer may, for example, build a video receiving capability into their cellular telephones. The cellular telephone is to be usable to receive a stream of compressed video information transmitted from a satellite, to decode the compressed information into video, and to display the video on the display of the cellular telephone. The cellular telephone user may therefore watch satellite television programming on the display of the cellular telephone. The manufacturer, however, also wants the cellular telephone to be inexpensive to manufacture. In one example, an older semiconductor processing technology is to be used to realize digital processing circuitry of the cellular telephone in order to reduce the cost of the integrated circuits making up the cellular telephone. Using the older processing technology is less expensive than using a higher speed, newer processing technology.

In one example, the older processing technology limits the clock speed of a digital signal processor that can be realized to about one hundred megahertz. It is desired to be able to use this older technology to video decode thirty frames per second of VGA (640×480 pixels) compressed video information, and to display the resulting VGA resolution video in real time on the display of the cellular telephone. Unfortunately, a one hundred megahertz digital signal processor does not have adequate throughput to carry out the required amount of processing. A digital signal processor having a clock frequency of 250 to 300 megahertz would be required to decode the VGA video stream at thirty frames per second. Accordingly, if the inexpensive semiconductor processing technology is used, then it may only be possible for the cellular telephone to display one third the desired resolution images at the desired thirty frames per second frame rate.

There also may be reasons other than cost for limiting the frequency of clock signal that clocks the digital signal processing circuitry within a cellular telephone.

SUMMARY INFORMATION

A solution is desired that allows the limited clock rate to be used without limiting the resolution of the video that can be decoded and viewed on the cellular telephone.

An amount of encoded video (for example, H.264 video or MPEG4 video) includes a sequence of encoded portions. Each encoded portion contains information on how to reconstruct a corresponding macroblock of pixels in a frame of the video. Some portions are intra-encoded. The decoding of an intra-encoded portion utilizes the result of the decoding one or more other portions. The other portions may be called “predecessors.” Reconstruction of the overall frame of video involves identifying a portion that has no predecessor portions that have not been decoded. A table called a “predecessor table” may be used in this identification. The decoding of each such identified portion is then initiated. When the decoding of a portion is substantially complete (reconstructed at least up to the point of deblocking), then the remaining portions to be decoded are examined to identify portions that have no predecessors that have not been decoded. Again, the decoding of each such identified portion is then initiated. This process of identifying portions that have no undecoded predecessors and then initiating decoding of those identified portions is repeated until all portions of the frame have been decoded.

By carrying out this method, the decoding of portions is initiated such that multiple portions are decoded simultaneously. Each such portion can be decoded on a different work entity, thereby increasing the rate of decoding of the overall frame as compared to a decoding method where only one portion can be decoded at a time. Because deblock filtering of a reconstructed predecessor macroblock can destroy information (reconstructed but prefiltered information) needed in the intra-decoding of other dependent portions, prefiltered predecessor information is stored in a buffer for subsequent use during intra-decoding of dependent portions, thereby facilitating the simultaneous decoding of multiple portions.

In one embodiment, the amount of encoded video is received as a Network Abstraction Layer (NAL) unit bitstream onto a cellular telephone. A set of parallel digital signal processors in the baseband processor integrated circuit within the cellular telephone decodes the bitstream in real time. The baseband processor integrated circuit therefore includes a video CODEC (enCOder/DECoder) functionality. After the method identifies portions that can be decoded simultaneously, the identified portions are decoded in parallel by the various parallel digital signal processors. By distributing the workload over multiple digital signal processors, higher resolution frames of video can be rendered at an adequately high frame rate without having to increase the maximum processor clock rate of the digital signal processors within the baseband processor integrated circuit. The resulting high resolution frames of video are output from the baseband processor integrated circuit and are rendered on the display of the cellular telephone for viewing. In one example, an H.264 video stream of color VGA frames (640×480 pixels) is received onto a cellular telephone and is decoded in real time at a frame rate of thirty frames per second using a set of parallel digital signal processors, where each of the digital signal processors has a maximum clock rate of one hundred megahertz.

Additional methods and structures are described in the detailed description below. This summary does not purport to define the invention. The invention is defined by the claims.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a mobile communication device1. Mobile communication device1in this example is a cellular telephone that includes a Radio Frequency Integrated Circuit (RFIC)2, a baseband processor integrated circuit (BPIC)3, and a display4. RFIC2includes an analog circuit for receiving RF cellular telephone signals from an antenna5, processing and converting the signals into digital form, and communicating the resulting digital information to BPIC3. RFIC2also includes circuitry for receiving digital information from BPIC3, for processing and converting the digital information into analog form, and for transmitting the information as RF signals from antenna5. In addition to supporting cellular telephone communication, BPIC3also serves as a hardware platform for running various application layer programs. One such application in the present example is a video decoding application. BPIC3includes a video CODEC (enCOder/DECoder) functionality. A stream of video information in H.264 format is transmitted from a satellite. The video RF signal is received by RFIC2and is communicated in the form of a bitstream6of H.264 Network Abstraction Layer (NAL) units to BPIC3. Bitstream6is sectioned up and communicated to BPIC3in accordance with a protocol. An ARM processor portion7of the BPIC3reassembles the bitstream6in accordance with the protocol and places bitstream6in the form of NAL units9into a memory8.

FIG. 2is a simplified diagram of the bitstream6of video information. In the simplified example illustrated here, bitstream6includes a sequence of twenty macroblock information portions. These macroblock information portions are labeled0through19inFIG. 2. Each portion includes three subportions, referred to here as “encoded macroblock information portions” (EMIPs). Consider, for example, macroblock information portion MB0in the bitstream7. This portion MB0includes a first EMIP10that indicates how to reconstruct Y luminance information for macroblock MB0, a second EMIP11that indicates how to reconstruct Cr chroma information for the macroblock MB0, and a third EMIP12that indicates how to reconstruct Cb choma information for the macroblock MB0. A macroblock in this specific example is a sixteen by sixteen block of pixel information.

A frame of pixel information, where each pixel includes luminance and chrominance information, can be organized into three frames (also called fields), one for Y luminance, one for Cr chrominance, and one for Cb chrominance. When the frame is to be rendered on display4, the corresponding luminance and chrominance values from the three frames are combined, and converted in the Red-Green-Blue (RGB) color space. The YCrCb to RGB conversion is performed by a Mobile Display Processor (MDP) portion13of the BPIC3. The RGB pixel information is supplied to display4for rendering.

FIG. 3illustrates the luminance frame. EMIP10of portion MB0ofFIG. 2contains information for how to reconstruct the luminance information for macroblock MB0in the frame ofFIG. 3; the EMIP for luminance information in portion MB1ofFIG. 2contains information for how to reconstruct the luminance information for macroblock MB1ofFIG. 3; and so forth.

FIG. 4is a simplified diagram that illustrates how the frame ofFIG. 3can be reconstructed in accordance with the H.264 standard. Simplified terminology is employed to facilitate explanation of the process depicted inFIG. 4. For additional detail on how to process a NAL unit bitstream and how to reconstruct a frame of video information, see the H.264 standard (for example, see: ITU-T Video Coding Experts Group (VCEG), Recommendation H.264/ISO/IEC 14496-10, “Advanced Video Coding,” 2003). The description below corresponding toFIG. 4is simplified for illustrative purposes in that it represents a single-threaded implementation of an H.264/AVC compliant decoder.

ARM processor portion7retrieves the NAL units9from memory8. The NAL units9include headers and other information. What each NAL header means is specified by the H.264 standard. The NAL headers are deciphered as indicated by block14, and entropy unpacking is performed on the remaining information as indicated by block15. The remaining information includes symbols. Each symbol is looked up in a table to identify a corresponding string of bits. The resulting strings of bits that correspond to the symbols are concatenated to form a stream of quantized coefficients (X). The processing of blocks14and15are both performed by ARM processor7, and the resulting stream of quantized coefficients and deciphered header information is written back into memory8. ARM processor7may be clocked at approximately one gigahertz in this example.

It is recognized that the NAL header deciphering of block14may be referred to in the art as “NAL header decoding” and that the entropy unpacking of block15may be referred to in the art as “entropy decoding.” The processing of blocks14and15is not, however, referred to here as decoding. Rather, the term “decoding” is used here to describe other processing including inverse transforming, inter-decoding, intra-decoding (see dashed line42inFIG. 4).

A digital signal processor (DSP) portion16of the baseband processor integrated circuit3retrieves the quantized coefficients (X) and rescales the coefficients in accordance with the H.264 standard. This resealing reverses a scaling that was performed during H.264 encoding of the frame. This resealing is illustrated by block17ofFIG. 4. (Both DSP portion16and ARM processor portion7can read from and write to memory8. Memory8is a processor-readable medium. Both ARM processor portion7and DSP portion16execute separate sets of instructions that are stored in other processor-readable media (not shown) that are parts of ARM processor portion7and DSP portion16, respectively.)

DSP portion16then inverse transforms the rescaled coefficients as specified in the H.264 standard. This inverse transform reverses a transform performed during H.264 encoding of the frame. Application of the inverse transform is illustrated by block18ofFIG. 4. The result is pixels of difference information (D). The difference pixel values are ordered such that difference pixel values for a first macroblock are output, and then difference pixel values for a second macroblock are output, and so forth in macroblock scan line order.

The macroblock of difference pixel information (D) could have been either inter-encoded or intra-encoded. “Inter-encoded” in the example ofFIG. 4means the macroblock is encoded based at least in part on pixel information from another block in another frame (not the frame currently being reconstructed). For example, the difference pixel information (D) may have been inter-encoded by subtracting a macroblock being encoded from the corresponding macroblock in the prior frame (the frame in the video information that precedes the frame being reconstructed). This difference pixel information was then transformed, quantized, scaled, packed, and entropy packed to form an inter-encoded EMIP.

“Intra-encoded” means that the macroblock is encoded based at least in part on pixel information from another block in the current frame. For example, the difference pixel information (D) may have been intra-encoded by subtracting pixel information of a macroblock being encoded from pixel information along an edge of a neighboring macroblock in the same frame. This difference pixel information was then transformed, quantized, scaled, packed and entropy packed to form an intra-encoded EMIP. For additional detail, see the H.264 standard.

For example, if the current EMIP being decoded was an inter-encoded EMIP, then block19causes appropriate pixels from a prior frame to be supplied (symbolized inFIG. 4by switch symbol20) to a summer (symbolized inFIG. 4by summing node symbol21). The supplied pixels from a macroblock are called the prediction macroblock (P). The difference macroblock (D) pixel values are added to the macroblock P pixel values to generate a reconstructed (but unfiltered) macroblock (UF) of pixel values. On the other hand, if the current EMIP being decoded was an intra-encoded EMIP, then blocks22and23cause a portion of a previously decoded macroblock of the current frame to be supplied (symbolized inFIG. 4by switch symbol20) to the summer21. The portion of the supplied macroblock is called the prediction macroblock (P). Each pixel value of difference macroblock D is added to a pixel value from macroblock P to generate a pixel value of a reconstructed (but unfiltered) macroblock (UF). In this intra-decoding, note that the portion of the prediction macroblock (P) is not a portion of a filtered macroblock taken from the output of a deblocking filter block25, but rather is a portion of a prefiltered macroblock taken from the output of summer21. There are multiple ways that the portion of the prediction macroblock (P) is used to generate a reconstructed macroblock from an intra-encoded EMIP. For details on these multiple ways, see the H.264 standard.

Whether the current EMIP being decoded was inter-encoded or intra-encoded is determined by header information in the bitstream. Block24ofFIG. 4uses this header information to control whether inter or intra-decoding is employed. Block24is therefore illustrated as controlling the position of switch symbol20.

A frame of such reconstructed macroblocks may exhibit blockiness and discontinuities between the various macroblocks of the frame. In accordance with H.264, the boundaries between neighboring reconstructed macroblocks are filtered to help reduce the blockiness. This filtering is sometimes called “deblocking filtering” and is represented inFIG. 4by block25. Deblocking filter25outputs the reconstructed and filtered current macroblock (F)26. Macroblock (F)26is stored in memory8along with other similarly reconstructed macroblocks in the same frame such that an entire frame27of reconstructed macroblocks is generated. Reconstructed frame27is stored in memory8inFIG. 1. As explained above, mobile display processor13retrieves the frame27, converts it into RGB format, and supplies the frame of RGB pixels to display4for rendering. When the decoding of NAL units further into the bitstream6corresponding to a next frame begins, the just completed reconstructed and filtered frame27is made available for use in decoding an inter-encoded EMIP. The storage of such prior reconstructed and filtered frames is illustrated inFIG. 4by block19. In the presently described embodiment, the H.264 bitstream is decoded at a rate of thirty VGA (640×480 pixels) frames per second using a BPIC3. BPIC3has one ARM processor7(one gigahertz maximum clock rate) and a DSP16involving six parallel DSP processors (each DSP processor has a maximum clock rate of 100 MHz).

FIG. 5is a flowchart diagram that illustrates a novel method that allows the one hundred megahertz DSP processors to decode a H.264 bitstream of NAL units into VGA frames at the thirty frames per second rate. The method ofFIG. 5involves what may be called a “predecessor table.” How the predecessor table is derived is explained below. After the explanation of the predecessor table, then the steps in the method ofFIG. 5are explained.

FIG. 6illustrates a set of five macroblocks A, B, C, D and X. Macroblock X is the current macroblock to be decoded. Due to the use of intra-encoding and deblocking in H.264, the decoding of macroblock X may require the result of decoding macroblocks C and D. The decoding of macroblock X cannot therefore be performed until macroblocks C and D have been substantially decoded (rescaled, inverse transformed, and reconstructed at least up to the point of deblocking). This is so because if macroblock X is intra-encoded, then its decoding would require that block22inFIG. 4contain reconstructed (but not filtered) macroblocks C and D. Accordingly, macroblocks C and D are said to be “predecessor” macroblocks for macroblock X. This relationship, which depends on the details of the type of intra-encoding and deblocking employed, is used to generate the predecessor table.

FIG. 7is a diagram of a frame of macroblocks. The number in the upper right corner of each macroblock is the macroblock number. The number in the center of each macroblock is a predecessor count value for the macroblock. Initially, all predecessor count values in the table are unknown and therefore are represented inFIG. 7as “X's.”

In a first step, the macroblock structure ofFIG. 6is placed with respect to the frame ofFIG. 7so that macroblock X of the macroblock structure ofFIG. 6is disposed over macroblock MB0ofFIG. 7. This is illustrated in the left portion ofFIG. 8. The darkened macroblocks represent the macroblocks of the macroblock structure ofFIG. 6. Because macroblocks C and D are outside the boundaries of the frame as indicated byFIG. 8, macroblock X can be decoded without waiting for the decoding of any other macroblock. Macroblock MB0is therefore said to have no predecessors. As illustrated in the right portion ofFIG. 8, a zero (representing that MB0has no predecessors) is the predecessor count value for MB0.

Next, the macroblock structure ofFIG. 6is shifted to the right so that macroblock X of the macroblock structure ofFIG. 6is disposed over macroblock MB1. This is illustrated in the left portion ofFIG. 9. Macroblock C is still outside the boundaries of the frame, but macroblock D is now over MB0. Accordingly, macroblock MB0must be decoded before macroblock MB1can be decoded. MB1is therefore said to have one predecessor macroblock (MB0). A one (representing that MB1has one predecessor) is the predecessor count value for MB1as illustrated in the right portion ofFIG. 9.

Next, the macroblock structure ofFIG. 6is shifted to the right so that macroblock X of the macroblock structure ofFIG. 6is disposed over macroblock MB2. This is illustrated in the left portion ofFIG. 10. Macroblock C is still outside the boundaries of the frame, but macroblock D is now over MB1. Accordingly, macroblock MB1must be decoded before macroblock MB2can be decoded. MB2is therefore said to have one predecessor macroblock (MB1). A one (representing that MB2has one predecessor) is the predecessor count value for MB2as illustrated in the right portion ofFIG. 10.

This process of shifting the macroblock structure ofFIG. 6across the macroblocks of the frame ofFIG. 7is repeated in scan line order, left to right, row by row down the various rows of the frame until each predecessor count value in the predecessor table is filled in.

FIG. 11illustrates the resulting predecessor table. This table is used in the method ofFIG. 5. Initially, in the method ofFIG. 5, video information is received (step100inFIG. 5). The video information includes a plurality of EMIPs for a frame. Some EMIPs are inter-encoded, and other EMIPs are intra-encoded. The video information may, for example, be bitstream6ofFIG. 1.

Next (step101), one or more EMIPs are identified that have no predecessor EMIPs that have not been decoded. In one example, a control entity process executing on DSP16retrieves the predecessor table ofFIG. 11from memory8. The zero predecessor count value for MB0indicates that the EMIP for MB0is an EMIP that has no predecessor EMIPs that have not yet been decoded.

Next (step102), decoding of the EMIPs identified in step101is initiated. The decoding of each of these EMIPs is carried out by a different working entity. In one example, DSP16includes six parallel DSP processors. Each DSP processor is clocked at a one hundred megahertz rate. A pipelined architecture is employed with interleaved one hundred megahertz clock signals clocking each respective DSP processor. From the perspective of software executing on DSP16, there appear to be six separate DSP processors available for the execution of code. Each DSP processor executes a separate thread of instructions and is considered to be a different work entity. All threads receive work to do from a separate queue.

In the presently described example, only one EMIP was identified in step101and this is the EMIP for MB0. This EMIP for MB0is placed on the shared queue. The first thread (denoted T1inFIG. 1) picks it up for decoding on the first virtual DSP processor and decodes the EMIP for MB0in accordance with the methodology ofFIG. 4.

FIG. 12illustrates this stage in processing. This state persists as long as the decoding of no EMIP is substantially complete (substantially complete means decoding is complete to the point of obtaining the reconstructed but unfiltered macroblock (UF)). When it is determined that the decoding of an EMIP has been substantially completed (step103), then process flow returns to step101. In the diagrams ofFIGS. 12-23, a macroblock whose EMIP has been substantially decoded is represented as a block filled with cross-hatching. From step103, decoding also continues such that the reconstructed macroblock (UF) is deblock filtered to generate a reconstructed and filtered macroblock. The resulting reconstructed and filtered macroblock is output (step104) and is accumulated to begin the formation of a reconstructed and filtered frame.

In the presently described example, once the decoding of macroblock MB0is substantially complete, the identification of one or more EMIPs that have no predecessor EMIPs (step101) is performed using the predecessor table ofFIG. 12. In the predecessor table, the predecessor count values of all macroblocks for which MB0is a predecessor are decremented by one. They are decremented by one because one of their predecessors (MB0) has now been adequately decoded. In the presently described example, MB0is a predecessor for MB1. As indicated byFIG. 13, the predecessor count value of MB1is decremented from one to zero. Any macroblock for which its predecessor count value is zero does not have any predecessors. Accordingly, MB1is identified in step101as being an EMIP that has no predecessor EMIPs that have not been decoded.

Next (step102), the decoding of the EMIP for MB1is initiated. In the present example, the EMIP for MB1is placed onto the shared queue. Because thread T1is now idle, thread T1can retrieve the EMIP for MB1from the queue and start decoding it. When the decoding for the EMIP for MB1has been substantially completed (step103), then processing returns to step101. Decoding also continues such that the reconstructed macroblock (UF) for MB1is deblock filtered to generate a reconstructed and filtered macroblock for MB1.

When the decoding for the EMIP for MB1causes processing to return to step101, the predecessor count values of all macroblocks for which MB1is a predecessor are decremented. As illustrated inFIG. 14, this results in the predecessor count values of macroblocks MB2and MB5being decremented. Note that the macroblock dependency structure ofFIG. 6indicates that MB1is a predecessor for both MB2and for MB5. The decrementing results in the predecessor count values for macroblocks MB2and MB5changing from ones to zeros. The EMIPs for MB2and MB5are therefore identified in step101as being EMIPs that have no predecessor EMIPs that have not been decoded.

In the presently described example, EMIPs for MB2and MB5are pushed onto the shared work queue as the last step of processing for the prior MBs. DSP thread T1pops the EMP for MB2from the queue, and thread T2pops the EMIP for MB5from the queue. This is the state of processing illustrated inFIG. 15. At this point, not just one, but two EMIPs are being simultaneously decoded using multiple different work entities (in this case, two threads).

When one of these EMIPs is substantially decoded, then processing proceeds from decision step103back to step101. In the presently described simplified example, the decoding of all EMIPs takes the same amount of time. The EMIP for MB2and the EMIP for MB5therefore are both determined to be substantially decoded in step103at the same time. Substantially decoded MB2is a predecessor for both MB3and for MB6. Accordingly, step101involves decrementing the predecessor count values for MB3and MB6. Also, substantially decoded MB5is a predecessor for MB6. Accordingly, step101involves decrementing the predecessor count value for MB3once and involves decrementing the predecessor count value for MB6twice. As illustrated inFIG. 16, the predecessor count values for MB3and MB6are reduced to zeros. Due to their predecessor count values being zeros, the EMIPs for MB3and MB6are identified (step101) as being EMPS that have no predecessor EMIPs that have not been decoded. Decoding of the identified EMIPs (step102) is initiated. As illustrated inFIG. 16, EMIPs for MB3and MB6are pushed onto the shared queue. Thread T1pops the EMIP for MB3from the queue and thread T2pops the EMIP for MB6from the queue. The EMIPs for MB3and MB6are thereafter decoded simultaneously by different work entities (in this case, different threads).

Processing proceeds in this manner across the macroblocks of the frame. Processing of the EMIPs in the presently described example is set forth by the sequence of diagrams ofFIGS. 16-23. Note that the method carried out by the control entity (a process executing on DSP16) causes three EMIPs to be processed at the same time at different points (seeFIGS. 16 and 18) in the overall process. The three work entities (three threads of instructions T1, T2and T3) that perform this parallel processing are illustrated inFIG. 1as blocks within DSP16.

BUFFER FOR PREFILTERED VALUES: The decoding of a group of EMIPs at the same time is possible because the information required to decode each EMIP in the group is not dependent on the results of decoding others of the EMIPs in the group that are to be simultaneously decoded. As indicated inFIG. 6, the decoding of an intra-encoded EMIP for macroblock X requires that the EMIP for macroblocks C and D be decoded first. More particularly, the intra-decoding of macroblock X may require the decoding results from a strip of values along the bottom edge of macroblock B and may require the decoding results from a strip of values along the right edge of macroblock D and may require the decoding results for a small block of values in the lower right corner of macroblock A.FIG. 24illustrates this strip of values that might be required in the intra-decoding of macroblock X. In the example of H.264, this strip is one value wide and extends upward along the right edge of macroblock D, through the bottom right corner (one value) of macroblock A, and left to right across the bottom edge of macroblock B, and extends about one quarter of the way into macroblock C.

In carrying out the decoding of MB7in the decoding flow ofFIGS. 12-23set forth above, if the EMIP for MB7were reconstructed to generate the prefiltered macroblock values (UF), and then those prefiltered macroblock values (UF) were deblock filtered before moving on to decode the next EMIP, and if the prefiltered macroblock values (UF) were not stored, then when the EMIP for macroblock MB8was to be decoded (seeFIG. 17), the prefiltered macroblock values (UF) for the right edge of MB7would not be available for intra-decoding of the EMIP for MB8. Similarly, when the EMIP for macroblock MB12was to be decoded (seeFIG. 18), the prefiltered macroblock values (UF) for the bottom edge of MB7would not be available for intra-decoding of the EMIP for MB12. To provide access to these prefiltered values for the subsequent decoding of EMIPs for other macroblocks, the bottom edge strip of prefiltered values of the EMIP being decoded is stored into a buffer prior to deblocking filtering. Similarly, to provide access to these prefiltered values for the subsequent decoding of EMIPs for other macroblocks, the right edge strip of prefiltered values of the EMIP being decoded is stored into the buffer.

FIG. 25illustrates a buffer28that is used to store prefiltered reconstructed values for use in decoding subsequent EMIPs in the same frame. Buffer28includes several vertically extending column sections29-32and several horizontally extending row sections33-37. Arrow38illustrates that when the decoding of the EMIP for macroblock MB7is substantially complete, the strip of prefiltered values along its bottom edge is stored in a corresponding portion35of buffer28. Portion35is the portion of buffer28that corresponds to the column of macroblocks that contains macroblock MB7. These values remain in buffer28until the EMIP for macroblock MB12is to be decoded. When the EMIP for macroblock MB12is decoded, the values in portion35of buffer28may be used in intra-decoding. The precedence order of the macroblocks of the frame ensures that no EMIP for a macroblock in the column will be decoded before the EMIP for macroblock MB12. Accordingly, when an EMIP for a macroblock in a column is substantially complete, its bottom strip of prefiltered values is written into the portion of buffer28corresponding to that column. These stored prefiltered values are then available for use in the decoding of the macroblock EMIP immediately below in the column.

FIG. 26illustrates that when the decoding of the EMIP for macroblock MB7is substantially complete, the strip of prefiltered values along its right edge is stored in a corresponding portion30of buffer28. Portion30is the portion of buffer28that corresponds to the row of macroblocks that contains macroblock MB7. These values remain in buffer28until the EMIP for macroblock MB8is to be decoded. When the EMIP for macroblock MB8is decoded, the values in portion30of buffer28may be used in intra-decoding. The precedence order of the macroblocks ensures that no EMIP for a macroblock in the row will be decoded before the EMIP for macroblock MB8. Accordingly, when an EMIP for a macroblock in a row is substantially complete, its right edge strip of prefiltered values is written into the portion of buffer28corresponding to that row. These stored prefiltered values are then available for use in the decoding of the macroblock EMIP immediately to the right in the row.

Note fromFIG. 24that a reconstructed but unfiltered value from macroblock A (lower right corner of macroblock A) may be required to intra-decode an EMIP for macroblock X. Each of the portions30-32therefore contains an additional value at the top of the portion. In the example ofFIG. 26, when the decoding of macroblock MB7is substantially complete, the right edge strip of prefiltered values in MB7is written into the lower portion of30in buffer28and the prefiltered value from the right corner of portion35is written to the top of portion30. The right corner of portion35is the result of prior processing of MB2. Then the bottom horizontal edge strip of MB7is written to the portion35in buffer28as illustrated inFIG. 25. The intra-decoding of the EMIP for macroblock MB8may then use the values in the top of column portion30, as well as the other values in the bottom of column portion30, as well as the values in the row portion36. Portions29-32may be called “column” portions of buffer28since portions29-32form a column (even though each portion29-32corresponds to a row of macroblocks). Portions33-37may be called “row” portions of buffer28since portions33-37form a row (even though each portion33-37corresponds to a column of macroblocks). In one advantageous aspect, buffer28is disposed in memory within DSP16rather than in memory8in order to reduce the number of memory accesses across bus41that are required in order for DSP16to perform intra-decoding operations. AlthoughFIG. 25is illustrated and described beforeFIG. 26in the text above, the column buffer update operations illustrated by lines39and40inFIG. 26are performed prior to the operation described by line38inFIG. 25.

ENCODING ALGORITHMS OTHER THAN H.264: The method set forth above for decoding multiple EMIPs simultaneously applies to decoding EMIPs that are encoded using encoding algorithms other than H.264. The description of the decoding of H.264 EMIPs above is provided as an example. To apply the method to decode EMIPs that are encoded using another encoding algorithm, the predecessors for a block to be decoded in accordance with the encoding algorithm are determined. In one example, the relationship of these predecessors to the block to be decoded is then applied to generate a precedence table. The precedence table is then used in the decoding of the EMIPs to determine when all the predecessors for a given EMIP have been adequately decoded. When all predecessors for a given EMIP have been determined to have been adequately decoded, then the decoding of the given EMIP is initiated. The decoding of EMIPs can be initiated on different work entities such that multiple EMIPs are decoded simultaneously.

FIG. 27illustrates a predecessor macroblock relationship for an MPEG4 encoding algorithm. In the set of four macroblocks A, B, C and X illustrated inFIG. 27, macroblock X is the current macroblock to be decoded. Macroblocks B and D are predecessors for macroblock X. In the same way that the predecessor relationship ofFIG. 6is employed to generate the predecessor table ofFIG. 11for H.264, the relationship of predecessors illustrated inFIG. 27is employed to generate a predecessor table for MPEG4. A buffer like buffer28inFIGS. 25 and 26is employed to store prefiltered and reconstructed values generated in the MPEG4 decoding of one EMIP. The stored prefiltered and reconstructed values may be used later in the intra-decoding of another EMIP in the frame. In this manner, the method set forth in this patent document for decoding multiple EMIPs simultaneously can be utilized to decode video information that was encoded using encoding algorithms other H.264 and MPEG4.

Although certain specific embodiments are described above for instructional purposes, the present invention is not limited thereto. Encoded video information need not be received onto a decoding device in the form of a stream of information, but rather may be received onto the decoding device by reading the encoded video information out of memory. The encoded video in the memory may, for example, be stored and retrieved as a file. The work entities that are capable of decoding EMIPs may be software threads such that the overall method ofFIG. 5is realized in software. Alternatively, the work entities may be different dedicated hardware processing units. Software can be used to push the decoding of EMIPs onto a queue or queues for these dedicated hardware processing units. Alternatively, dedicated hardware can be used to push the decoding of EMIPs onto a queue or queues for the hardware processing units. The decoding method need not be embodied on a mobile communication device, but rather may be embodied on another device. In one embodiment, the decoding method is performed by a video reader (for example, Windows Media Player) application that executes on a personal computer. The decoding method can be performed by video decoding hardware and/or software embodied in televisions, video disc players, and other video decoding and viewing devices. Accordingly, various modifications, adaptations, and combinations of the various features of the described specific embodiments can be practiced without departing from the scope of the invention as set forth in the claims.