Encoding/decoding device

Details Encoding/decoding device Encoding/decoding device

1998-09-09

2002-06-18

Tran, Phuoc (Department: 2721)

Image analysis

Image compression or coding

Lossless compression

C382S233000

Reexamination Certificate

active

06408102

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a device for encoding and/or decoding of a Huffman code which is a variable-length code.
2. Related Background Art
Compression technologies for the digital signals are showing remarkable progresses in recent years, and methods proposed by JPEG (Joint Photographic Exterts Group) and MPEG (Moving Picture Exterts Group) are becoming accepted as world-wide standards for compressing digitized still and moving image signals.
In these compressing methods, the image signal is at first orthogonally transformed by DCT (discrete cosine transformation), then the amount of information is reduced by eliminating the signal components of the visually inconspicuous portions in thus transformed signal, and the information is further compressed by Huffman encoding.
In the Huffman encoding, the codes of variable length are assigned according to the frequency of appearance of the codes. The amount of information can be compressed by the assignment of a code of a shorter bit length to the code of a higher frequency of appearance.
In the decoding of thus encoded Huffman codes with a table, the memory capacity required for the table inversely proportional to the speed of decoding. Consequently there can be conceived two opposite approaches which are:
a) a method of reducing the memory capacity for the table, though the process speed is low; and
b) a method of increasing the process speed though a larger memory capacity is required for the table.
An extreme case of the method (a) consists of decoding of 1 bit in each cycle, requiring several cycles for decoding a Huffman code. Such decoding method is cited as a conventional method in the Japanese Patent Laid-open Application No. 57-55668. On the other hand, an extreme case of the method (b) decodes a Huffman code in a cycle.
There can naturally be conceived other intermediate methods between these extreme cases, such as methods for decoding two or more bits in a cycle.
In all these conventional methods, the information of the Huffman code to be decoded is supplied, without conversion to another information, either directly into the table or a part of such information is supplied, in combination with information obtained by previous decoding, into the table.
FIG. 1
shows a conventional decoding device for decoding a Huffman code in a cycle, designed for decoding a Huffman code of a maximum code length of 16 bits into a fixed-length code of 8 bits.
In
FIG. 1
, there are shown a terminal
101
for entering the Huffman-encoded data, and a buffer
102
for temporarily storing the data. Since Huffman code is a variable-length code, the input data rate cannot be constant if the output data rate at the decoding is maintained constant, so that the above-mentioned buffer is required.
There are also provided an unpacking circuit
103
for connecting the data entered with a unit of m bits and obtaining the leading 16 bits after the removal of the already decoded data; a decoding table
104
for decoding a Huffman code in said 16-bits data; a terminal
105
for outputting the decoded fixed-length code (8 bits); and a 4-bits signal
106
indicating the bit length of the decoded Huffman code.
Said 4-bits signal
106
may represent the bit length itself or the bit length minus one, and
FIG. 1
shows the latter case. A maximum code length of 16 bits requires 5 bits for direct representation, but, as a code length of 0 bit does not exist, a representation with 4 bits is made possible by indicating (code length −1), namely by representing the code length of 1 bit with “0000”. However, there is no difference between the two methods if the maximum code length is not an exponent of 2. The signal
106
is supplied to the above-mentioned unpacking circuit
103
, for eliminating the decoded data.
This example required the memory of a large capacity, as the decoding table
104
requires 64 k×12 bits or 96 kBytes.
Then,
FIG. 2
shows the configuration in which the above-explained conventional example is applied to a decoding device for the JPEG codes. Also in case the JPEG codes, a Huffman code of a maximum code length of 16 bits is decoded into a fixed-length code of 8 bits (NNNN signal of 4 bits and SSSS signal of 4 bits), but additional bits are inserted between the Huffman codes and have to be removed at the decoding.
If the additional bits have a maximum bit length of 10 bits, the signal released from the unpacking circuit
200
shown in
FIG. 2
becomes 26 bits. Among these 26 bits, the leading 16 bits are supplied to the decoding table
104
and are converted, as already explained with reference to
FIG. 1
, into a fixed-length code of 8 bits and code-length information
106
of 4 bits. On the other hand, the signal of 26 bits is also supplied to a shifter
201
for removal of the decoded Huffman code based on the code-length information (said removal being achieved by shifting said signal of 26 bits by said code length), and the leading 10 bits are supplied to a terminal
202
. All said 10 bits do not constitute the signal of additional bits, but only the bits of an upper rank indicated by the SSSS signal output from the decoding table constitute said additional bits.
Thus, after the decoding of a Huffman code and before the decoding of a next Huffman code, it is required, in the configuration shown in
FIG. 1
, to remove the bits of the already decoded Huffman code by the unpacking circuit, but, in case of
FIG. 2
, to remove also the bits of the additional signal.
For this reason, the signal
106
indicating the code length of the Huffman code and a signal
203
(SSSS signal) indicating the bit length of the additional bits are added in an adder
204
, and the result of the addition is supplied to the unpacking circuit
200
for removing the Huffman code and the additional bits in each cycle.
In the conventional example explained above, the high-speed decoding of the Huffman codes requires a large memory capacity for the decoding table, leading to the following drawbacks:
1) In forming the decoding device into an integrated circuit, the chip area becomes larger and requires a higher cost;
2) A long time is required for the rewriting of the decoding table; and
3) As the amount of information in the decoding table is large, it is not possible to effect optimum Huffman encoding for each information (for example image information) to be compressed. If such optimum encoding is conducted, the decreased information by compression has to be associated, for each image, with information on the decoding table, and such optimum encoding becomes meaningless because the amount of such associated information is quite large.
SUMMARY OF THE INVENTION
The object of the present invention is to reduce the memory capacity required for the decoding table, as such reduction of the memory capacity resolves all three drawbacks mentioned above.
The above-mentioned object can be attained, according to an embodiment of the present invention, by a Huffman encode/decoding device comprising means for comparing a Huffman code to be decoded with plural boundary values; means for identifying the bit length of said Huffman code from the result of comparison by the comparing means; means for determining the difference between the lower limit boundary value at the bit length and said Huffman code; and means for adding the difference to a code number corresponding to the boundary value, wherein the code number of said Huffman code is determined by calculation with the above-mentioned means, and the Huffman code is with a table for converting the code number to the original fixed-length code.


REFERENCES:
patent: 3701111 (1972-10-01), Cocke et al.
patent: 4475174 (1984-10-01), Kanayama
patent: 4516246 (1985-05-01), Kenemuth
patent: 4700175 (1987-10-01), Bledsoe
patent: 4899149 (1990-02-01), Kahan
patent: 5377266 (1994-12-01), Katta et al.
patent: 5761345 (1998-06-01), Saito et al.
patent: 5801840 (1998-09-01), Sakai
patent: 5844611 (1998-12-01), Hamano et al.
patent: 57-055668 (1983-04-01), None

Affiliated with

Also associated with

Rating

Encoding/decoding device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Encoding/decoding device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding/decoding device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2907508