Coded data generation or conversion – Digital code to digital code converters – To or from number of pulses
Reexamination Certificate
2003-02-06
2004-05-25
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from number of pulses
C341S106000
Reexamination Certificate
active
06741191
ABSTRACT:
BACKGROUND OF THE INVENTION
This application claims the priority of Korean Patent Application No. 2002-10981, filed Feb. 28, 2002, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
1. Field of the Invention
The present invention relates to an improved Huffman decoding method and apparatus, and more particularly, to a Huffman decoding method and apparatus that performs Huffman decoding by constructing an efficient one-dimensional look-up table generated from a binary tree, and by using a numerical method for improving processing efficiency.
2. Description of the Related Art
Because of the unique characteristics of the Huffman code, the related art Huffman decoding method using a binary tree is considered a very efficient method based on maximum search time, average search time, and search time deviation. However, according to the search method based on the related art binary tree, to generate a data structure for searching, a complicated process is required for constructing a binary tree based on a linked list. Also, comparison and branch statements for transition between nodes in a binary tree search slow the processing flow of the operations of a related art processor, thereby decreasing the processing speed of a Huffman decoder.
The structure and operation of the prior art Huffman decoding apparatus and method will now be explained referring to accompanying drawings.
FIG. 1
is a schematic block diagram of the related art Huffman decoding apparatus. The apparatus comprises an input buffer
110
that receives an encoded bit stream, a search engine
120
, a Huffman look-up table
130
, and an output buffer
140
that outputs decoded Huffman data.
FIG. 2
is a flowchart of the prior art Huffman decoding method of a Huffman decoder based on a related art conditional branch statement. This method is performed in the apparatus shown in
FIG. 1
, and is described in greater detail below.
FIG. 3
is a diagram showing a binary Huffman tree structure according to the related art method. Nodes
310
,
322
,
330
,
332
,
342
,
344
, and
356
are internal nodes that branch to next nodes. Nodes
320
,
340
,
346
,
350
,
352
,
354
,
360
, and
362
are terminal nodes that have return values to be actually sent back.
Table 1 is a codebook of the binary Huffman tree shown in FIG.
3
.
TABLE 1
Codeword
Value
0
60
100
59
1010
61
1011
58
1100
62
11010
57
11011
63
111
4
FIGS. 4
a
and
4
b
are diagrams showing the memory structure of a Huffman table according to the related art binary tree Huffman decoding method. As shown in
FIGS. 4
a
and
4
b
, the prior art Huffman table uses 3 memory spaces. As shown in
FIG. 4
a
, for an internal node, a null value is stored in the middle memory space among the allocated 3 memory spaces, the address of a left-hand node of the children nodes is stored in the left-hand memory space, and the address of a right-hand node of the children nodes is stored in the right-hand memory space. Also as shown in
FIG. 4
b
, for a terminal node, an internal value of the node, that is, a return value to be sent back, is stored in the middle memory space of the allocated 3 memory spaces, and null values are stored in the left-hand and right-hand memory spaces.
Referring to
FIGS. 3 through 5
, and based on the flowchart shown in
FIG. 2
, the decoding method of a Huffman decoder using the Huffman table of the prior art binary tree structure will be explained below.
In step S
210
, a first step of decoding, based on the codeword of an encoded bit stream input to the Huffman decoder, an entry corresponding to a root node of the Huffman tree shown in
FIG. 3
(i.e., the internal node
310
) is accessed. In step S
220
, a comparison and branch statement, it is determined whether the node corresponding to the entry accessed in the step S
210
is an internal node or a terminal node.
In step S
230
, if it is determined in step S
220
that the node corresponding to the accessed entry is a terminal node, a value stored in the middle memory space among the 3 memory spaces allocated to the terminal node is output as a decoded codeword value to be sent back. Alternatively, in step S
240
, if it is determined in step S
220
that the node corresponding to the accessed entry is an internal node, it is determined whether the value of 1 bit input from the bit stream is ‘0’ or ‘1’. If the value is ‘0’, step S
250
is performed. If the value is ‘1’, step S
260
is performed.
In step S
250
, an entry corresponding to an address stored in the left-hand memory space among the 3 memory spaces allocated to the current node is accessed, and step S
220
is then performed. Alternatively, in step S
260
, an entry corresponding to an address stored in the right-hand memory space among the 3 memory spaces allocated to the current node is accessed, and step S
220
is then performed.
Referring to
FIGS. 2 and 5
, a process for decoding an input bit stream ‘1110100 . . . ’, which is encoded according to the prior art Huffman decoding method described above, will now be explained.
In step S
210
, an entry corresponding to the root address of the Huffman binary tree (the entry which corresponds to address ‘1’ of the Huffman table shown in
FIG. 5
) is accessed.
In step S
220
, it is determined whether the node of the accessed entry is an internal node or a terminal node. Referring to
FIG. 5
, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address ‘1’ is ‘NULL’, ‘4’ is stored in the left-hand memory space and ‘7’ is stored in the right-hand memory space. Accordingly, in step S
220
it is determined that the node corresponding to the address ‘1’ is an internal node shown in
FIG. 4
a
, and accordingly, step S
240
is performed.
In step S
240
, the first bit ‘1’ of the first encoded codeword of the input bit stream ‘
1
110100’ is input. Because the input bit (new digit( )) is ‘1’, step S
260
is performed.
In step S
260
, an entry corresponding to address ‘7’ stored in the right-hand address ‘2’ of the current address ‘1’, that is, in the right-hand memory space of the current node, is accessed, and step S
220
is performed.
In the step
220
, it is determined whether the node corresponding to the address ‘7’ of the Huffman table is an internal node or a terminal node. Referring to
FIG. 5
, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address ‘7’ is ‘NULL’, ‘10’ is stored in the left-hand memory space and ‘13’ is stored in the right-hand memory space. Accordingly, in step S
220
it is determined that the node corresponding to the address ‘7’ is an internal node shown in
FIG. 4
a
, and step S
240
is performed.
In step S
240
, the second bit ‘1’ of the first encoded codeword of the input bit stream ‘1
1
10100’ is input. Because the input bit (new digit( )) is ‘1’, step S
260
is performed.
In step S
260
, an entry corresponding to address ‘13’ stored in the right-hand address ‘8’ of the current address ‘7’, that is, in the right-hand memory space of the current node, is accessed, and step S
220
is performed.
In step S
220
, it is determined whether the node corresponding to the address ‘13’ of the Huffman table is an internal node or a terminal node. Referring to
FIG. 5
, the value stored in the middle memory space of the 3 memory spaces of the node corresponding to address ‘13’ is ‘NULL’, ‘22’ is stored in the left-hand memory space and ‘25’ is stored in the right-hand memory space. Accordingly, in step S
220
it is determined that the node corresponding to the address ‘13’ is an internal node shown in
FIG. 4
a
, and step S
240
is performed.
In step S
240
, the third bit ‘1’ of the first encoded codeword of the input bit stream ‘11
1
0100’ is input. Because the input bit (new digit( )) is ‘1’, step S
260
is performed.
In step S
260
, an entry corresponding to address ‘25’ stored in the right-hand address ‘14’ of the current address ‘13’, that is, in the right-hand memory space of the current node, is accessed, and step S
220
Jang Heung-yeop
Jang Tae-kyu
Jeong Jong-hoon
LandOfFree
Huffman decoding method and apparatus 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 apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Huffman decoding method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225363