Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2002-12-09
2004-07-20
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
Reexamination Certificate
active
06765513
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to decompression techniques, and more specifically to a method and apparatus for decoding bit streams compressed with compression techniques (such as Huffman Coding) employing variable length codes.
2. Related Art
Compression techniques are often used to generate smaller-size representations of bit streams. In general, a compression technique is applied on a source bit stream to generate a compressed bit stream, with the compressed bit stream having fewer bits than the source bit stream. Such compression typically reduces storage requirements and/or bandwidth requirements, as is well known in the relevant arts.
Several compression techniques use compression tables representing a mapping of a source code to a compressed code. The compressed code is typically shorter compared to the source code (at least for frequently occurring source code). In operation, a source bit stream is divided into a sequence of source codes, and each source code is mapped to the corresponding compressed code using the compression table. The resulting sequence of compressed codes represent a compressed bit stream corresponding to the source bit stream.
A compression technique may employ variable length (not a fixed number of bits) codes (either source code or compressed code). For example, Huffman coding techniques generally use variable length portions for both the source codes and compressed codes. Huffman techniques are described in further detail in a book entitled, “The Data Compression Book” by Mark Nelson and Jean-loup Gailly, M&T Books, New York, N.Y. 1995, ISBN 1-55851-434-1, which is incorporated in its entirety herewith. Thus, compressed bit streams may be generated using such compression techniques.
It is generally desirable to recover (or generate again) a source stream corresponding to a compressed stream, and the corresponding processing is commonly referred to as ‘decoding’. For example, a compressed stream may be received on a network connection, and it may be necessary to decode the compressed stream to generate the corresponding source stream. The source stream usually lends to further additional processing (e.g., playing a song represented by the source stream).
Decoding operations may need to be implemented while meeting several requirements such as high throughput rate (“speed”) of decoding, minimization of memory requirements, etc. Accordingly, what is needed is a method and apparatus for decoding bit streams compressed with compression techniques employing variable length codes, while meeting one or more of such requirements.
SUMMARY OF THE INVENTION
The present invention enables decompression (decoding) of a compressed bit stream generated from a source bit stream using Huffman-coding type (which use variable length compressed and source codes) compression techniques. In an embodiment, a maximum length (M) of compressed codes desired to be decoded in a single lookup of a table is first determined.
A table of 2
M
rows is then generated, with each row indicating whether a corresponding M-bit combination (viewed from the first bit) contains a compression code (in which case the end of the compression code is present in that M-bit combination), and a corresponding source code. The length of the compression code may also be stored. In one implementation, the table (a data structure) is stored on a computer readable medium, from which a processor can retrieve and use the rows to decode a compressed bit stream.
To decode a compressed bit stream, the first M-bits of the compressed bit stream are set to a present portion. One of the 2
M
rows with the M-bit combination equaling the present portion is selected as a matching row. If the matching row indicates that the M-bit combination contains a compressed code, at least a portion of the present portion is decoded as equaling the source code in the matching row. If the number of bits in the corresponding compression code is less than M, the corresponding fewer number of bits are deemed to be un-decoded and included in the next portion sought to be decoded.
In case a row indicates that the M-bit combination does not contain a compressed code (i.e., the end of a compressed code is not in the combination), additional bits are used for continuing decoding operation. In an embodiment, a designer may specify a value (N) and N more bits of the compressed bit stream are used for decoding. Accordingly, 2
N
additional rows are included for all possible combinations of the N bit values. Each additional row may contain similar content as with the 2
M
rows noted above.
The M-bit partially matching (or forming a part of) a compressed code specify which specific 2
N
need to be searched. In an implementation, all of the 2
M
rows and 2
N
rows (potentially multiple sets thereof) are provided in the form of a single table and an entry in the 2
M
rows specifies which 2
N
rows to search in the form of an offset (from the entry). The offset is used to select the specific 2
N
rows to use for further decoding.
Thus, the 2
N
rows enable a decoding operation if the end of a compressed code is present within (M+N) bits. N more bits may be used if a match is not detected in the (M+N) bits. The decoding may thus continue until the entire compressed bit stream is decoded.
Further features and advantages of the invention, as well as the structure and operation of various embodiments of the invention, are described in detail below with reference to the accompanying drawings. In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.
REFERENCES:
patent: 5226082 (1993-07-01), Kustka
patent: 5245338 (1993-09-01), Sun
patent: 5831557 (1998-11-01), Handley
patent: 6043765 (2000-03-01), Twardowski
patent: 6580377 (2003-06-01), Du et al.
Brady III W. James
Marshall, Jr. Robert D.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
Williams Howard L.
LandOfFree
Decoding bit streams compressed with compression techniques... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding bit streams compressed with compression techniques..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding bit streams compressed with compression techniques... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3246643