Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
2000-06-21
2001-12-18
Wamsley, Patrick (Department: 2721)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
C341S067000
Reexamination Certificate
active
06331827
ABSTRACT:
BACKGROUND OF THE INVENTION
(a) Field of the Invention
The present invention relates to a Huffman-code decoder having a reduced circuit scale and, more particularly, to a technique for decoding a Huffman code data obtained by coding and compressing color still picture data based International Standard “JPEG” (Joint Photographic Experts Group) defined in ISO/IEC10198-1, or color motion picture data based on International Standard “MPEG1” (Motion Picture Image Coding Experts Group 1) defined in ISO/IEC11172-2, or International Standard “MPEG2” (Motion Picture Image Coding Experts Group II) defined in ISO/IEC13818-2, or International Standard “Digital Video (DV)” defined in IEC61834-2.
(b) Description of a Related Art
Picture data generally includes a large amount of information, and is processed by using a data compression technique. The data compression techniques available now include JPEG, MPEG1, MPEG2 and DV, wherein the picture data is compressed by using a series of Huffman codes as an international standard.
Each of the Huffman codes has a single bit (D
0
), two bits (D
0
, D
1
), three bits (D
0
, D
1
, D
2
), or sixteen bits (D
0
, D
1
. . . D
15
) depending on the original picture data, wherein bit D
0
is the most significant bit and bit D
15
is the least significant bit in the Huffman code having sixteen bits. Huffman codes having a specified number of bits (or specified code length) ranges between a maximum code (M
1
, M
2
. . . M
16
) and a minimum code for the specified code length.
Several techniques are proposed for reducing the circuit scale for the decoders used for decoding the Huffman codes to obtain decoded data.
FIG. 1
shows a conventional Huffman-code decoder, described in JP-A-6-276104. The Huffman-code decoder includes a plurality of discrete circuits
311
to
31
n each corresponding to one of Huffman codes and including a coding filter
301
, Huffman-code register
302
and a coincidence detector
303
. One of the discrete circuits
311
to
31
n responds to the input Huffman code to output a decoded address for the input Huffman code, whereby a decoded output is delivered from the Huffman table
320
based on the decoded address.
In the conventional Huffman-code decoder of
FIG. 1
, the number of discrete circuits
311
to
31
n provided for respective Huffman codes is large and thus increases the circuit scale of the Huffman-code decoder.
FIG. 2
shows another Huffman-code decoder described in JP-A-6-276394, including a code length detector
431
for detecting the code length of the input Huffman code and a code detector
432
for detecting a coded data among the coded data stored therein based on the code length supplied from the code length detector
431
. In the code length detector
431
, each of 8-bit comparator
411
, 9-bit comparator
412
, and 16-bit comparator
419
compares the input Huffman code in the compressed data against the maximum code M
8
, M
9
, or M
16
of the Huffman code having a corresponding code length. A priority encoder
410
detects the code length based on the results of comparison in the comparators
411
to
419
. In the coded data detector
432
, each 256-word RAM
421
to
429
receives corresponding eight bits among the whole bits of the input Huffman code as an address signal to output the stored coded data as an intermediate data. A data selector
420
selects one of the intermediate data output from the 256-word RAMs based on the code length supplied from the code length detector
431
.
In the Huffman-code decoder of
FIG. 2
, most 256-word RAMs for storing the decoded data have redundant memory cells wherein data are not stored due to less number of bits, which raises the capacity of the RAMs. This also raises the circuit scale of the decoder. In addition, since the code length detector
431
includes only 8-bit comparator
411
to 16-bit comparator
419
, the code length detection is separately conducted for first bit to seventh bits and then for eighth bit to sixteen bit for the input Huffman code, which detection consumes a large processing time.
FIG. 3
shows another conventional Huffman-code decoder, described in JP-A-7-303045. The Huffman-code decoder includes an address calculator
554
for outputting intermediate data, a code length detector
553
for outputting the code length of the input Huffman code, an address selector
552
for selecting one of the intermediate data and a memory
551
for storing decoded data in a plurality of memory cells. The address calculator
554
includes a plurality of value data storage sections
521
to
536
each for storing the minimum code for each code length and a corresponding number of bit adders
501
to
516
including 1-bit adder
501
, 2-bit adder, and 16-bit adder
516
, which output respective intermediate data. The address selector
552
selects one of the intermediate data based on the code length detected by the code length detector
553
, thereby outputting a decoded address, based on which the memory
551
outputs a decoded data.
In the Huffman-code decoder of
FIG. 3
, the address calculator
554
includes adders
501
to
516
each having a number of bits corresponding to the code length of the Huffman codes, and the code length detector
553
also has therein comparators each having a number of bits corresponding to the code length of the Huffman codes. This increases the circuit scale of the Huffman-code decoder.
SUMMARY OF THE INVENTION
In view of the above, it is an object of the present invention to provide a Huffman-code decoder having a reduced circuit scale and capable of decoding the Huffman code at a high speed.
The present invention provides a Huffman-code decoder including: a coded data memory for storing coded data for possible Huffman codes, the coded data having addresses defined by sequential numbers of the Huffman codes, a number of the possible Huffman codes being equal to or less than 2
N
, the possible Huffman codes having M bits at most; a maximum code data storage section including a plurality of memory cells each for storing a maximum code data; a value data storage section including a plurality of memories each for storing value data corresponding to minimum code among Huffman codes having a corresponding number of bits; a code length detector for detecting a code length of an input Huffman code by comparing the input Huffman code against the maximum code data; a first selection section for selecting all bits of the input Huffman codes having (N−1) bits or less and (n-N+1)th bit to n-th bit of the input Huffman code having N bits or more based on the code length detected by the code length detector, “n” being a natural number assuming N to M; a second selection section for selecting one of maximum code data, stored in the maximum code data storage section, based on the code length detected by the code length detector; and an address calculator for calculating an address based on the selected bits of the input Huffman code and the selected value data to specify the coded data in the coded data storage section based on the calculated address, each the value data corresponding to a remainder obtained by subtracting the address of a minimum code among Huffman codes having a corresponding number of bits in the coded data storage section from minimum code data.
The minimum code data corresponds to the minimum code among Huffman codes having (N−1) bits or less and corresponds to (n-N+1)th bit to n-th bit of a minimum code among Huffman codes having N bits or more.
In accordance with the Huffman-code decoder of the present invention, since the value data stored in the value data storage section has N bits or less, the capacity of the value data storage section is reduced compared to the conventional decoder.
The above and other objects, features and advantages of the present invention will be more apparent from the following description, referring to the accompanying drawings.
REFERENCES:
patent: 5801650 (1998-09-01), Nakayama
patent: 5805737 (1998-09-01), Abe
patent: 6-276394 (1994-03-01), None
patent: 6-2
McGuireWoods LLP
NEC Corporation
Wamsley Patrick
LandOfFree
Huffman decoder using two priority encoder to reduce circuit... 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 decoder using two priority encoder to reduce circuit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Huffman decoder using two priority encoder to reduce circuit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600580