Decoding method for a Huffman code

Details Decoding method for a Huffman code Decoding method for a Huffman code

2000-06-15

2002-06-11

Young, Brian (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

C341S079000, C340S398100

Reexamination Certificate

active

06404358

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to decoding, and, more particularly, to a decoding method and apparatus for a Huffman code.
BACKGROUND OF THE INVENTION
Huffman codes are commonly used in various applications such as, for example, in compression/decompression algorithms for digital, audio or video signals. In a Huffman code, each item of source data (symbol) is coded by a variable number of bits which is inversely proportional to a statistical frequency of use of the source data. The coded data is generally supplied by a continuous stream of bits without any separator element (control element) so as to increase the level of compression.
The source data is obtained from the corresponding coded data using special decoding tables. In particular, a look-up table (LUT) is used in which each row contains a flag indicating whether an index for access to the row represents an item of coded data. If this is the case, the row contains a field which specifies the associated source data. The bits of the coded data received in sequence are used to form the index of the decoding table, until a row, the flag of which indicates an item of coded data, is reached. The corresponding source data is obtained from this row.
If Max indicates the maximum number of bits of the coded data, the decoding table must therefore have a number of rows substantially equal to 2
Max
. This involves an extremely large amount of memory, in particular, in the case where there are several alternative decoding tables, which are selected according to the various statistical distribution of the source data.
Another known decoding method groups together the possible values of the coded data in clusters, each including a number of bits ranging between two consecutive multiples of a predefined value. Each cluster has associated with it, for each value of the maximum number of bits added to the preceding cluster, a row of the decoding table which contains a coded data flag. If the flag indicates an item of coded data, the row contains two fields which specify the associated source data and its length. In the opposite case, the two fields specify an address of the next cluster and its maximum length.
The maximum number of bits of the first cluster is used to access a row of the decoding table. The decoding method repeats—until it reaches a row, the flag of which indicates an item of coded data—the steps for selecting the bits of the next cluster (the number of which is obtained from the current row) and accessing the row corresponding to their value (using the address obtained from the current row). The source data and its actual length are obtained from the fields of the row thus obtained. In this way, it is possible to reduce substantially the amount of memory occupied by the decoding table.
A drawback of the known approach described above is that the decoding method requires a lot of feedback cycles. This makes the decoding method somewhat complex and slow. Moreover, the amount of memory occupied by the decoding table is, in any case, not insignificant.
SUMMARY OF THE INVENTION
An object of the present invention is to overcome the abovementioned drawbacks. This and other objects, features and advantages are provided by a decoding method for a Huffman code, comprising the steps of receiving a continuous stream of coded data each including a variable number of bits at least equal to a minimum number, and obtaining from each item of coded data a corresponding item of source data. A decoding memory structure is provided which comprises, for each value of an initial group of bits comprising a number not greater than the minimum number and for each value of each further bit, a record formed by a flag having an end-of-decoding value or a not end-of-decoding value and a field indicating the source data or the records associated with the values of an immediately following bit depending on whether the flag has, respectively, the end value or the not end value.
The method further includes accessing the record corresponding to the value of the initial group, and repeating—until a record having the flag with the end value is reached—the step of accessing the record corresponding to the value of the immediately following bit using the field of the current record. The source data is obtained from the field of the current record.
Moreover, a corresponding processor program, program product and processing system are provided for decoding a Huffman code.


REFERENCES:
patent: 4475174 (1984-10-01), Kanayama
patent: 5216423 (1993-06-01), Mukherjee
patent: 5801648 (1998-09-01), Satoh et al.
patent: 5973626 (1999-10-01), Berger et al.
patent: 6300888 (2001-10-01), Chen et al.
patent: 0593046 (1993-10-01), None
patent: 0683569 (1995-05-01), None
Cain, R.G. “Unified Encoding and Decoding of Huffman Codes” IBM Technical Disclosure Bulletin. vol. 16, No. 11, Document No. XP-002126809, Apr. 1974, pp. 3678-3681.

Affiliated with

Also associated with

Rating

Decoding method for a Huffman code 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 method for a Huffman code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding method for a Huffman code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2949314