Various techniques for coding video are described in standards promulgated by organizations such as the Moving Picture Expert Group (MPEG), the International Telecommunications Union (ITU), the International Organization for Standardization (ISO), and the International Electrotechnical Commission (IEC). For example, Context Adaptive Binary Arithmetic Coding (CABAC) is an entropy coding requirement specified in the H.264/AVC standard ITU-T/ISO/IEC H.264/MPEG-4 (Part 10) Advanced Video Coding (Video Coding for Very Low Bit Rate Communication, ITU-T Recommendation H.264 (May 2003), ITU-T Recommendation H.264: Advanced video coding for generic audiovisual services, ISO/IEC 14496-10:2005 (E)).
CABAC involves arithmetic coding which is quite high in computational complexity. Arithmetic coding takes a stream of symbols as input and outputs a floating point number between 0 and 1 based on the probability of occurrence of each symbol in the input stream. The longer the input stream size, the more bits required to represent the floating point number. In order to avoid this floating point number from overflowing, a renormalization process is used.
The renormalization process uses a range value (e.g., codIRange) and an offset value (e.g., codILow) to output bits at every clock into a compressed bitstream. Binary arithmetic encoding is used to modify the codIRange value and the codILow value at every clock and to provide the modified values as inputs for the next clock. The values are used again and again in a iterative loop. When values outside a certain range or window, the values are renormalized and brought back within the window.
The renormalization process generally involves restricting a nine bit codIRange value and a 10 bit codILow value to specific ranges. If the codIRange value falls within a 0-255 range, the codIRange value is pushed into a 256-511 range by multiplying the codIRange value by 2 repeatedly (e.g., in N steps).
For the N iterations, if the codILow value falls in the 256-511 range, the codILow value is subtracted by 256 while incrementing a bitsOutstanding value. If the codILow value falls in the 512-1023 range, the codILow value is subtracted by 512 while outputting ‘1’. If the codILow value falls in the 0-255 range, the codILow value is multiplied by 2 while outputting ‘0’.
This renormalization process is sequential in nature and is a bottleneck in achieving a high throughput CABAC encoder. Current solutions for CABAC renormalization are software based and take multiple cycles to normalize one value. Hardware based solutions generally take 3 to 5 cycles per bit. Typical CABAC encoders output 1 bit for every 3 to 5 clocks on the average. This means for 200 MHz clock frequency, at 1 bit for every 4 clocks, the encoding bit rate is 50 Mbps. Therefore, to encode higher bitrate video streams at real time requires higher frequency of operation.