Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
2002-02-22
2003-09-16
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
Reexamination Certificate
active
06621429
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Huffman decoding method and decoder, a Huffman decoding table, a method of preparing the table, and storage media storing respective programs for executing the methods.
2. Description of the Related Art
Huffman coding encodes symbols by assigning thereto respective codewords having lengths corresponding to probabilities of occurrence of the symbols to thereby minimize the average length of encoded symbols. Huffman coding is known as a typical method of entropy encoding (variable length encoding), and widely used e.g. in compression of multi-media data, such as image data and voice data.
An example of a conventional Huffman decoder will be described with reference to
FIGS. 6
to
8
. It is assumed here that input data encoded by using a Huffman coding table shown in
FIG. 6
are decoded. That is, data (symbol) “A” is assigned with a codeword “1”having a code length of 1 (bit), data “B” a codeword “00” having a code length of 2(bits), data “C” a codeword “010” having a code length of 3(bits), data “D” and “E”codewords “01111” and “01100” each having a code length of 5 (bits), data “F” a codeword “011101”, having a code length of 6 (bits), and data “G”, “H”, “I”, “J”, “K”, and “L” codewords “0111001”, “0111000”, “0110111”, “0110110”, “01101010”, and “0110100” each having a code length of 7, respectively.
FIG. 7
shows the construction of the conventional Huffman decoder.
In the figure, reference numeral
31
designates a codeword table storing codewords of the Huffman coding table shown in
FIG. 6
, reference numeral
32
designates a code length table storing code lengths associated with the respective codewords, and reference numeral
33
designates a data table storing decoded data associated with the respective codewords. Further, reference numerals
34
,
35
,
36
designate a counter for supplying a read address to the codeword table
31
, the code length table
32
, and the data table
33
, an input data-acquiring circuit for acquiring input data D having the number of bits determined based on a code length (represented by “length” in the figure) read out from the code length table
32
, from a stream of input data encoded by Huffman coding, and an agreement-detecting circuit for detecting agreement between a codeword read from the codeword table
31
and the input data D supplied from the input data-acquiring circuit
35
.
The flow of processing by the conventional Huffman decoder constructed as described above will be described with reference to. FIG.
8
.
First, in a step S
21
, the input data D retrieved by the input data-acquiring circuit
35
, the count n of the counter
34
(i.e. read address for the tables
31
to
33
) and code length data L are all set to an initial value 0. Then, the process proceeds to a step S
22
, wherein an address #n (n=0 immediately after the initialization) of the code length table
32
is accessed to read out a code length therefrom.
Then, the process proceeds to a step S
23
, wherein it is determined whether or not the code length read out agrees with the code length data L. In the case of n=0, the code length read out from the code length table
32
is 1 (length=1), so that there occurs disagreement between the code length (length=1) read out and the code length data L, which has been initialized to 0, and therefore, the process proceeds to a step S
24
, wherein the input data-acquiring circuit
35
acquires (length−L) bits (equal to 1 bit in the present case, since L has been initialized to 0) from a stream of input data. That is, the input data D is shifted leftward by the (length−L) bits, and the input data which is (length−L) bits long and has been acquired is added to the shifted input data to update the input data D. In the case of n=0, the original input data D has been initialized to 0, so that the updated input data D is set to data which is 1 bit long from the start position thereof. Then, the value of the code length data L is set to the code length (length=1).
After executing the step S
24
, or when the code length read out in the step S
22
agrees with the code length data L (YES to step S
23
), the process proceeds to a step S
25
, wherein a codeword having the address #n is read out from the codeword table
31
. Then, it is determined in a step S
26
whether or not the codeword read out agrees with the input data D. If the result shows the agreement between the codeword and the input data D, decoded data stored in the address #n of the data table
33
is read out from the data table
33
, followed by terminating the decoding of the Huffman encoded data. Then, to decode the next input data, the process starting with the step S
21
as described above is carried out again.
On the other hand, if the codeword read out and the input data D do not agree with each other, the program proceeds to a step S
28
, wherein the count adr of the counter
34
is incremented by 1, and then the process returns to the step S
22
, so as to repeat the process described above as to a new address (n+1).
Thus, by using the memory storing the Huffman coding table, input data encoded by Huffman coding can be decoded in a round-robin fashion.
It should be noted that there have been proposed various kinds of the Huffman decoding method and decoder other than the above-described one, including a method of using a memory with addresses having the maximum code length, a method of tracing a code tree for each bit, and a method of decoding in a parallel fashion by using a plurality of memories.
In the case of the Huffman decoding method using the Huffman coding table described above, all information of decoding data, code lengths, and codewords is necessary, which increases the required memory capacity of the Huffman coding table. Further, this method is a sequential search-based method which repeatedly carries out a determining process until the agreement between input data and a codeword occurs, and therefore, if data having a long code length is retrieved, the number of times of looking up the table becomes very large, which causes a low efficiency of the decoding process.
Further, in the case of the method using addresses having the maximum code length, it is possible to carry out decoding at a high speed, but it necessitates a very large memory capacity.
Also, in the case of the method of performing parallel processing in order to increase the processing speed, the size of a circuit of the decoder is increased.
SUMMARY OF THE INVENTION
It is a first object of the present invention to provide a Huffman decoding method and decoder which is capable of carrying out a decoding process at a high speed with a small memory capacity, and requires only a small-sized circuit, and a storage medium storing a program for executing the Huffman decoding method.
It is a second object of the present invention to provide a Huffman decoding table for use in the Huffman decoding method and decoder, and a method of preparing the Huffman decoding table, a storage medium storing a program for executing the method of preparing the Huffman decoding table.
To attain the first object, according to a first aspect of the invention, there is provided a Huffman decoding method of decoding input data encoded by a Huffman code, comprising the steps of preparing a table describing a binary tree corresponding to the Huffman code and having leaves each storing data, and carrying out a binary tree-based search of the table, based on the input data sequentially acquired by at least one bit to thereby decode the input data encoded by the Huffman code.
Preferably, the binary tree has first nodes having the leaves connected thereto, second nodes having no leaves connected thereto, and the table stores words corresponding to the leaves of the binary tree, and words corresponding to the second nodes having no leaves connected theretp. The table stores, as the words corresponding to the leaves of the binary tree, decoded data cor
Ishida Atsushi
Tsuchido Toshiaki
Pillsbury & Winthrop LLP
Yamaha Corporation
LandOfFree
Huffman decoding method and decoder, huffman decoding table,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Huffman decoding method and decoder, huffman decoding table,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Huffman decoding method and decoder, huffman decoding table,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3086526