Decoding bit streams encoded according to variable length codes

A decoding approaching suitable for architectures such as Very Long Instruction Word (VLIW), in which throughput performance would be reduced in case if large blocks of conditional core are executed repetitively. Some of the code-words are received according to escape modes, which require different kinds of processing depending on specific mode. The decoding logic is partitioned into two parts, with the first part accessing entries in tables corresponding to code-words. The first part writes the symbol value retrieved from the accessed entry into an output buffer. In case of escape modes, the first part writes an intermediate decoded value to the output buffer, and an escape mode identifier retrieved from an accessed entry, and a position identifier in the output buffer for the symbol sought to be decoded in an intermediate buffer. The second part then performs the specific processing required for each entry in the intermediate buffer. The block sizes executed on conditions are reduced, thereby facilitating higher degree of parallelism and thus higher throughput performance.

RELATED APPLICATIONS

The present application is related to the U.S. Provisional Patent Application Ser. No. 60/595,707, entitled, “Decoding Bit Streams Encoded According to Variable Length Codes”, filed on Jul. 29, 2005, naming as inventors: Sadanand Shirdhonkar and Venkata Ratna Mullangi, and is incorporated in its entirety herewith.

BACKGROUND

1. Field of the Invention

The present invention relates generally to compression technologies, and more specifically to a method and apparatus for decoding variable length codes (e.g., Huffman Encoding) while using optimal resources.

2. Related Art

Symbols are often encoded using variable length codes. Huffman encoding provides an example approach to such encoding. Variable length encoding has been used in several environments, typically due to the loss-less nature and the level of compression achieved.

In a typical scenario, an encoder encodes each input symbol to a corresponding bit string (code-word) using a pre-specified table, with the length of code-word potentially being different for different input symbols. In general, short length code-words are chosen for frequently occurring input symbols. A decoder then receives a bit stream containing such variable length code-words and constructs the symbols by using the inverse encoding tables (or corresponding information).

The decoding technique may need to be implemented while meeting various constraints in the corresponding environments. For example, in devices using VLIW (very large instruction word) processors, it may be desirable to avoid if conditions in the decoding operation. In addition, it may be desirable that the input characters be constructed quickly (using minimal processing power).

DETAILED DESCRIPTION

A decoding approach provided according to an aspect of the present invention generates a first symbol from a first code-word after generating a second symbol from a second code-word, even though the first code-word is located before the second code-word in a stream of symbols encoded according to an approach for compression.

In an embodiment, the approach allows variable length code-words, with some symbols being encoded according to escape modes. Various aspects of the present invention enable the symbols to be decoded while minimizing conditional processing (e.g., if conditions). Such a feature is particularly suited for Very Long Instruction Word (VLIW) type architecture based systems, which can more effectively exploit parallelism in the absence of conditional processing.

The conditional processing is minimized by splitting the decoding task into two distinct parts. The first part accesses a lookup table to identify symbol value in case of non-escape (or table) mode, and an intermediate value which requires appropriate further processing in case of escape modes. The data identifying the specific position (e.g., in the form of an index) in the sequence of symbols (sought to be generated by decoding) for each intermediate value, is written into an intermediate buffer (by the first part).

The second portion performs the necessary corrections to intermediate values according to respective escape modes to generate corresponding symbols, and writes the generated symbols into the corresponding specific locations in the sequence of symbols. As a result, after operation of the second portion, all the decoded symbols may be available, as desired. In an embodiment, the intermediate values are stored in the same locations of the output buffer, as where the corresponding final symbols are finally stored. As a result no additional memory may be required for storing intermediate values.

Due to such an approach, the first part can process several code-words (e.g., in a block or a macro-block) with a high throughput performance (e.g., one code-word decoded every pipeline cycle) in a pipelined architecture. The second part can also provide high pipelined throughput performance since the amount of processing to be performed depending on different escape codes is minimal, and the VLIW architecture may be designed to minimize/avoid reduction in throughput performance in case of such minimal conditional processing.

2. Example Environment

FIGS. 1 and 2together represent an example environment in which various aspects of the present invention can be implemented. Only the details of the components as believed to be relevant to an understanding of the operation of the described embodiments are provided in this application for conciseness. For further details, the reader is referred to documents related to the MPEG-4 Standards, well known in the relevant arts.

Broadly,FIG. 1represents a digital video encoder device which compresses video frames into a format suitable for transmission/storage, andFIG. 2represent a video decoder device reproducing the video frames. Even though shown as part of different devices, the components of the two Figures are often implemented in a single component (codec)/device, capable of both image capture and reproduction.

Continuing with respect toFIG. 1, the block diagram is shown containing image encoder110, motion estimation (ME) unit130, error generation unit140, discrete cosine transform (DCT) unit150, quantization unit (Q)155, zigzag (ZZ) scan unit160, variable length coder (VLC)170, inverse quantization (IQ) unit180, inverse DCT (IDCT) unit190and reference frame buffer195. Each block is described below in further detail.

Image encoder110generates macro blocks (MB) on path113from video signal received on path101. The video signal may be received in the form of a sequence of frames, with each frame containing multiple pixels. Each pixel is represented digitally in YCbCr format (well known in the art), wherein Y represents the luminance and Cb, Cr respectively represent the hue and saturation of a pixel. A video image containing 720*480 pixels can be logically divided into 1350 16*16 macro-blocks.

Each macro block (16×16 pixels) may be represented in formats such as 4:2:0 and 4:2:2 as well known in the relevant art. For example, in case of 4:2:0 format, each macro block contains six blocks (each block is of size 8×8 pixels), with 4 blocks representing Y(luminance), one block representing Cr and one block representing Cb.

Image encoder110is shown containing buffer115and MB generation unit120. Buffer115holds an input frame received on path101for encoding and transmission (typically using various prediction approaches). MB generation unit120receives the input frame on path112and divides the input frame into a number of macro blocks (MB) noted above. Each macro block is provided on path113for further processing.

Motion estimation unit130receives a macro block on path113(input macro block) and a reference frame on path193(from reference frame buffer) and generates a motion vector. The motion vector generated generally represents a distance and direction in which a image portion (represented by macro block) has moved. The generated motion vector is provided on path137.

Error generation unit140generates a residue macro block representing a difference (error) in the input macro block and corresponding reference macro block (obtained from reference frame buffer). The received macro block and reference macro blocks may be received either directly from respective paths113and193or may be received from motion estimation unit130. The residue macro block is provided to DCT150on path145.

Discrete cosine transform (DCT) unit150receives residue macro block from error generation unit140and provides a DCT coefficient block on path156as described in below paragraphs. DCT unit150performs discrete cosine transform (well known in the relevant arts) on the received residue macro blocks. DCT may be performed consistent with the format of macro block received. For example, macro block having format 4:2:0 may be divided into 4 luminance blocks and two chrominance blocks, and DCT may be performed on each block (8*8 pixel) sequentially.

Typically, a two dimensional DCT performed on each block (8*8 pixels) produces a block of DCT coefficients representing contribution of a particular combination of horizontal and vertical spatial frequencies in the original picture block. In an embodiment, DCT performed on an 8×8 block of 8 bit pixels produces DCT block of 8×8 with 11 bit coefficients. The coefficients at the lower frequencies typically contain higher energy (magnitude) and the energy content of other coefficients tend to zero. Quantization unit (Q)155quantizes the two dimensional DCT coefficient blocks and the quantized DCT values are provided on path to zigzag scan unit160.

IDCT190receives the quantized values of DCT coefficient on path156and constructs a corresponding picture block by performing a inverse of discrete cosine transform. The constructed picture blocks are stored as reference frames in a reference frame buffer195. The reference frames are provided to motion estimation unit130on path193for motion prediction.

Zigzag scanner160receives each quantized DCT coefficient block on path156and transforms the DCT coefficient block into one dimensional data suitable for variable length coding. Typically, the sequence of coefficients are picked such that both horizontal and vertical frequency increase in this order, and the variance of the coefficients decrease in the order. In one embodiment, the sequence of data is represented using a sequence run and value pairs (run-value pair) as described in further detail below. A run generally represents a number of zeroes before a non-zero value. The run-value pairs are provided on path167.

Variable length coder (VLC)170generates a variable length code-word for each run value pair received on path167. Variable length code-word may be generated using technique such as Huffman encoding etc. Generally, VLC170converts a run-value pair into a run-value-last triplet and generates a variable length code-word for each run-value-last triplet (“input symbol” in this embodiment). Here “last” indicates if the run-value pair is the last such pair in a given block.

The generated code-word are transmitted on path199in a desired format. Typically the information representing motion vectors, block formats, block size, etc., are transmitted as metadata along with the code-words. The manner in which a bit stream representing the code-words may be processed to construct the video frames is described below with reference toFIG. 2.

3. Receiving Components

FIG. 2is a block diagram illustrating the manner in which code-words are processed to produce video frames for display. The block diagram is shown containing variable length decoder210, inverse zigzag unit220, inverse quantization unit (IQ)230, inverse DCT (IDCT)240, and image construction unit260.

Inverse zigzag unit220, inverse quantization unit (IQ)230, inverse DCT (IDCT)240, and image construction unit260respectively perform the reverse operation of zigzag (ZZ) scan unit160, quantization unit155, discrete cosine transform (DCT) unit150and a combination of blocks of image encoder110, motion estimation (ME) unit130. The components are described only briefly further, for conciseness.

Inverse zigzag unit220generates a quantized DCT coefficients block from a run-value-last triplet received from Huffman decoder210. The size of the block is generally obtained from the metadata transmitted along with code-word as noted above. Inverse quantization unit (IQ)230performs inverse quantization and generates a DCT coefficients block. The generated DCT coefficient blocks are then provided to IDCT240on path234.

Inverse DCT (IDCT) unit240performs inverse discrete cosine transform on the received set of coefficients(block) and generates pixel values in Y(luminance), Cr and Cb (color information) format. The generated pixels are generally provided as an image table. Image construction unit260receives the image information from the image table and metadata, to generate each frame of image for display.

Variable length decoder210decodes a sequence of code-words (contained in the sequence of bits received from the digital video encoder ofFIG. 1) and generates the corresponding triplets (run-value-last triplet/symbols) corresponding to the code-words. Variable length decoder210may extract various metadata information and present the metadata information as a table. The triplets are provided to inverse zigzag unit220.

In general, the decoding operation needs to be consistent with the encoding operation. Accordingly an example encoding approach is described first below.

4. Example Encoding Approach

In the example approaches described herein, a four mode VLC (variable length coding) is employed. The four modes are referred to as the default table mode, level escape mode (escape mode1), run escape mode (escape mode2) and full escape mode (escape mode3). In the table mode, a (VLC) table exists (such as Huffman table for Huffman encoding), which maps the most commonly occurring run-level-last triplets to their corresponding variable length code-words.

Generally, Huffman (VLC) table in such an embodiment is characterized by parameters referred to as LMAX and RMAX. LMAX represents the maximum level of a given run listed in the table. RMAX represents the maximum run for the given level represented in the table. Accordingly a recived run-value pair is encoded in default table mode when received level is less than or equal to LMAX and received run value is less than or equal to RMAX ((level<=LMAX) and (run<=RMAX)). In this case, the code-word is obtained by indexing into the code-word table, using the level and run values.

Received run-value pair is encoded in level escape mode when received level value is greater than LMAX and less than twice of LMAX, and received run value is less than RMAX ((LMAX<level<=2*LMAX) and (run<=RMAX)). In such case, a new run-level pair is generated as new run=run and new level=level−LMAX. The new run and new level is encoded according default table mode and corresponding code-word is transmitted with a prefix code representing level escape mode.

Similarly, a run escape mode is used when RMAX<run<=(2*RMAX+1) and (level<=LMAX). The new run-level pair is generated as newrun=run−(RMAX+1) and new level=level. New run and new level is encoded according to default table mode and the corresponding code-word is transmitted with a prefix code representing run escape mode.

In the full escape mode, VLC170encodes the received run-value pair with an escape code followed by the actual run, length and last values. The full escape mode is used when the received run-level pair does not satisfy any of the above conditions. In the full escape mode, the code-word comprises of a predefined number of bits, that are used to send the run, level and last values without any encoding.

Decoding of the code-word needs to be performed consistent with the encoding operation described above. Various aspects of the present invention decode the code-words while using optimal resources. The advantages of the invention can be appreciated in comparison to some prior approaches. Accordingly, the prior decoding approaches are described briefly below.

5. Example Prior Decoding Approaches

FIG. 3is a flowchart illustrating decoding approach of an example prior embodiment. The flowchart begins in step301and control passes to step310. In step310, VLD210accesses an entry in a table corresponding to a code-word. Various approaches may be used to determine the specific entry to be accessed.

In step320, VLD210obtains an attribute representing escape mode information from the accessed entry. In an embodiment, the attributes information contained in the entry include the “last” bit, sign bit and the escape mode. In step340, VLD210determines whether attribute indicates an escape mode1. Control transfers to step345in case of escape code is 1 and to step355otherwise.

In step345, VLD210accesses the next code-word and generates a corresponding intermediate value. In step350, VLD210corrects the level of the intermediate value to generate the final symbol. Control then transfers to390.

In step355, VLD210determines whether attribute indicates escape mode2. Control transfers to step360in case of escape code is 2 and to step370otherwise. In step360, VLD210decodes the next code-word and generates a corresponding intermediate symbol. In step365, VLD210corrects the run of the intermediate symbol to generate the final (decoded) symbol. Control then transfers to step390.

In step370, VLD210determines whether attribute indicates escape mode3. Control transfers to step375in case of escape code is 3 and to step390otherwise (in which case the symbol is indicated in the access entry, without any escape mode processing). In step375, VLD210forms the symbol from a number of bits of the bit stream. Control then transfers to step390.

In step390, VLD210writes the symbol to an output buffer. In step395, VLD210checks whether decoded triplet indicates that the present codeword is the last code-word in the block. Control transfer to step399in case of last code-word, and to step310to continue processing the next code-word otherwise. The flowchart ends in step399.

From the above, it may be appreciated that the symbols are generated (and written into output buffer) in the same sequence as in which the corresponding code-words are received.

In addition, it may be appreciated that substantial portion of the processing logic is ‘conditional’ (depending on the specific escape mode) processing. Such conditional processing is not conducive to high throughput performance, at least in some architectures, as described below with respect to Very Long Instruction Word (VLIW) architecture.

FIG. 4is a block diagram illustrating the general features of a system implemented according to Very Long Instruction Word (VLIW) architecture. System400is shown containing program memory410, dispatch unit420, processing units431–434and451–454, register files440and460, and data memory480. Only the details of VLIW architecture as believed to be relevant to an understanding of the operation of the described embodiment, are provided in the present application. For further details on VLIW architecture, the reader is referred to a document entitled, “SPRU189—TMS320C6000

CPU and Instruction Set Reference Guide” and “SPRU197—TMS320C6000 Technical Brief”, which are available from Texas Instruments, Inc., the assignee of the subject patent application.

Processing units451–454and register file460may respectively operate similar to processing units431–434and register file440, and the description is not repeated for conciseness. The remaining blocks are described below in further detail.

Program memory410stores instructions, which operate to decode the code-words and generate corresponding symbols. Each processing unit431–434may be designed to perform corresponding set of operations (add, shift, multiply, conditional operation, etc.). Each processing unit is implemented according to a pipeline architecture, and generates one result each processing cycle in the steady state. Data memory480provides any data required during execution of instructions, and also stores the results of execution of instruction, if necessary.

Dispatch unit420retrieves small sets of instructions from program memory410and schedules the instructions for execution on a suitable processing unit. Each set of instructions is dispatched to the corresponding processing unit. Each of such set of instructions is preferably a loop that executes for many iterations, and the sub-sets should be executable in parallel such that parallelism can be exploited to the fullest in the pipeline architecture.

Register file440contains multiple registers used by processing units during execution. Some of the registers (“predicate registers”) are used for conditional execution of single instructions. Generally, an instruction can be specified associated with a predicate register, and the instruction is executed (or completed) only if the predicated register is set to 1, otherwise the instruction is not executed.

Only a small number of such predicate registers (e.g., 6) are available, in one embodiment. The predicate registers may be designed (in hardware) such that the pipeline throughput performance is not impacted substantially. While the execution of instructions based on such predicate registers may not substantially impede the throughput performance, branch instructions may cause the throughput performance to be reduced substantially. Accordingly, it is desirable that the number of instructions processed conditionally be reduced.

Also, it may be appreciated that higher throughput performance may be obtained if consecutive loop iterations are independent of each other, i.e., the current loop iteration should not depend on the computations of the previous iteration. Otherwise, the next iteration cannot start till the current one has finished its computations. This condition can be quantified as the loop-carry dependency (LCD) bound. It is defined as the minimum delay required, from the point of start of the current iteration, to the point where the next iteration can start. The set of instructions contributing to the LCD bound form the critical path.

The approach described inFIG. 3, by its nature is linear with less scope for parallelism, as illustrated below with respect toFIGS. 5A and 5B.

InFIG. 5A, it is assumed that nine instructions501–509together implement the flowchart ofFIG. 3, and in particular that instructions501–503implement steps310–320, instructions504–508implement steps340–375, and instruction509implements step390.

FIG. 5Bdepicts the manner in which the execution of instructions of501–509is repeated 4 times (as shown by iterations530,540,560and570) in time domain (line550) to decode four symbols. As can be readily appreciated, iteration540starts only after completion of execution of instruction506of iteration530.

Thus, the loop carry dependency (representing absence of parallelism) is shown in duration551–553. Of that,551–552is due to data dependency since the decoding of second code-word cannot be started until the length of the first code-word (from iteration530) is determined. Duration552–553is due to the conditional processing of escape code in iteration530).

Similarly, loop carry dependency delays553–554and554–555correspond to iterations540to560, and560to570respectively. The decoding of the four symbols is shown completing at time point556. The manner in which various aspects of the present invention allow such delays to be reduced, is described below in further detail.

8. Enhancing Throughput Performance in Decoding Variable Length Code-Words

According to an aspect of the present invention, the number of instructions processed depending on a condition is reduced by dividing the decoding logic into two separate parts, with the first part merely accessing the relevant entries from a table and writing the intermediate value to an intermediate buffer in case of escape modes.

The second part corrects the intermediate values as needed by the corresponding escape mode to generate the corresponding symbols. The generated symbols are written into an output buffer at appropriate locations specified by the first part. The first part writes the symbols directly into the output buffer in case of non-escape modes. The operation of the first and second parts are respectively described below with respect toFIGS. 6A and 6B.

FIG. 6Ais a flowchart illustrating the manner in which a first part is implemented to enhance throughput performance in decoding variable length code-words. The flowchart is described with respect toFIG. 2merely for illustration. However, the approaches can be implemented in various other environments. The flowchart begins in step601, in which control immediately passes to step605.

In step605, VLD210sets a location index to 0. The location index is used to identify the position in the output buffer, as described below in further detail. In step610, VLD210forms input data containing a code-word (from the sequence of bits received as input). In step615, VLD210accesses an entry corresponding to the input data from a table.

In step620, VLD210determines whether the code-word is related to a symbol encoded according to table mode (i.e., without escape modes). A field in the accessed entry indicates the mode of encoding. Control passes to step625in case of table mode, and to step635otherwise.

In step625, VLD210writes the symbol value contained in the accessed entry into the output buffer at a position identified by the location index. It should be appreciated that in case the code-word in the prior iteration corresponds to an escape mode, the symbol value of the present iteration represents an intermediate value which needs to be further processed according to the escape mode.

In case the code-word in the prior iteration does not correspond to an escape mode, the symbol value of the present iteration represents the symbol corresponding to the present code-word according to the table mode. In step630, VLD210increments the location index, and control then passes to step645.

In step635, VLD210writes the location index and mode identifier into the intermediate buffer in case the present entry indicates that the symbol being presently decoded is according to escape mode. In step640, in case the present code word indicates escape mode3, VLD210writes the next M bits into output buffer and increments the location index, wherein M represents the number of bits representing the symbol.

In step645, VLD210checks whether there are more code-words to be processed. Control passes to step610to process additional code-words, or else to step649, in which the flowchart ends.

Thus, by operation of the flowchart ofFIG. 6A, the decoded symbol values in the accessed entries, whether representing the final symbol or the intermediate values requiring additional processing, are written in the output buffer. The intermediate buffer contains additional information indicating the mode identifier and the values in the output buffer, which require additional processing according to the corresponding mode identifier. The manner in which a second part processes the information in the intermediate buffer to generate the corresponding symbols is described below with respect toFIG. 6B.

FIG. 6Bis a flowchart illustrating the manner in which a second part generates symbols encoded in escape modes from the intermediate buffer noted inFIG. 6A. The flowchart begins in step671, in which control transfers to step675.

In step675, VLD210reads escape mode identifier and location identifier from the intermediate buffer. The location identifier identifies the location in the write buffer where the corresponding intermediate value, which needs to be corrected according to the escape mode identifier, is present.

Additional processing depends on the escape mode identifier as represented by step680. In case of escape mode1, in step681, VLD210corrects the level of the symbol in the output buffer. Level correction generally entails adding the LMAX value corresponding to the run value. The corrected level value is written back to the output buffer.

Similarly, in case of escape mode2, in step682, VLD210corrects the level of the symbol (intermediate value) in the output buffer. In case the mode identifier equals escape mode3, in step683, VLD210generates the symbol (run-value pair) from the M-bits in the output buffer.

In step690, control passes to step675if there are additional entries in the intermediate buffer. Otherwise, the flowchart ends in step699. From the above, it may be appreciated that the output buffer would contain all the sequence of symbols corresponding to the sequence of code-words received by VLD210.

It may further be appreciated that the code-words not encoded in escape modes, are generated inFIG. 6A(and stored in the output buffer) before the code-words encoded according to escape modes, even if the code-words encoded according to escape modes are present ahead in the received sequence.

Also, the loop ofFIG. 6Bis executed only as many times as the number of occurrences of code-words encoded according to escape modes.

Further, As the decoding process is split into two independent parts, the number of conditional instructions executed in each part is reduced. Hence such conditional instructions may be executed using the predicate registers noted above in VLIW architectures, instead of using branches for conditional execution. As a result, the code can be scheduled and characteristic VLIW throughput performance is achieved, which is superior compared to the approach ofFIG. 3. The increase in throughput performance compared toFIGS. 5A and 5B, is illustrated below with respect toFIGS. 7A and 7B.

9. Timing Diagram Illustrating the Enhanced Throughput Performance

FIG. 7Ais shown containing two sets of instructions710and720respectively executing flowchart ofFIGS. 6A and 6B. It is assumed that instruction set710contains four instructions711–714and instruction set720contains seven instructions721–727, and in particular that instructions711–713implement steps610–615and instruction714implements steps620to645. Instructions721–727implement flowchart6B for all the entries in the intermediate buffer (described above).

FIG. 7Bdepicts the manner in which the execution of instructions of711–714is repeated 4 times (as shown by iterations730,740,760and770) and once execution instruction721–727(as shown by iteration780) in time domain (line750). Four iterations730,740,760and770are performed to access the relevant entries from a table and writing the intermediate value to an intermediate buffer in case of escape modes. Multiple iterations of780are performed to correct the intermediate values according to the corresponding entries in the intermediate buffer.

As can be readily appreciated, iteration740starts after completion of execution of instruction713of iteration730. Such a loop carry dependency is due to data dependency since the decoding of second code-word cannot be started until the length of the first code-word (from iteration530) is determined. However, loop carry dependency due to conditional processing (552–553as in case of prior art inFIG. 5) is reduced by not performing decoding operations (in iterations730,740,750and760) corresponding to symbols encoded in escape mode.

Iteration780may consume minimal processing time since iteration780is performed only for the number of escape codes received. Further, iteration780may be started before (the shown) time point755while decoding subsequent set of symbols, thereby enabling further parallelism. In comparison withFIG. 5B, it may be appreciated that the throughput performance in generating the symbols is enhanced by using parts1and2.

Manner in which first part inFIG. 6Aand second part inFIG. 6Bis implemented is illustrated in further detail below with an example.

FIG. 8Acontains a table (referred in various approaches described above) representing a portion of an example Huffman table used for encoding run value pairs by Huffman encoder170. Rows811–816respectively represents entries corresponding 6 run-value pairs, columns820,830,835and840respectively represents run, value, mode indicator indicating one of the four modes in which corresponding run-value are coded, and a digital code resulting from encoding the corresponding run-value-last triplets, which is then transmitted.

Run-value-last triplets in rows811and812and816are respectively encoded in table mode or without escape mode, (as indicated in column835) with the corresponding digital codes 100, 000001000000 and 0011100. The run-value-last triplets in rows813–815are encoded respectively in escape modes1,2and3(as indicated in column835). Accordingly the corresponding digital codes are represented in column840.

The table inFIG. 8Bfurther illustrates the manner in which the sequence of bits of column840contain code-words represent the run-value pair (symbols) in columns820/830in case of representation by escape modes (rows813–815). The manner in which the symbols of rows813–815represent corresponding code-words is respectively illustrated by rows881–883.

Column891of all three rows881–883contains a bit sequence 0000011 indicating that the symbols of all the three rows are encoded according to an escape mode. In the following bit positions, values of 0, 10, and 11 respectively represent escape modes1,2, and3respectively as represented by column892. For modes1and2, the last, not-last status is indicated by the Huffman code-word of the modified run-value pair, whereas for escape mode3, another bit (0 for not-last) is appended to the escape mode code-word. Thus, the code-word for escape modes1,2and3respectively equal 00000111, 000001110, and 0000011110.

Column893indicates intermediate values corresponding to each escape code in row813–815. In case of escape mode3the intermediate value is shown containing the binary representation of corresponding run-level (10, 10) value in row815. Accordingly, the bits following the code-word representing the escape mode identifier, are used to determine the symbols. Thus, in case of escape modes1and2, the code-word following the escape mode identifier code-word is decoded to generate the intermediate value. Thus, with respect to rows813,811and881, it may be appreciated that intermediate value generated for symbol (0, 13) equals (0, 1) assuming LMAX=12. In case of escape mode3, the run and values are represented in binary values as shown in rows815and883.

The manner in which the code-words encoded according to the table inFIG. 8Aare decoded using the approach described above is illustrated below with reference toFIGS. 9A–9C. In other words, the manner in which each entry of column840would be decoded is described below. It is further assumed that all these six code-words are part of a single macro-block (of a video image frame, noted above) and received in successive positions.

Broadly, the flowchart ofFIG. 6Agenerates the output buffer ofFIG. 9Aand intermediate buffer ofFIG. 9Bwhen processing the successive code-words of column840received in successive positions. The flowchart ofFIG. 6Bthen processes each entry ofFIG. 9Bto update the entries inFIG. 9Ato generate the final values in output buffer ofFIG. 9C.

Now with respect toFIG. 9A, the first part (flowchart ofFIG. 6A), generates six entries901–906in output buffer900corresponding to each of the symbols of rows811–816. The six entries are assigned index values of 0–5 as shown in column910. As may be appreciated from rows901,902and906(corresponding to rows811,812and816), the run level values of code-words in non-escape mode are written by operation of the first part.

However, in case of escape modes1and2, the intermediate values of column835(of rows813and814respectively) are written into corresponding rows (903and904) of columns920and930. It should be appreciated that the intermediate values in case of escape modes and also code-words in case of table mode are generated using similar processing logic, and thus both can be written into output buffer900without requiring conditional processing logic. In case of escape mode3, as shown in row905, the bits following the escape mode code-word are written into columns920and930, as desired. (NOTE: inFIG. 9A, row909should be904)

The flowchart ofFIG. 6B(part2) processes every entry/row in the intermediate buffer949ofFIG. 9B. Thus, with respect to row911, part2reads the array1index value 2 and the escape type1(corresponding to level escape). Part2generates a new run-value pair (0, 13) by adding a maximum value (in this case, assumed to be 12 for run0) to the value in row903, column930. The corrected run-value pair is updated in to array1as shown in row973(corresponding to row903ofFIG. 9A)FIG. 9C. The processing of remaining entries ofFIG. 9Bis similarly described.

It should also be appreciated that the features described above may be implemented in various combinations of hardware, software and firmware, depending on the corresponding requirements. The description is continued with respect to an embodiment in which the features are operative upon execution of the corresponding software instructions.

11. Digital Processing System

FIG. 10is a block diagram of computer system1000illustrating an example system for implementing the decoder noted above. Computer system1000may contain one or more processors such as central processing unit (CPU)1010, random access memory (RAM)1020, secondary memory1030, graphics controller1060, display unit1070, network interface1080, and input interface1090. All the components except display unit1070may communicate with each other over communication path1050, which may contain several buses as is well known in the relevant arts. The components ofFIG. 10are described below in further detail.

CPU1010may execute instructions stored in RAM1020to provide several features of the present invention. CPU1010may contain multiple processing units, with each processing unit potentially being designed for a specific task. Alternatively, CPU1010may contain only a single processing unit. RAM1020may receive instructions from secondary memory1030using communication path1050. In addition, RAM1020may store the various buffers/arrays described above.

Graphics controller1060generates display signals (e.g., in RGB format) to display unit1070based on data/instructions received from CPU1010. Display unit1070contains a display screen to display the images defined by the display signals. The decoded video frames may be displayed on the display screen. Input interface1090may correspond to a keyboard and/or mouse, and generally enables a user to provide inputs. Network interface1080enables some of the inputs (and outputs) to be provided on a network.

Secondary memory1030may contain hard drive1038, flash memory1036and removable storage drive1037. Secondary storage1030may store the software instructions and data (e.g., the VLC tables), which enable computer system1000to provide several features in accordance with the present invention.

Some or all of the data and instructions may be provided on removable storage unit1040, and the data and instructions may be read and provided by removable storage drive1037to CPU1010. Floppy drive, magnetic tape drive, CD-ROM drive, DVD Drive, Flash memory, removable memory chip (PCMCIA Card, EPROM) are examples of such removable storage drive1037.

Removable storage unit1040may be implemented using medium and storage format compatible with removable storage drive1037such that removable storage drive1037can read the data and instructions. Thus, removable storage unit1040includes a computer readable storage medium having stored therein computer software and/or data. An embodiment of the present invention is implemented using software running (that is, executing) in computer system1000.

In this document, the term “computer program product” is used to generally refer to removable storage unit1040or hard disk installed in hard drive1031. These computer program products are means for providing software to computer system1000. As noted above, CPU1010may retrieve the software instructions, and execute the instructions to provide various features of the present invention described above.

While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.