Abstract:
An improved Huffman decoding method and an apparatus thereof are provided. The method includes (a) obtaining index information from a first bit of a codeword formed with bits of a part of a received encoded bit stream, and accessing an entry of the look-up table corresponding to the obtained index information, and (b) determining a type of the entry based on an internal value of the accessed entry.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    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.  
           [0002]    1. Field of the Invention  
           [0003]    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.  
           [0004]    2. Description of the Related Art  
           [0005]    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.  
           [0006]    The structure and operation of the prior art Huffman decoding apparatus and method will now be explained referring to accompanying drawings.  
           [0007]    [0007]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.  
           [0008]    [0008]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.  
           [0009]    [0009]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.  
           [0010]    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                      
 
           [0011]    [0011]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.  
           [0012]    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.  
           [0013]    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.  
           [0014]    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.  
           [0015]    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.  
           [0016]    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.  
           [0017]    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.  
           [0018]    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.  
           [0019]    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.  
           [0020]    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.  
           [0021]    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.  
           [0022]    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.  
           [0023]    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.  
           [0024]    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.  
           [0025]    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.  
           [0026]    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  is performed.  
           [0027]    In step S 220 , it is determined whether the node corresponding to the address ‘25’ 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 ‘25’ is ‘4’, ‘NULL’ is stored in the left-hand memory space and ‘NULL’ is stored in the right-hand memory space. Accordingly, in step S 220  it is determined that the node corresponding to the address ‘25’ is a terminal node shown in FIG. 4 a , and step S 230  is performed.  
           [0028]    In the step  230 , the value ‘4’ stored in the middle memory space among the 3 memory spaces allocated to the node corresponding to the address ‘25’ is output as a decoded codeword value.  
           [0029]    Accordingly, the decoded codeword ‘4’ corresponding to the first codeword ‘111’ of the input bit stream ‘ 111 0100’ is obtained, and decoding of the second codeword of the bit stream ‘1110100’ is performed.  
           [0030]    In the same manner as in the process for obtaining the decoded codeword value ‘4’, in step S 210  as the first step of the decoding, an entry corresponding to address ‘1’ of the Huffman table, that is, the root address of the Huffman binary tree, is accessed and then step S 220  is performed.  
           [0031]    In step S 220 , it is determined whether the accessed node corresponding to the address ‘1’ of the Huffman table is an internal node or a terminal node. 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 the step  220  it is determined that the node corresponding to the address ‘1’ is an internal node shown in FIG. 4 a , and step S 240  is performed.  
           [0032]    In step S 240 , the first bit ‘0’ of the second codeword of the input bit stream ‘111 0 100’ is input. Because the input bit (new digit( )) is ‘0’, step S 250  is performed.  
           [0033]    In step S 250 , an entry corresponding to the address ‘4’ stored in the left-hand address ‘0’ of the current address ‘1’, that is, the left-hand memory space of the current node, is accessed and step S 220  is performed.  
           [0034]    In step S 220 , it is determined whether the node corresponding to the address ‘4’ 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 ‘4’ is ‘60’, ‘NULL’ is stored in the left-hand memory space and ‘NULL’ is stored in the right-hand memory space. Accordingly, in step S 220  it is determined that the node corresponding to the address ‘4’ is a terminal node shown in FIG. 4 a , and step S 230  is performed.  
           [0035]    In step S 230 , the value ‘60’ stored in the middle memory space among the 3 memory spaces allocated to the node corresponding to the address ‘4’ is output as a decoded codeword value corresponding to the second codeword ‘0’ of the bit stream ‘1110100’.  
           [0036]    In this manner, the decoded codeword value ‘59’ corresponding to the third codeword ‘100’ of the encoded bit stream ‘1110100’ input to the Huffman decoder is output. By doing so, decoded codeword values ‘4, 60, 59, . . . ’ corresponding to the bit stream ‘1110100 . . . ’ are obtained.  
           [0037]    The related art has various problems and disadvantages. For example, but not by way of limitation, in the related art Huffman decoding method based on a binary tree, a complicated process for generating a binary tree based on a linked list should be performed to generate a data structure needed for searching. In particular, comparison and branch statements for transition between nodes in a binary tree search reduces the processing flow of the operations of a processor such that the efficiency of the operational speed decreases. Also, since each node uses 3 memory spaces in the look-up table according to the related art Huffman decoding method, memory spaces are excessively consumed.  
         SUMMARY OF THE INVENTION  
         [0038]    The present invention provides an improved Huffman decoding method by which the related art ‘comparison and branch’ command that decreases processing efficiency in the prior Huffman decoding process can be omitted so that the operational speed of a Huffman decoder can increase, and required memory resources can decrease.  
           [0039]    The present invention also provides an improved Huffman decoding system which performs the improved Huffman decoding method by which the related art ‘comparison and branch’ command that decreases processing efficiency in the prior Huffman decoding process can be omitted, so that the operational speed of a Huffman decoder can increase, and required memory resources can decrease.  
           [0040]    According to an aspect of the present invention, there is provided a decoding method for decoding an encoded bit stream using a look-up table comprising: (a) obtaining index information from a first bit of a codeword formed with bits of a part of the received encoded bit stream, and accessing an entry of the look-up table corresponding to the obtained index information; and (b) determining a type of the entry based on an internal value of the accessed entry.  
           [0041]    It is preferable that in step (b) it is determined whether the entry corresponds to an internal node or a terminal node, according to the sign of the internal value of the accessed entry.  
           [0042]    It is preferable that the decoding method further comprises: (c) when it is determined in step (b) that the accessed entry corresponds to an internal node, calculating an index value of an entry which will be accessed next, based on an index value of the current entry, the internal value of the accessed entry, and the second bit value of the codeword.  
           [0043]    According to another aspect of the present invention, there is provided a decoding apparatus for decoding an encoded bit stream according to a binary tree search, comprising: a processor which decodes the encoded bit stream; and a memory which is connected to the processor and stores a look-up table related to the decoding, wherein the look-up table has entries which correspond to respective nodes of the binary tree and have internal values, and the type of a node of the binary tree corresponding to each entry is determined by the internal value stored in relation with the entry.  
           [0044]    It is preferable that the internal value stored in relation with the entry has a different sign according to the type of a node corresponding to the entry.  
           [0045]    It is preferable that if the node corresponding to the entry is an internal node, the internal value of the entry is a relative distance value between the internal node which is the current node, and a node to be accessed next. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0046]    The above and other aspects and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which:  
         [0047]    [0047]FIG. 1 is a schematic block diagram of a related art Huffman decoding apparatus;  
         [0048]    [0048]FIG. 2 is a flowchart for explaining the related art Huffman decoding method performed in the apparatus shown in FIG. 1;  
         [0049]    [0049]FIG. 3 is a diagram showing a binary tree structure which is used in the related art Huffman decoding method;  
         [0050]    [0050]FIGS. 4 a  and  4   b  are diagrams showing memory spaces of a Huffman table, corresponding to respective nodes used in the related art Huffman decoding method;  
         [0051]    [0051]FIG. 5 is a Huffman table used in the related art Huffman decoding method;  
         [0052]    [0052]FIG. 6 is a schematic diagram showing a process for generating a one-dimensional look-up table according to an exemplary, non-limiting embodiment of the present invention;  
         [0053]    [0053]FIG. 7 is a table showing a process for generating a one-dimensional look-up table according to an exemplary, non-limiting embodiment of the present invention;  
         [0054]    [0054]FIG. 8 is a one-dimensional look-up table used in a decoding method according to an exemplary, non-limiting embodiment of the present invention; and  
         [0055]    [0055]FIG. 9 is a flowchart for explaining an improved Huffman decoding method based on numerical operations, according to an exemplary, non-limiting embodiment of the present invention. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0056]    [0056]FIG. 6 is a schematic diagram showing a process for generating an efficient one-dimensional look-up table when the look-up table is reconstructed in order to perform an improved Huffman decoding method according to an exemplary, non-limiting embodiment of the present invention. In the table converting process, the nodes of a binary tree are grouped in each identical search stage and arranged in a one-dimensional array from left to right so as to increase the size of the codewords shown in Table 1. When the look-up table shown in FIG. 6 is generated, each internal node stores a relative distance between the location of the current node and a node which will be accessed next, as an internal value, and each terminal node stores a return value that is to be actually sent back as an internal value.  
         [0057]    The one-dimensional array generated in a sorting process has a structure of a serial static look-up table as shown in FIG. 6, without generating a dynamic data structure by a linked-list.  
         [0058]    Referring to FIG. 6, the generation process of the one-dimensional look-up table will now be explained in more detail. Index numbers are sequentially given to respective nodes from the upper layer to the lower layer, that is, in order of layer-0, layer-1, layer-2, layer-3, layer-4, and layer-5. Also, in an identical layer, index numbers are sequentially given to respective nodes. In a preferred embodiment of the present invention, continuous index numbers are given to sibling nodes as shown in FIG. 6. Though index numbers are given from the left-hand side to the right-hand side in an identical layer in the present embodiment, the present invention is not limited thereto, as index numbers may be given from the right-hand side to the left-hand side in an identical layer.  
         [0059]    In FIG. 6, to the terminal nodes to which index numbers 0, 4, 7, 8, 9, 10, 12, 13, . . . are given, actual return values ‘60’, ‘59’, ‘4’, ‘61’, ‘58’, ‘62’, ‘57’, and ‘63’ are allocated respectively, from the left-hand side to the right-hand side in increasing order of the size of codewords shown in table 1.  
         [0060]    Meanwhile, in the internal nodes to which index numbers 1, 2, 3, 5, 6, 11, . . . are given, relative distance values between the current nodes and a node which will be accessed next are stored, respectively. In the internal nodes to which index numbers 1, 2, 3, 5, 6, 11 are given, the difference values of the index numbers of the current nodes and the index number of the left-hand node of children nodes, that is, ‘− 1 ’, ‘− 2 ’, ‘− 3 ’, ‘− 3 ’, ‘− 4 ’, and ‘− 1 ’, are stored, respectively.  
         [0061]    [0061]FIG. 7 illustrates a one-dimensional look-up table constructed according to the table reconstruction method shown in FIG. 6. The reconstructed one-dimensional look-up table contains the index numbers given to respective nodes of the binary trees and the internal values of the nodes stored in relation with the index numbers. The internal value of each internal node stored in the look-up table is the relative distance value between the current node and a node which will be accessed next, that is, the difference value between the index number of the current node and the index number of the left-hand node of the children nodes in the present embodiment, and therefore is always a negative value. Meanwhile, the internal value of each terminal node is a result value which will be sent back, that is, a return value, and therefore is a positive value.  
         [0062]    Though in the present embodiment, each internal node has a difference value between the index number of the current node and the index number of the left-hand node of the children nodes, the present invention is not limited thereto, as other relative distance values, such as the difference value from the index number of the right-hand node, may be stored selectively in other embodiments.  
         [0063]    The columns named ‘Left-hand node: 0’ and ‘Right-hand node: 1’ in the one-dimensional look-up table shown in FIG. 7 are not included in the final look-up table shown in FIG. 8, and show an intermediate process for generating a table. These columns indicate search address values which will be accessed next in a search process. Together with 1 bit data read from an encoded bit stream, each item in these columns indicates the index number of a node in a search stage for moving to a next node.  
         [0064]    The related art binary tree Huffman look-up table should have 3 elements for each node, including a data value of the node and address values for moving to a next node when branch to the left-hand node or the right-hand node is performed. Accordingly, 3 memory spaces are needed for each node of the binary tree.  
         [0065]    In contrast, in the final look-up table according to an exemplary, non-limiting embodiment of the present invention shown in FIG. 8, each internal node has only a relative distance value between the current node and a node which will be accessed next, and each terminal node has only a result value which will be sent back, that is, a return value. Also, each of these two values as indicated by thick lines in FIG. 7 occurs always exclusively. Therefore, each of them can be arranged in a one-dimensional space as shown in FIG. 8. Accordingly, compared to the related art look-up table, needed memory space is reduced by at least a third.  
         [0066]    [0066]FIG. 9 is a flowchart for explaining an improved Huffman decoding method using the one-dimensional look-up table according to an embodiment of the present invention shown in FIG. 8. In step S 910  as the first step of decoding using the one-dimensional look-up table, an entry of the look-up table of FIG. 8 is accessed by using the first bit value of a predetermined codeword of an encoded bit stream which is input to the Huffman decoder, as index information.  
         [0067]    In step S 920 , it is determined whether a current node corresponding to the entry accessed in step S 910  is an internal node or a terminal node. In the present embodiment, the type of a node is determined according to whether the internal value of a corresponding entry is a positive value or a negative value.  
         [0068]    In step S 920 , if the internal value stored in the corresponding entry is a positive value, it is determined that the current node is a terminal node, and step S 930  is performed. If the internal value is a negative value, it is determined that the current node is an internal node, and step S 940  is performed.  
         [0069]    When it is determined in step S 920  that the current node is a terminal node, the internal value of the current node is output as a return value which will be actually sent back, in step S 930 . However, when it is determined in step S 920  that the current node is an internal node, a new index value is calculated according to the following equation 1 in step S 940 , and an entry in the look-up table corresponding to the calculated index value is accessed:  
         index=index−data(index)+new_digit( )  (1)  
         [0070]    In the equation 1, index in the right side denotes the index number of a current node, data(index) denotes a relative distance value between the current node stored as an internal value in the current entry and a node which will be accessed next, and new_digit( ) denotes a next bit value. The relative distance value is the difference value between the index number of the current node and the index number of the left-hand node of the children nodes of the current node.  
         [0071]    Referring to the one-dimensional look-up table according to the present invention shown in FIG. 8 and the flowchart shown in FIG. 9, an exemplary, non-limiting process for decoding ‘1110100’ in an encoded bit stream which is input to the Huffman decoder will now be explained.  
         [0072]    In step S 910  as the first step of decoding, an entry of the look-up table of FIG. 8 is accessed by using the first bit ‘1’ of the first codeword of an encoded bit stream ‘ 1 110100’ which is input to the Huffman decoder, as index information. Here, it is assumed that a codeword corresponding to a predetermined return value begins from the first bit of the bit stream ‘1110100’.  
         [0073]    In step S 920 , it is determined whether a current node is an internal node or a terminal node, based on the sign of the internal value of a node corresponding to the current entry accessed in step S 910 , that is, the entry having the index value 1 of the look-up table of FIG. 8. In the present embodiment, since the internal value of the entry having the index value 1 is a negative value ‘−1’ in the step  920 , it is determined that the current node is an internal node, and step S 940  is performed.  
         [0074]    In step S 940 , a new index value is calculated by equation 1 and a new entry is accessed according to the calculated index value, and then the step  920  is performed. In the present embodiment, data(index) is the result value of index number 1-2, and new_digit( ) is the next bit value ‘1’ in the bit stream ‘1 1 10100’ desired to be decoded. Accordingly, the new index value is index=1−(−1)+1=3.  
         [0075]    Therefore, in step S 940 , an entry corresponding to index 3 is accessed and then step S 920  is performed. In step S 920 , it is determined whether a node of the current entry accessed in step S 940 , that is, the entry corresponding to index 3 of the look-up table of FIG. 8, is an internal node or a terminal node. In the step  920 , since the internal value of the entry is a negative value ‘−3’, it is determined that the current node is an internal node, and step S 940  is performed again.  
         [0076]    In step S 940 , according to equation 1, a new index value is calculated. Since new_digit( ) is the second bit value ‘1’ of the first codeword in the bit stream ‘11 1 0100’ desired to be decoded, the new index value is index= 3−(− 3)+1=7.  
         [0077]    Therefore, an entry corresponding to index 7 is accessed and then step S 920  is performed. In step S 920 , it is determined whether a node of the current entry accessed in step S 940 , that is, the entry corresponding to index 7 of the look-up table of FIG. 8, is an internal node or a terminal node. In step S 920 , since the internal value of the entry is a positive value, it is determined that the current node is a terminal node, and step S 930  is performed.  
         [0078]    In step S 930 , the internal value ‘4’ of the entry corresponding to index 7 is output as a result value which will be sent back, that is, a decoded codeword. By doing so, the decoding steps for the first bit set in the encoded bit steam ‘ 1 110100’, that is, the codeword ‘111’, are finished, and then decoding for a second codeword begins.  
         [0079]    In step S 910 , an entry of the look-up table of FIG. 8 is accessed by using the first bit ‘0’ of the second codeword of the bit stream ‘1110100’. In step S 920 , since the internal value of the entry corresponding to index 0 accessed in step S 910  is a positive value, it is determined that the current node is a terminal node and step S 930  is performed (the internal value is returned).  
         [0080]    In step S 930 , the internal value ‘60’ of the entry corresponding to index 0 is output as a decoded codeword. By doing so, the decoding steps for the second codeword ‘0’ in the encoded bit steam ‘111 0 100’, are finished, and then decoding for a third codeword begins.  
         [0081]    In step S 910 , an entry of the look-up table of FIG. 8 is accessed by using the first bit ‘1’ of the third codeword of the bit stream ‘1110 1 00’. In step S 920 , since the internal value of the current entry accessed in step S 910 , that is, the entry corresponding to index 1, is a negative value ‘−1’, it is determined that the current node is an internal node and step S 940  is performed.  
         [0082]    In step S 940 , according to the equation 1, a new index value is calculated. Since new_digit( ) is the next bit value ‘0’ in the bit stream ‘11101 0 0’ desired to be decoded, the new index value is index=1−(−1)+0=2. Therefore, an entry corresponding to index 2 is accessed, and step S 920  is performed.  
         [0083]    In step S 920 , it is determined whether a node of the current entry accessed in step S 940 , that is, the entry corresponding to index 2 of the look-up table of FIG. 8, is an internal node or a terminal node. In the present embodiment, since the internal value of the current entry is a negative value ‘−2’, it is determined that the current node is an internal node, and step S 940  is performed.  
         [0084]    In step S 940 , according to the equation 1, a new index value is calculated. Since new_digit( ) is the second bit value ‘0’ of the third codeword in the bit stream ‘111010 0 ’ desired to be decoded, the new index value is index=2−(−2)+0=4 according to the equation 1. Therefore, an entry corresponding to index 4 is accessed and then step S 920  is performed.  
         [0085]    In step S 920 , it is determined whether a node of the current entry accessed in step S 940 , that is, the entry corresponding to index 4 of the look-up table of FIG. 8, is an internal node or a terminal node. In step S 920 , since the internal value of the current entry is a positive value ‘59’, it is determined that the current node is a terminal node, and step S 930  is performed.  
         [0086]    In step S 930 , the internal value ‘59’ of the current entry is output as a decoded codeword of the third codeword ‘100’ of the encoded bit stream ‘1110   100   ’. Thus, decoding for 3 codewords in the encoded bit stream ‘ 111 0 100 ’ is performed and decoded codewords ‘4, 60, 59’ are output as result values.  
         [0087]    Therefore, when the process for performing the Huffman decoding method based on the related art binary tree is compared with the process for performing the improved Huffman decoding method according to the exemplary, non-limiting present embodiment, it is shown that the Huffman decoding method applies 1 data bit which is input from the encoded bit stream, directly to the access of an entry of the look-up table, that is, to calculations of address values so that conditional statements, which are needed for transition between nodes in the related art Huffman decoding method, can be removed. Accordingly, the Huffman decoding method according to the present invention achieves more improved processing efficiency.  
         [0088]    Table 2 shows the performance results of the improved Huffman decoding method according to the present invention and the Huffman decoding method by the related art sequential search method.  
                                                                               TABLE 2                                       Average               search frequency                Search   Total   Proposed   Sequential   Improvement       Huffman   stage/table   search   search   search   of search       codebook   size   frequency   method   method   speed (%)                    Scale    19/121   14022   3.91   5.09   30.01       factor        1   16/81   5624   4.52   12.50   177.98        2   16/81   7857   5.39   18.61   245.11        3   16/81   16710   3.77   6.46   71.11        4   16/81   8680   4.77   11.42   139.32        5   16/81   28794   3.08   4.51   46.35        6   16/81   1086   5.17   14.04   172.58        7   16/64   2958   2.64   3.29   24.80        8   16/64   582   4.81   11.13   131.28        9    16/169   234   2.94   5.09   73.26       10    16/169   2594   6.51   33.60   415.63       11    16/289   7640   7.41   65.02   776.43                  
 
         [0089]    As shown in the performance results of Table 2, when an arbitrary MPEG-2 advanced audio coding (AAC) test files were tested, performance improvement was achieved by a minimum of about 24% to a maximum of about 777% according to the types of Huffman codebooks. Also, from the viewpoint of average search frequency, the Huffman decoding method according to the present embodiment showed about 75% performance improvement compared with the Huffman decoder using an ordinary sequential search method.  
         [0090]    Table 3 shows the test results of the methods by using 6 different MPEG-2 AAC files under the same measuring environments.  
                                                               TABLE 3                                       Total search frequency                    Proposed search   Sequential search   Improvement of       Test file   method   method   search speed (%)                    test01.aac   407,591   1,168,714   187       test02.aac   404,608   1,238,404   206       test03.aac   360,727   1,236,965   243       test04.aac   371,423   941,376   153       test05.aac   174,997   511,710   192       test06.aac   239,362   740,700   209       Average   326,451   972,978   198                  
 
         [0091]    As shown in Table 3, the improved Huffman decoding method according to the present embodiment improves the search speed by a minimum of about 153% and a maximum of about 243% according to the types of file, compared with the Huffman decoding method of the related art sequential search method.  
         [0092]    The present invention is not limited to the preferred embodiments described above, and it is apparent that variations and modifications by those skilled in the art can be effected within the spirit and scope of the present invention as defined in the appended claims.  
         [0093]    Also, the present invention may be embodied in a code, which can be read by a computer, on a computer readable recording medium. The computer readable recording medium includes all kinds of recording apparatuses on which computer readable data are stored.  
         [0094]    The computer readable recording media includes (but is not limited to) storage media such as magnetic storage media (e.g., ROM&#39;s, floppy disks, hard disks, etc.), optically readable media (e.g., CD-ROMs, DVDs, etc.), and carrier waves (e.g., transmissions over the Internet). Also, the computer readable recording media can be transmitted to computer systems connected through a network, and it can store and execute a computer readable code in a distributed mode.  
         [0095]    According the improved Huffman decoding method and apparatus of the present invention as described above, ‘comparison and branch’ operations needed in the prior art binary tree search are removed, thereby increasing the search speed. Also, a look-up table can be implemented with a memory space which is only a third of the memory space of the prior art table that is used for the ‘comparison and branch’ statements. Additionally, the encoded bit stream may be encoded by one of the motion pictures experts group (MPEG) standard, the joint photographic coding experts group (JPEG) standard, and the H.26x standard.