Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
1999-12-28
2004-08-03
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Including details of decompression
C382S246000
Reexamination Certificate
active
06771824
ABSTRACT:
BACKGROUND OF THE INVENTION
1.Field of the Invention
This disclosure relates to coding methods and, in particular, to a Huffman decoder.
2.Description of the Related Art
Huffman coding is a variable length coding (VLC) technique for lossless data compression that, unlike the lossy nature of transform based coders, provides for the exact recovery of the original data from its compressed version. Compression is achieved by assigning longer codewords to less frequent input symbols and shorter codewords to the more frequent input symbols. Given the source symbol probability distribution, a Huffman coder achieves optimality; that is, the average length of Huffman code approaches the theoretical minimum, i.e., the entropy of the source, where the entropy of the source is defined as the minimum number of bits needed to encode the entire message with lossless compression.
Due to its simplicity and efficient compression capability, Huffman coding has been widely used in the international standards for Group 3 fax, Group 4 fax, JPEG image compression, and MPEG1/MPEG2 video compression.
Huffman encoders map the input source data into codewords of variable length, concatenate them all together and then segment them into fixed-length words (e.g., 8 bits or 16 bits). Huffman encoding can be implemented via table look-ups, or bit-serial operations by traversing a Huffman tree. The use of table look-ups usually speeds up the encoding process. A Huffman look-up table is built based on the empirical source symbol probability distribution. Due to the different characteristics of the data statistics, different applications may have different Huffman look-up tables.
Huffman decoding presents a set of unique challenges. Since different source symbols have different codeword lengths, the receiver has no knowledge of the boundaries of the consecutive codewords in a bitstream. The receiver usually has to decode the bitstream sequentially, bit-by-bit, by tracing a Huffman tree until a leaf (i.e., a terminating node) is reached. Tracing a Huff-man tree node-by-node is time-consuming. Table look-ups were proposed to speed up the decoding process. Traditional table look-ups allow receivers to decode one symbol at a time. However, it does not provide adequate throughput for very high data rate applications, such as decoding HDTV. See (Obed Duardo, et al. “An HDTV Video Decoder IC for A TV Receivers”
IEEE Transactions on Consumer Electronics
. Vol. 43, number 3, pages 628-632, August, 1997 and S. F Chang and D. G. Messerschmitt. “Designing High-Throughput VLC Decoder Part I—Concurrent VLSI Architectures.”
IEEE Transactions on Circuits and systems for Video Technology
. Vol. 2, number 2, pages 187-196, June 1992). Given the proliferation of high data rate applications, the ability to decipher multiple-coded symbols in each clock cycle is desirable for clock speeds typically operated in the range of 15 to 100 Mhz.
SUMMARY OF THE INVENTION
Briefly and in general terms, in a preferred embodiment, the present invention provides a method to enhance the decoding rate of symbols from a coded bitstream. The coded bitstream includes one or more variable length codes (VLCs) produced by a Huffman code.
According to one aspect of the invention, an extended Huffman look-up table is constructed from an original Huffman look-up table wherein the extended Huffman look-up table contains row entries for decoding multiple variable length encoded symbols in a single clock cycle.
According to a second embodiment of the invention, a look-up table is constructed capable of decoding at least N Discrete Cosine Transform (DCT) coefficients in a single clock cycle so as to complete the decoding of an entire DCT block within 64/N+1 clock cycles.
The present invention advantageously improves the decoding rate (i.e., throughput) by extending an original Huffman table from the most frequent symbols while increasing the look-up table size a nominal amount.
A further advantage of the present invention, in accordance with the second embodiment, is that the decoding rate performance is guaranteed. This aspect is desirable from a hardware design perspective in that the method is adaptable to satisfy differing video hardware system requirements simply by adjusting the value of N (i.e., the number of coefficients to be decoded in a single cycle).
REFERENCES:
patent: 4853696 (1989-08-01), Mukherjee
patent: 5621405 (1997-04-01), Park
patent: 5696507 (1997-12-01), Nam
patent: 5825314 (1998-10-01), Kawauchi et al.
patent: 5973626 (1999-10-01), Berger et al.
Bai-Jue Shieh et al., A high-throughput memory based VLC decoder with code boundary prediction, IEEE 1051-8215/00, 1514-1521.*
Chang et al., Designing high throughput VLC decoder, IEEE 1051-8215/92, pp. 187-196.*
Durado et al. An HDTV video coder, IEEE 0098 3063/97, pp. 628-631.
Chiu Yi-Jen
Duardo Obed
Hingorani Rajesh
Wilford Paul Albin
Boudreau Leo
Sherali Ishrat
LandOfFree
Adaptive variable length decoding method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive variable length decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive variable length decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348951