Decoding device

Details Decoding device Decoding device

2000-03-30

2001-10-02

Lam, Tuan T. (Department: 2816)

Coded data generation or conversion

Digital code to digital code converters

To or from number of pulses

Reexamination Certificate

active

06297754

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a decoding device for decoding a data stream, and more particularly to a decoding device for decoding a data stream containing Huffman-encoded data.
2. Description of the Related Art
Recently, decoding devices for decoding a Huffman-encoded bit stream (data stream) have been widely developed. Decoding methods used in such decoding devices are generally categorized into two types. One type focuses on saving memory. The other type focuses on increasing decoding speed. An encoding method will be initially described before describing such decoding methods.
FIG. 11
shows an example of a Huffman encoding book
1100
used in Huffman encoding. The left column
1101
of the Huffman encoding book
1100
indicates input values to be Huffman-encoded. In the example shown in
FIG. 11
, the input values range from 0 through 63. The middle column
1102
of the Huffman encoding book
1100
indicates Huffman codes corresponding to the respective input values. The right column
1103
of the Huffman encoding book
1100
indicates a code length corresponding to the respective Huffman codes. In Huffman encoding, the higher the frequency of occurrence of an input value, the shorter the Huffman code which is assigned to the input value. Conversely, the lower the frequency of occurrence of an input value, the longer the Huffman code which is assigned to the input value.
For example, the first row
1104
of the Huffman encoding book
1100
indicates that a Huffman code (01110) is assigned to an input value 0, and the code length of the Huffman code is 5 bits. An encoding device receives and encodes an input value 0 and outputs the resulting Huffman code (01110). The encoding device does not need to output information indicating the code length of the Huffman code along with the Huffman code. This is because any code which has the same digit sequence beginning from the leftmost digit of a Huffman code (01110) but is shorter than the Huffman code (01110) cannot be included in the Huffman encoding book
1100
. All the other Huffman codes which have a code length of five or more do not contain the Huffman code (01110) as a digit sequence beginning with the leftmost digit of the other Huffman codes. Accordingly, when a decoding device decodes the Huffman code (01110), the decoding device does not need information specifically indicating that the code length of the Huffman code (01110) is 5 bits. Thus, a Huffman code (01110) itself can include information indicating which input value (0) the Huffman code corresponds to and information indicating the code length (5) of the Huffman code.
For that reason, Huffman codes can be generated in a contiguous way to produce a bit stream which is then output from the encoding device.
Hereinafter, a conventional decoding method focusing on saving memory will be described.
FIG. 12
shows a decoding table
1200
used for decoding data encoded with the Huffman encoding book
1100
shown in FIG.
11
. The decoding table
1200
is obtained by rearranging the rows of the Huffman encoding book
1100
shown in
FIG. 11
in order of the code length of the Huffman code from the shortest. The left column
1102
A of the decoding table
1200
indicates Huffman codes. The middle column
1103
A indicates the code length of the Huffman codes. The right column
1201
indicates the results of decoding the Huffman codes. As is seen from
FIG. 12
, a Huffman code having a code length of three bits (000) on the first row
1202
is the shortest Huffman code. The result from decoding the Huffman code (000) is “9” which corresponds to the tenth row
1105
(input value “9”) of the Huffman encoding book
1100
shown in FIG.
11
.
As is also seen from
FIG. 12
, a Huffman code (1111111111) with 10 bits on the lowest row
1203
is one of the longest Huffman codes. The result from decoding the Huffman code (1111111111) is “63” which corresponds to the 64th row
1106
(input value “63”) of the Huffman encoding book
1100
shown in FIG.
11
.
Huffman decoding in a decoding device using the decoding table
1200
will be described below.
The first row
1202
(the uppermost row) of the decoding table
1200
indicates that the code length is three. Based on this code length, a first three bits are read out of a bit stream. The decoding device determines whether the first three bits of data of the bit stream match the Huffman code (000) on the first row
1202
.
If the matching is successful (i.e., a match is found), the decoding device outputs “9” as the result of the decoding, and shifts a reading position in the bit stream by three bits. One Huffman-decoding operation is thus finished.
If the matching is not successful, a next row
1204
of the decoding table
1200
is considered. The second row
1204
has a code length of four. Accordingly, an additional one bit (1=4−3) next to the three bits which already have been read out is read out of the bit stream.
It is then determined whether the four bit data thus read matches a Huffman code (0010) on the second row
1204
.
If the matching is successful, “17” is output as the result of the decoding. The reading position of the bit stream is shifted by one bit. One Huffman-decoding operation is thus finished.
If the matching is not successful, a next row
1205
of the decoding table
1200
is looked up. The third row
1205
has a code length of four. Accordingly, no new bit is read out of the bit stream. It is then determined whether the four bit data thus currently read matches the Huffman code (0011) on the third row
1205
.
In this way, the matching procedure is repeated until data which is sequentially read out of the bit stream matches any of the Huffman codes contained in the decoding table
1200
. When the decoding device finds a row having a Huffman code matching the data, the decoding device outputs the value on the right column of the row as the result of the decoding operation.
The decoding table used in the above-described decoding method is very small in size. This is because such a decoding table only needs the same number of rows as that of input values (0 to 63). In the decoding method, however, the decoding table is accessed many times in the matching procedure until a matching Huffman code is found. This requires considerable processing time.
Next, a conventional decoding method focusing on increasing decoding speed will be described below.
FIG. 13
shows a decoding table
1300
used in decoding data which has been encoded using the Huffman encoding book
1100
shown in FIG.
11
. An example of the decoding method represented in
FIG. 13
uses addresses having a ten-bit width. The bit width (10 bits) of the addresses corresponds to the maximum code length (10 bits) of the Huffman codes in the Huffman encoding book
1100
shown in FIG.
11
.
A decoding device reads 10-bit data out of a bit stream and accesses the decoding table
1300
using the 10-bit data as an address. In the decoding table
1300
, an area
1301
including addresses (0000000000) through (0001111111) describes that a code length is three and the result of the decoding operation is “9”. The 10-bit data in which the first three bits are a Huffman code (000) is necessarily among the addresses (0000000000) through (0001111111). The Huffman code (000) corresponds to the value “9”. In this case, the decoding device outputs “9” as the result of the decoding corresponding to the first three bits (000) based on the decoding table
1300
shown in FIG.
13
. The area
1301
indicates that the code length is three. Accordingly, the decoding device shifts a reading position by three bits and reads 10-bit data from the reading position. The decoding table
1300
shown in
FIG. 13
is accessed using the 10-bit data as an access. Thus, the next Huffman decoding operation is performed.
The above-described decoding method can achieve high speed. Each Huffman decoding operation is finished by one access to the decoding table. However, the decoding method focusing on increasing decoding speed r

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2570416