Method and system for providing arithmetic code normalization and byte construction

A method and system are provided for code normalization and byte construction. A plurality of subsets of bits is extracted from a first input. Each of the subsets of bits has a bit width equaling a number of leading zeros from a second input variable. Further, a consecutive sequence of the plurality of subsets is stored in a memory. In addition, the consecutive sequence of the plurality of subsets is read from the memory if a third input release flag is established.

BACKGROUND

This disclosure generally relates to the field of video data processing. More particularly, the disclosure relates to Context Adaptive Binary Arithmetic Coding (“CABAC”) for digital video encoders.

2. General Background

Video signals generally include data corresponding to one or more video frames. Each video frame is composed of an array of picture elements, which are called pixels. A typical color video frame having a standard resolution may be composed of over several hundreds of thousands of pixels, which are arranged in arrays of blocks. Each pixel is characterized by pixel data indicative of a hue (predominant color), saturation (color intensity), and luminance (color brightness). The hue and saturation characteristics may be referred to as the chrominance. Accordingly, the pixel data includes chrominance and luminance. Therefore, the pixel data may be represented by groups of four luminance pixel blocks and two chrominance pixel blocks. These groups are called macroblocks (“MBs”). As a video frame generally includes many pixels, the video frame also includes a large number of MBs. Thus, digital signals representing a sequence of video frame data, which usually include many video frames, have a large number of bits. However, the available storage space and bandwidth for transmitting these digital signals is limited. Therefore, compression processes are used to more efficiently transmit or store video data.

Compression of digital video signals for transmission or for storage has become widely practiced in a variety of contexts. For example, multimedia environments for video conferencing, video games, Internet image transmissions, digital TV, and the like utilize compression. Coding and decoding are accomplished with coding processors. Examples of such coding processors include general computers, special hardware, multimedia boards, or other suitable processing devices. Further, the coding processors may utilize one of a variety of coding techniques, such as variable length coding (“VLC”), fixed coding, Huffman coding, blocks of symbols coding, and arithmetic coding. An example of arithmetic coding is Context Adaptive Binary Arithmetic Coding (“CABAC”).

CABAC techniques are capable of losslessly compressing syntax elements in a video stream using the probabilities of syntax elements in a given context. The CABAC process will take in syntax elements representing all elements within a macroblock. Further, the CABAC process constructs a compress bit sequence by building out the following structure: the sequential set of fields for the macroblock based on the chosen macroblock configuration, the specific syntax element type and value for each of the fields within this field sequence, and the context address for each of the syntax elements. The CABAC process will then perform binarization of the syntax elements, update the context weights, arithmetically encode the binarizations of syntax elements (“bins”), and subsequently pack the bits into bytes through the syntax element processing component.

The components of the CABAC process include: the CABAC weight initialization mode selection module, the macroblock syntax sequence generator, the binarization engine, the context address generator, the context weight update engine, the arithmetic coder, the bit packetizer, and the Network Abstraction Layer (“NAL”) header generator. The CABAC engine within a video encoder may accomplish two goals within the encoding process: (1) to carry out compressed data resource prediction for mode decision purposes; and (2) to losslessly compress the data for signal output delivery. The compressed data resource prediction task predicts the amount of bits required given a set of specific encoding modes for a given macroblock. Potential mode decision implementations may have up to eight modes to select from. The computational demand on the CABAC engine to support the mode decision task is significant.

The weight update, arithmetic encoder and the bit packing components of the CABAC engine may require a significant amount of non-trivial computational and processing resources in a sequential processor implementation. Given that high performance encoding systems require multiple macro block rate distortion iterations of encoding per macro block, the CABAC process may impose an unreasonable resource demand on a processor-based solution. Prior implementations typically compromise on mode decision CABAC resource estimation accuracy by limiting the CABAC to bin level accuracy.

A system capable of processing one binary symbol per clock cycle requires a matching back end-receiving engine capable of also processing the results on every cycle. The back end tasks consist of a value normalization task, which may generate up to eight bits of data, and a bit packing task, which groups the bits into bytes. The implementation solutions for the normalization and bit packing tasks are complex and computationally demanding.

Current implementations of the normalization function for the CABAC arithmetic coder fall into two categories. The first category includes routines that can generate at most one bit per cycle. This approach may utilize up to eight cycles to process one binary symbol as a single binary symbol may generate up to eight bits. The second category includes routines that achieve single cycle per binary symbol using a method that does not optimally handle all cases of the carry from the input data and the adder.

SUMMARY

In one aspect of the disclosure, a process extracts a plurality of subsets of bits from a first input. Each of the subsets of bits has a bit width equaling a number of leading zeros from a second input variable. Further, the process stores, in a memory, a consecutive sequence of the plurality of subsets. In addition, the process reads the consecutive sequence of the plurality of subsets from the memory if a third input release flag is established.

In another aspect, a process stores a consecutive set of variable bit width data into a first in first out buffer. The variable bit width data has a width that is determined by a number of leading zeroes from an input variable. Further, the process reads the data from the first in first out buffer if the receiving data contains only ones.

In yet another aspect, a process stores a consecutive set of data from a first input variable into a memory. Further, the process receives a subsequent data set from the first input variable. In addition, the process reads the consecutive set of data from the memory if the subsequent data set includes one or more binary bits having a value of zero.

DETAILED DESCRIPTION

A method and system are disclosed, which provide an improved video digital data compression capable of providing a single cycle normalization for real-time digital video encoders, such as an MPEG-4 or an H-264 series encoder. The method and system may be utilized by the back end processor within the arithmetic encoder. As a result, normalization and payload to byte packing may be accomplished.

FIG. 1illustrates a CABAC process100. At a process block102, the CABAC process100selects a CABAC weight initialization mode. Further, at a process block104, the CABAC process100generates an MB syntax sequence. In addition, at a process block106, the CABAC process106converts a syntax to binary. The term binarization may be utilized to denote the process block106. Further, at a process block108, the CABAC process100performs a context address determination. The term ctxldx generation may be utilized to denote the process block108. At a process block110, the CABAC process100performs a context weight update. Further, at a process block112, the CABAC process100performs an arithmetic encoding. In addition, at a process block114, the CABAC process100performs a bit packetizing. Finally, at a process block116, the CABAC process100performs a NAL header construction. An elementary stream results from the CABAC process100.

FIG. 2illustrates an arithmetic coder normalization process200. In one embodiment, the arithmetic coder normalization process200can be utilized for the MPEG4 standard to process data at the bit level. The arithmetic coder normalization process200may utilize up to eight loop iterations to process a single binary input symbol from the front end arithmetic coder. Accordingly, an upper bound is placed on the computational demand. The arithmetic coder normalization process begins at a process block202. Further, at a process block204, the arithmetic coder normalization process200receives a codeLow input variable and a codeRange input variable. In one embodiment, the codeLow input variable includes ten bits and the codeRange input variable includes nine bits. Further, at a process block206, the arithmetic coder normalization process200increments an internal index. For example, the arithmetic coder normalization process200may increment an internal index “t” by one. In addition, at a process block208, the arithmetic coder normalization process200extracts the most significant bit from the codeLow input variable for a carry bit. At a process block210, the arithmetic coder normalization process200sets a variable to hold the number of leading zeros of the codeRange input variable. For example, the variable may be entitled shftCnt. Further, at a next process block212, the arithmetic coder normalization process200extracts a block of bits from the codeLow input variable. This is accomplished by discarding the most significant bits of the codeLow input variable and removing all the leading zeros to form a variable bit width block of bits. The variable bit width block of bits is then stored in a payload array at location t, which may be referred to by the variable payload[t].

At a decision block214, the arithmetic coder normalization process200determines if the contents of the variable payload[t], i.e., the bits, include only ones or both ones and zeroes. If the variable payload(t) includes both ones and zeroes, the arithmetic coder normalization process200proceeds to a process block216. At the process block216, the arithmetic coder normalization process begins with the first entry of the payload array. A carry is added to the first entry in the payload array. The payload is then outputted without the resulting carry. The arithmetic coder normalization process200then adds the carry from the addition of the first entry in the payload array to the second entry in the payload array. The payload is then outputted without the resulting carry. The arithmetic coder normalization process200works through the entries payload array in a similar manner until the entry in payload(t−1) is processed. The iterations through these entries in the payload array may be denoted by the following code: for (i=0; i<t; i++ ) {payload[i] += carry; Output(payload[i]}. Once the entry in payload[t−1] is processed, the arithmetic coder normalization process200proceeds to a process block218where the most recent payload is moved to the base of the array, which may be denoted by payload[0] = payload[t]. The arithmetic coder normalization process200then proceeds to a process block220to reset the payload array by setting the variable t to zero. The arithmetic coder normalization process200then ends at a process block230.

If the arithmetic coder normalization process200determines, at the decision block212, that the contents of the variable payload[t] include only ones, the arithmetic coder normalization process proceeds from the decision block212to the process block222. At the process block222, the carry bit is examined. The arithmetic coder normalization process200then proceeds to a decision block224to determine if the input carry bit equals one. If the arithmetic coder normalization process200determines that the input carry bit equals one, the arithmetic coder normalization process200proceeds to a process block226. At the process block226, the arithmetic coder normalization process200outputs all payload entries from index zero to index t sequentially beginning with the index zero. This approach can be denoted by the following code: for (i=0; i<=t; i++ ) {Output(payload[i])}. The arithmetic coder normalization process200then proceeds to a process block228. At the process block228, the arithmetic coder normalization process200resets the index to negative one. The arithmetic coder normalization process200then ends at a process block230.

If the arithmetic coder normalization process200determines, at the decision block224, that the input carry bit does not equal one, the arithmetic coder normalization process200ends at the process block230.

FIG. 3illustrates a normalization and bit packing engine300capable of receiving one codeLow input and one code range input per cycle. This approach is based on binarization of syntax element (“bin”) level processing. In one embodiment, a hardware solution is capable of providing a normalization and bit packing to bytes operation. This approach significantly reduces the hardware resources utilized by current systems. Specifically, this approach utilizes logic instead of memory lookup tables to resolve decision making tasks.

The normalization and bit packing engine300receives two distinct variables: a codeLow variable302and a codeRange variable304, on every clock cycle. A leading zero detector306generates an output that is equal to the number of leading zero binary bits in the codeRange variable304. This output is registered in a latch shiftCnt308. A bus splitter310outputs a carry bit and a dchunk variable. The carry bit is extracted from the most significant bit of the codeLow variable302. Further, the dchunk variable, which includes the second through ninth lower bits of the codeLow variable302, is then shifted right by shiftCnt variable308through a shift latch312. The output dchunkRa of this shift latch312is then further shifted by bitPos16_1variable through a bitPos16_1shift latch314to align the data to fit into an output preparation register316. The output preparation register316is utilized to hold data until there are enough output bits to form a full byte. In another embodiment, a plurality of output preparation registers316may be utilized.

A bit position calculator318generates a bitPos16_1variable and a byte ready flag based on the input to the shiftCnt variable. The bitPos16_1variable identifies where the dchunkR should reside within the output preparation register316. The byte ready flag identifies when the least significant byte320is ready for output. The bitPos16_1shift latch314outputs dchunk16, which is then sent to a logical or gate322along with the output from the output preparation register316. The output from the logical or gate322is then sent to an adder324along with a shifted carry bit from a shift latch326to form both the output byte328and the new data for the output preparation register316. The shifted carry bit is generated by the shift latch326, which shifts the logically conditioned carry bit utilizing oneFlag_d, a delayed carry flag carry_d6, and a delayed carry flag carry_d5.

The oneFlag_d is generated by first providing dchunk to an all ones detector330. If dchunk is all ones, the all ones detector330outputs oneFlag and provides oneFlag to a latch332. The latch332shifts oneFlag and outputs oneFlag_d.

The oneFlag_d is provided along with a delayed carry flag carry_d6to a first gate330. Further, the output of the first gate334is provided along with a delayed carry flag carry_d5to a second gate336.

The output of the adder324is split into a plurality of bytes through a bit splitter338. In one embodiment, the bit splitter338splits the output of the adder324into three bytes. Further, in one embodiment, the bit splitter338is a twenty four bit splitter. The most significant byte is provided to an output byte register340, which may be denoted by the term outByte. The two least significant bytes are routed through a multiplexor342to feed the inputs of the output preparation register316. Based on the byteRdy flag, the multiplexor342selects one of the two lower output bytes from the adder324for the middle byte344of the output preparation register316.

FIG. 4illustrates a process400for code normalization and byte construction. At a process block402, the process400extracts a plurality of subsets of bits from a first input. Each of the subsets of bits has a bit width equaling a number of leading zeros from a second input variable. Further, at a next process block404, the process400stores, in a memory, a consecutive sequence of the plurality of subsets. In addition, at a process block406, the process400reads the consecutive sequence of the plurality of subsets from the memory if a third input release flag is established.

FIG. 5illustrates another process500for code normalization and byte construction. At a process block502, the process500stores a consecutive set of variable bit width data into a first in first out buffer. The variable bit width data has a width that is determined by a number of leading zeroes from an input variable. Further, at a process block504, the process500reads the data from the first in first out buffer if the receiving data contains only ones.

FIG. 6illustrates yet another process600for code normalization and byte construction. At a process block602, the process600stores a consecutive set of data from a first input variable into a memory. Further, at a process block604, the process600receives a subsequent data set from the first input variable. In addition, at a process block606, the process600reads the consecutive set of data from the memory if the subsequent data set includes one or more binary bits having a value of zero.

FIG. 7illustrates a block diagram of a station or system700that implements a code normalizer and byte construction engine. In one embodiment, the station or system700is implemented using a general purpose computer or any other hardware equivalents. Thus, the station or system700comprises a processor (“CPU”)710, a memory720, e.g., random access memory (“RAM”) and/or read only memory (ROM), a normalization and byte construction module740, and various input/output devices730, (e.g., storage devices, including but not limited to, a tape drive, a floppy drive, a hard disk drive or a compact disk drive, a receiver, a transmitter, a speaker, a display, an image capturing sensor, e.g., those used in a digital still camera or digital video camera, a clock, an output port, a user input device (such as a keyboard, a keypad, a mouse, and the like, or a microphone for capturing speech commands)).

It should be understood that the code normalization and byte construction module740may be implemented as one or more physical devices that are coupled to the CPU710through a communication channel. Alternatively, the normalization and byte construction module740may be represented by one or more software applications (or even a combination of software and hardware, e.g., using application specific integrated circuits (ASIC)), where the software is loaded from a storage medium, (e.g., a magnetic or optical drive or diskette) and operated by the CPU in the memory720of the computer. As such, the normalization and byte construction module740(including associated data structures) of the present invention may be stored on a computer readable medium, e.g., RAM memory, magnetic or optical drive or diskette and the like.

It is understood that the normalization and byte construction engine described herein may also be applied in other type of encoders. Those skilled in the art will appreciate that the various adaptations and modifications of the embodiments of this method and apparatus may be configured without departing from the scope and spirit of the present method and system. Therefore, it is to be understood that, within the scope of the appended claims, the present method and apparatus may be practiced other than as specifically described herein.