Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
1997-10-27
2001-06-12
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S050000
Reexamination Certificate
active
06246347
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to variable length decoders (VLDs) used in data transmission systems, such as digital video data transmission systems, and more particularly, to a controller for a VLD, especially for a VLD which is programmable for decoding digital video data streams which are encoded in accordance with any of various different digital video compression standards, including both current coding protocols such as MPEG-1, MPEG-2, JPEG, H.261, H.263, DVC, and evolving and future coding protocols such as MPEG-4, H.263+, standard extensions, etc.
Efficient communication protocols are used in the transmission of digitally compressed images. These protocols have been created to target different applications, such as standard- and high-definition television, video conferencing, video recording on magnetic tape, and still image transmission. Some protocols have been standardized, such as MPEG-1, MPEG-2, JPEG, H.261, H.263, DVC, and many others. Other protocols are being developed to become standardized in the future, such as MPEG-4, H.263+, and standard extensions. Huffman codes are used in all of these protocols to compress various components of video data. Variable length decoders (VLDs) are used in digital video decoders to decode Huffman-encoded bit streams consisting of variable length coded (VLC) words or symbols.
There are striking general similarities among the different digital video compression standards. For example, most of the video compression standards take advantage of motion estimation to achieve temporal data compression, and the quantized Discrete Cosine Transform (DCT) to achieve spatial data compression. As a result, the “DCT block” and “macroblock” data representations are used almost universally, and code words such as DC and AC coefficients and motion vectors are treated almost identically in many standards. Provided that such fundamental data types along with other information have been decoded by the VLD, this data can be used in a universal decoder capable of decoding multiple compression standards. The video decoders, however, differ drastically in algorithms prescribed for their respective VLDs.
Digital video decoders generally perform four consecutive functions: variable length decoding, inverse quantization, inverse discrete cosine transform and motion compensation. The functions of variable length decoding, inverse quantization and inverse discrete cosine transform are used almost universally, while the function of motion compensation is used in some (MPEG-2, H.261) and is not used in other (JPEG, DVC) compression standards.
In digital video decoder designs, the compressed digital video bit streams are normally buffered using a sufficient amount of memory generally prescribed by a compression standard. The VLD is generally preceded by a buffer memory called a “rate buffer”. The bit width of a bit stream segment stored in the rate buffer is normally defined by the longest word in the compression protocol, which does not exceed 32 bits in the currently used video compression standards. The Huffman encoded data bits of this stored segment are presented to the VLD circuits for decoding.
Both dedicated and programmable VLDs must perform three distinct functions: bit stream segmentation or parsing, reconstruction of data values, and predicting the type of a Huffman symbol that follows. In this fashion, the VLD can produce the value of the current symbol, advance to the next symbol in the bit stream segment, and then select an appropriate table for its decoding.
The fundamental table look-up VLD is disclosed in U.S. Pat. No. 5,173,695, issued to Sun et al., the disclosure of which is incorporated herein by reference. This dedicated VLD includes a barrel shifter that provides an output decoding window having a bit width equal to the maximum-length code word. In response to a control signal, the barrel shifter directly shifts its decoding window across a sequence of available input bits as each code word is detected. To detect each code word, the leading bits in the decoding window are compared with code word entries in a look-up table. When a code word is detected, its corresponding code word length is added to the value of an accumulator with previously accumulated code word lengths to produce the control signal which directly shifts the decoding window by the number of bits in the just decoded word. Thus, the decoding window is shifted to the beginning of the next code word in the undecoded sequence of available input bits. The shifting of the decoding window and the decoding of the code word can be accomplished in one clock cycle. As a result, the table look-up decoder is capable of decoding one code word per clock cycle regardless of its bit length, thereby increasing the data throughput of the VLD relative to the previously available tree searching algorithm VLD. For reference, and advanced tree searching algorithm VLD (“Multi-Code-Book Variable Length Decoder”) is disclosed in the present inventor's U.S. patent application Ser. No. 08/580,404, filed on Dec. 28, 1995, which is assigned to the assignee of the present invention, and the disclosure of which is incorporated herein by reference.
It should be noted that the present inventor (along with co-inventors Victor L. Gornstein and Howard B. Pein) has developed a unique VLD architecture which greatly improves the speed of VLD operation by utilizing a “one-hot” data representation in the VLD, resulting in a VLD architecture which greatly accelerates the timing critical length decoding loop, which VLD architecture is disclosed in U.S. Pat. No. 5,650,905, issued on Jul. 22, 1997, and U.S. application Ser. No. 08/671,891 (which is a C-I-P of the '905 patent), filed on Jun. 28, 1996. These patents are also assigned to the assignee of the present invention, and are also incorporated herein by reference. With the one-hot architecture of the length decoding loop, the barrel shifter is preferably replaced by a one-hot bit stream barrel shifter matrix, the conventional word length decoder is replaced by a one-hot word length decoder, and the adder-accumulator is replaced by a one-hot ring barrel shifter matrix and a one-hot overflow matrix. Although not limiting to the present invention, this one-hot data representation and one-hot length decoding loop architecture is utilized in the preferred embodiment of the present invention disclosed hereinafter.
Although the number of variable length code variations in the Huffman look-up tables is relatively small, straightforward utilization of memories in both length- and value-decoders is impractical, due to the very wide address field which is required. For this reason, and also due to speed considerations in many applications, such as HDTV, a logic array decoding structure is normally utilized. Typically, the logic array decoding structure includes a plurality (plane) of fixed-width AND gates each of whose input signals have been selectively inverted to match a respective different one of all of the possible Huffman codes which are prescribed by the coding protocol employed. The AND plane is followed by an OR plane in which all code variations which lead to the same decoding results are combined to produce an output.
It becomes readily apparent that such a logic array decoding structure is dedicated to decoding bit streams which are encoded in accordance with a single fixed coding protocol compression standard). Thus, since it is not programmable, it is incapable of decoding bit streams which are encoded in accordance with any other coding protocol.
At the present time, there is a need in the industry for a VLD which is programmable for decoding digital video (and other Huffman-encoded) data streams which are encoded in accordance with any of various different digital video compression standards, including both current coding protocols such as MPEG-1, MPEG-2, JPEG, H.261, H.263, DVC, and evolving and future coding protocols such as MPEG-4, H.263+, standard extensions, etc. In parsing the bit str
Gathman Laurie E.
Jean-Pierre Peguy
Philips Electronics North America Corporation
Tokar Michael
LandOfFree
Controller for a variable length decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Controller for a variable length decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Controller for a variable length decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2544783