Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
1999-06-30
2003-06-17
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Including details of decompression
C382S246000, C708S203000, C341S067000
Reexamination Certificate
active
06580828
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to decoding data and more specifically to decoding data which has been variable length encoded. In particular, the present invention provides new methods and apparatus for decoding Huffman encoded data using a central processing unit (CPU) more quickly and efficiently.
In most computer systems, a number of applications are simultaneously running on the same CPU while data is being compressed/decompressed. As video data is becoming a facet of the computer based communication systems and applications, the need for higher quality images with higher resolution increases. Faster compression/decompression, including encoding/decoding, is needed to lower the amount of delay a user will encounter while dealing with video data.
Huffman coding is one of the algorithms most widely used to compress video data. Huffman coding has been used in various image and video compression standards such as the standards specified by the Joint Photographic Experts Group (JPEG), Motion Picture Experts Group (MPEG), MPEG-II, H.261, H.263, and H.323. These standards are included herein by reference, in there entirety and for all purposes. Huffman coding is a lossless entropy coding technique. Huffman coding utilizes probability to select the shortest code word for the data that occur most frequently. For example, when encoding English text, “E” which is a very popular character in the English language can be represented by a 2-bit code word, whereas “A” which is not used as frequently can be represented by an 8-bit code word.
As a result, Huffman coding compresses data by assigning shorter code words to more frequently occurring data and longer code words to less frequently occurring data. The assigned code words can be maintained in a table which is then used by both recipients and senders. Further details regarding Huffman encoding can be found in “A Method for the Construction of Minimum Redundancy Codes,”
Proceedings of the IRE
, Vol. 40, No. 9, September 1952, pp. 1098-1101, by D. A. Huffman, which is incorporated herein by reference in its entirety and for all purposes.
Moreover, Huffman code words are constructed in such a way that no code word is the prefix of another code word. This assures the unambiguous decoding of each symbol from a bitstream of data despite the variable lengths of the codes. Additional description of the characteristics of Huffman codes can be found in Data Compression Book, M&T Books, 1996, by M. Nelson and J. L. Gailly, which is also incorporated herein by reference in its entirety and for all purposes. On pages 31-35, this reference proposes a decoding algorithm based on tree-tracing. This algorithm is, however, not suitable for fast decompression using most of the currently available microprocessors such as Intel® Pentium® family.
Accordingly, a technique is desirable wherein data can be compressed/decompressed and encoded/decoded more quickly and efficiently in a computer system sharing its CPU power.
SUMMARY OF THE INVENTION
The present invention provides improved speed performance and efficiency for decoding data by comparing, in parallel, a first plurality of code words of received data with respective values from a code length table. If the compared first plurality of code words are outside of a criterion, a second plurality of code words of received data are compared with respective values from the code length table. If one of the code words from one of the first and the second compared plurality of code words meets the criterion, it is determined which one of the code words from the first and the second compared plurality of code words has met the criterion. Once the code word meeting the criterion is determined, its symbol value is provided.
In one embodiment, a method is disclosed which further includes masking off the first and the second plurality of code words of the received data. The masking off action defines which portion of the received data is to be compared with the respective values from the code length table. The first plurality of code words may be, for example, 2, 3, 4, and 5 bits from the same starting point of a bitstream. If one of these code words is within a maximum and minimum code value for that length of code, it is presumably the variable length code being searched for and can be applied to the Huffman look-up table. The masking allows the selection of different bit lengths for this parallel comparison.
In another embodiment, an algorithm is disclosed which uses only one table look-up to index the Huffman code value. This minimizes the number of registers required and accelerates the indexing of Huffman code values which can be very valuable in many situations. The algorithm utilizes a table which needs to be calculated only once for each Huffman code table. The algorithm calculates the table values based on results of two other table look-ups.
The present invention is preferably implemented using a microprocessor with an extended multimedia capability. In particular, a microprocessor having built-in capability for performing graphics operations requiring single instruction multiple data (SIMD) operations on multiple pixels is adapted to use the SIMD instructions to perform the decoding operations of the present invention.
REFERENCES:
patent: 4823201 (1989-04-01), Simon et al.
patent: 5379070 (1995-01-01), Retter et al.
patent: 5572208 (1996-11-01), Wu
patent: 5652582 (1997-07-01), Truong et al.
patent: 5686965 (1997-11-01), Auld
patent: 5696507 (1997-12-01), Nam
patent: 5872965 (1999-02-01), Petrick
Nelson, Mark et al. “The Data Compression Book,” M&T Books, Second Edition, Copyright 1993 by Van Nostrand Reinhold, pp. 31-35.
Pennebaker, William B., et al. “JPEG: Still Image Data Compression Standard,” Van Nostrand Reinhold, 1996 by M&T Books, pp. 464-467.
Intel Manual, Chapter 1 “Introduction to the Intel Architecture MMX™ Technology,” Developer's Manual, Copyright Intel Corporation 1996, pp. 1-1 through 1-4.
Azarian Seyed
Logitech Europe S.A.
Mehta Bhavesh M.
Townsend and Townsend / and Crew LLP
LandOfFree
Fast decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3123546