System and method for accelerating arithmetic decoding of video data

Presented herein is a system and apparatus for accelerating arithmetic decoding of encoded data. In one embodiment, there is presented a symbol interpreter for decoding CABAC coded data. The symbol interpreter comprises a first memory, a CABAC decoding loop, and a syntax assembler. The first memory receives a bitstream comprising the CABAC coded data at a channel rate. The CABAC decoding loop decodes the CABAC symbols at the channel rate, and comprises an arithmetic decoder for generating binary symbols from the CABAC coded data at the channel rate. The syntax assembler decodes the binary symbols at a consumption rate.

FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

BACKGROUND OF THE INVENTION

Based on established and proposed standards for encoding and decoding video data, such as H.264 (also known as MPEG-4, Part 10, and Advanced Video Coding), encoded digital video data may be broadcast at data rates exceeding 20 MBits per second for high definition television (HDTV). For compression, the H.264 standard allows individual frames to be encoded using varying amounts of data. As an example, the first frame of a sequence contains complete picture detail, and therefore requires more data, while subsequent frames are largely predicted from preceding frames, and therefore need only enough data to describe the differences.

H.264 optionally uses context adaptive binary arithmetic coding (CABAC) to further compress data that has already been compressed using spatial and temporal prediction, transforms, quantization and other techniques.

Unlike the other methods, CABAC is categorized as lossless compression because CABAC coding does not result in the loss of information. Nevertheless, CABAC can result in considerable compression gains.

In CABAC encoded data, a “syntax element”, which typically represents a coefficient or other datum from prior compression, is encoded as a variable length sequence of binary bits (“Bins”), and the individual Bins (i.e. 2-valued symbols) are then encoded using arithmetic coding. Arithmetic encoding expresses a sequence of symbols as a single fractional binary number between 0 and 1 using recursive subdivision of intervals to encode successive symbols. The number has as many fractional bits of precision as are needed to express its value. The relative likelihood of occurrence of a 1 and a 0 is used to encode the Bin with statistically optimal efficiency. In the CABAC decoder, a dynamic context table is kept with likelihood entries for each of many different types of Bins within syntax elements. The context table is preloaded at the beginning of a “slice” of video data, and subsequently the appropriate context table entry is updated after each Bin of a syntax element is decoded. Because a context table entry is referenced and updated in order for each Bin, parallelization of the decoding process is computationally complex.

A typical HDTV video decoder may assemble 30 frames per second. The standard allows for encoded frame data sizes as high as 12 Mbits per frame for HDTV. Therefore, an arithmetic decoder may need to decode at speeds of 360 Mbits/sec of encoded data at a peak decoding rate, if it is to complete the decoding process for each frame within one frame time. The peak rate of Bins is even higher than 360 Mbits/sec in this case. It is difficult using conventional CMOS integrated circuits, to build an arithmetic decoder and context memory that operates at this rate.

Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of ordinary skill in the art through comparison of such systems with the present invention as set forth in the remainder of the present application with reference to the drawings.

BRIEF SUMMARY OF THE INVENTION

Presented herein is a system and apparatus for accelerating arithmetic decoding of encoded data.

In one embodiment, there is presented a method for decoding context adaptive binary arithmetic coded data. The method comprises receiving a bitstream comprising the context adaptive binary arithmetic coded data at a channel rate; decoding the context adaptive binary arithmetic coded data at the channel rate, wherein decoding the context adaptive binary arithmetic coded data at the channel rate comprises generating a stream of intermediate binary symbols from the context adaptive binary arithmetic coded data at the channel rate; and decoding the stream of intermediate binary symbols at a consumption rate.

In another embodiment, there is presented a symbol interpreter for decoding context adaptive binary arithmetic coded data. The symbol interpreter comprises a first memory, a context adaptive binary arithmetic coded data decoding loop, and a syntax assembler. The first memory receives a bitstream comprising the context adaptive binary arithmetic coded data at a channel rate. The context adaptive binary arithmetic coded data decoding loop decodes the context adaptive binary arithmetic coded data at the channel rate, and comprises an arithmetic decoder for generating intermediate binary symbols from the context adaptive binary arithmetic coded data at the channel rate. The syntax assembler decodes the intermediate binary symbols to generate syntax elements at a consumption rate.

In another embodiment, there is presented a decoder for decoding context adaptive binary arithmetic coded data. The decoder comprises a first memory, a context adaptive binary arithmetic coded data decoding loop, and a syntax assembler. The first memory receives a bitstream comprising the context adaptive binary arithmetic coded data at a channel rate. The context adaptive binary arithmetic coded data decoding loop is operably coupled to the first memory to decode the context adaptive binary arithmetic coded data at the channel rate, and comprises an arithmetic decoder. The arithmetic decoder is operably coupled to the first memory to generate intermediate binary symbols from the context adaptive binary arithmetic coded data at the channel rate. The syntax assembler is operably coupled to the arithmetic decoder to decode the binary symbols to generate syntax elements at a consumption rate.

These and other advantages, aspects and novel features of the present invention, as well as details of illustrative aspects thereof, will be more fully understood from the following description and drawings.

DETAILED DESCRIPTION OF THE INVENTION

Referring now toFIG. 1, there is illustrated a block diagram describing exemplary encoded data. A data stream, that can represent a variety of original data100, such as digital video or audio, comprises a bit stream of data.

For example, where the original data is digital video, compression standards such as H.264 use spatial, temporal prediction, transformations, quantization, and scanning to reduce the amount of data representing the video data. Generally, the video data is represented by frequency coefficients and side information, known as syntax elements105. An encoder converts the syntax elements105into what are known as binary symbols (Bins)110. The Bins110are then encoded using arithmetic coding. Arithmetic encoding expresses a sequence of symbols as a single fractional binary number between 0 and 1 using recursive subdivision of intervals to encode successive symbols. The number has as many fractional bits of precision as are needed to express its value. The relative likelihood of occurrence of a 1 and a 0 is used to encode the Bin with statistically optimal efficiency. In context adaptive binary arithmetic coding (CABAC), a dynamic context table is kept with likelihood entries for each of many different types of Bins within syntax elements. The context table is preloaded at the beginning of a “slice” of video data, and subsequently the appropriate context table entry is updated after each Bin of a syntax element is decoded. The foregoing results in CABAC data115.

A transmitter can then transmit or broadcast the CABAC data115to decoders. Prior to transmission, additional processing, such as packetization and transport layering may also occur. The of CABAC data115preferably comprises significantly fewer bits than the original data100. As a result, less memory is used to store the CABAC data115and less bandwidth is used to transmit the CABAC data115. When the CABAC data115arrives at the decoder, the decoder decodes the CABAC data115back to the syntax elements105. The decoder then decodes the syntax elements105to reconstruct the original data100. In many cases, it is desirable to reconstruct the original data100in real time. For example, where the original data100represents digital video, the reconstructed original data100is displayed on a display device at specific times. Digital video100comprises a series of frames. When displayed at specific times, the frames simulate motion picture.

To display the frames for HDTV, the decoder reconstructs frames, on average, at least 30 frames/second. However, in H.264, varying amounts of the CABAC data115represent each frame. These amounts may vary, for example, from between a few dozen bits to 12 Mbits or more Therefore, to provide HDTV, the CABAC data115is decoded and decompressed at peak rates of up to 360 Mbits/sec. While the amount of data encoding each frame is varying, the frames in aggregate are still decoded at the same average rate for real-time applications. Decoding the CABAC data115back to the syntax elements105involves converting the CABAC data115to binary symbols110, and converting the binary symbols110to syntax elements105. Decoding the CABAC data115in parallel is difficult because the decoding of each Bin110from CABAC data115depends on previously decoded Bins110. As noted above, the CABAC data115assigned to code Bins110depends on the context table values developed from the previous Bins110.

Referring now toFIG. 2, there is illustrated a block diagram describing an exemplary video decoder400in accordance with an embodiment of the present invention. The video decoder400includes a code buffer405for receiving a video elementary stream. The code buffer405can be a portion of a memory system, such as a dynamic random access memory (DRAM). A symbol interpreter415in conjunction with a context memory410decodes the CABAC Bins and syntax elements from the bitstream. The context memory410can be another portion of the same memory system as the code buffer405, or a portion of another memory system.

The symbol interpreter415includes a VLC decoder415V and a CABAC decoder415B. The VLC decoder415V decodes sequences of Bins into syntax elements. The symbol interpreter415provides the syntax elements105for additional processing to recover the original data100, e.g, video data.

The symbol interpreter415receives the bit stream115of CABAC data115at a channel rate. For a video playback operation, the syntax elements105are processed to provide frames of digital video100at a consumption rate.

Referring now toFIG. 3, there is illustrated a block diagram of the symbol interpreter415B in accordance with an embodiment of the present invention. The symbol interpreter415B comprises a first memory104, such as SDRAM104, a CABAC decoding loop, and a syntax element assembler206. The first memory104receives CABAC data115at a channel rate.

The CABAC decoding loop decodes the CABAC data115at the channel rate. The CABAC decoding loop comprises an arithmetic decoder106, and can also comprise another syntax assembler108, and a selector112. The arithmetic decoder106converts the CABAC data115, to Bins110at the channel rate. The syntax assembler108converts the Bins110to syntax elements105. The selector112selects the context table entry to be used for decoding the next Bin based on the preceeding sequence of syntax elements105. The arithmetic decoder106converts CABAC data115to Bins110using (and updating) the selected context table entries stored in context RAM114. Sequencer11controls initialization of the context RAM114and starting and stopping of the CABAC decoding process.

While the CABAC decoding loop decodes the CABAC data115at the channel rate, the syntax element assembler206, similar to but possibly separate from syntax element assembler108, decodes the Bins110at the consumption rate, thereby generating syntax elements105. The syntax element assembler108can also be associated with a sequencer204.

The symbol interpreter415can also include another memory202, such as a buffer within an SDRAM, for storing Bins110generated by the arithmetic decoder106. The syntax element assembler206can request the Bins110from the memory202at the consumption rate.

Referring now toFIG. 5, there is illustrated a flow diagram for decoding CABAC data115in accordance with an embodiment of the present invention. At505, the CABAC data115, is received at a channel rate.

At510, the CABAC data115is decoded to Bins110at the channel rate. At515, the Bins110are decoded at a consumption rate, thereby generating syntax elements105.

Decoding the CABAC data115at the channel rate can also include generating510(2) syntax elements105from the binary symbols, and selecting510(3) the context table entry to be used for decoding the next bin, based on the preceeding sequence of syntax elements105.

The Bins110can also be written515(1) to a memory. The Bins110can subsequently be requested515(2) at the consumption rate and syntax elements105can then be generated515(3) from the Bins110at the consumption rate.

The embodiments described herein may be implemented as a board level product, as a single chip, application specific integrated circuit (ASIC), as part of an ASIC containing other functions, or with varying levels of the decoder system integrated with other portions of the system as separate components.

The degree of integration of the decoder system will primarily be determined by the speed and cost considerations. Because of the sophisticated nature of modern processor, it is possible to utilize a commercially available processor, which may be implemented external to an ASIC implementation. If the processor is available as an ASIC core or logic block, then the commercially available processor can be implemented as part of an ASIC device wherein certain functions can be implemented in firmware. Alternatively, the functions can be implemented as hardware accelerator units controlled by the processor.

While the present invention has been described with reference to certain embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the scope of the present invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the present invention without departing from its scope.

Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed, but that the present invention will include all embodiments falling within the scope of the appended claims.