Source: http://www.google.com/patents/US5696507?dq=5920316
Timestamp: 2013-12-11 01:58:29
Document Index: 337208575

Matched Legal Cases: ['art 51', 'art 52', 'art 51', 'art 51', 'art 52', 'art 51', 'art 52', 'art 52', 'art 52', 'art 52', 'art 52', 'art 51', 'art 52', 'art 52', 'art 51', 'art 52', 'art 52', 'art 52', 'art 52', 'art 52', 'art 52', 'art 51', 'art 52', 'art 52', 'art 102']

Patent US5696507 - Method and apparatus for decoding variable length code - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsDisclosed are method and apparatus for decoding variable length codewords such as a digital image signal at a high speed using a Huffman code tree, in accordance with the present invention, since a variable length coded codeword is stored in a look-up memory in a node order according to levels of a canonical...http://www.google.com/patents/US5696507?utm_source=gb-gplus-sharePatent US5696507 - Method and apparatus for decoding variable length codePublication numberUS5696507 APublication typeGrantApplication numberUS 08/655,838Publication dateDec 9, 1997Filing dateMay 31, 1996Priority dateMay 31, 1996Fee statusPaidPublication number08655838, 655838, US 5696507 A, US 5696507A, US-A-5696507, US5696507 A, US5696507AInventorsSeung-Hyun NamOriginal AssigneeDaewoo Electronics Co., Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (7), Referenced by (29), Classifications (8), Legal Events (7) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for decoding variable length codeUS 5696507 AAbstract Disclosed are method and apparatus for decoding variable length codewords such as a digital image signal at a high speed using a Huffman code tree, in accordance with the present invention, since a variable length coded codeword is stored in a look-up memory in a node order according to levels of a canonical Huffman code tree structure, and the node order of the coded codewords is detected by a predetermined calculating operation so that the node order is used as an address of the decoding codeword when decoding the variable length coded codeword. Therefore, the variable length code decoding is achieved in a manner which simply stores variables in a memory and a latch without changing a hardware when a Huffman code tree is changed by an operation of a central system. Also, since the present invention may by processing a coded codeword with a clock using a parallel calculation regardless of a decoded codeword length, it can decode a coded codeword at higher speed than a conventional variable length decoding apparatus and method thereof which perform to decode in the unit of bit.
What is claimed is: 1. A method for decoding a variable length code, said method comprising the steps of:a) receiving a coding bit string for decoding having a plurality of variable length codewords based on a Huffman code tree structure, for packing the received coding bit string for decoding to obtain a longest codeword length, and for outputting the packed coding bit string for decoding; b) calculating node position values for the packed coding bit string for decoding the longest codeword length outputted from the step a) in order to detect a boundary line of a codeword from the packed coding bit string for decoding the longest codeword length; c) detecting a code length of the variable length codeword according to the calculated node position values from the step b); d) calculating a total terminal node number from level "0" prior level to a in which a node corresponding to a codeword according to the detected code length from the step c) is located; e) adding the node position value corresponding to the detected code length from the the step c) in the calculated node position values from the step b) to the calculated total terminal node number from the step d), to output the added value; f) reading out to-be decoded codewords having the added value from the step e) as an address from a memory which are sequentially storing the decoding codewords from a root of a canonical Huffman code tree according to by node position of decoded codeword; and g) judging whether or not a bit string to be decoded remains, if no finish a routine, and if yes return to the step a). 2. The method for decoding a variable length code as claimed in claim 1, wherein the node position values are calculated by an expression ##EQU8## at the step b), wherein the PT.sub.k denotes node positions in accordance with binary input bits γ.sub.1, γ.sub.2, γ.sub.3 . . . γ.sub.k from `1` to `k` in a level "k" of the Huffman tree, the γ.sub.1 is a bit value of each bit string γ.sub.1, γ.sub.2, γ.sub.3 . . . , and the L.sub.i is the total terminal node numbers in a level "i".
4. The method for decoding a variable length code as claimed in claim 1, wherein the total terminal node numbers S.sub.k of the prior level to a level in which a node corresponding to the detected codeword length is calculated by means of ##EQU9## at the step d), where, S.sub.k means the total terminal node numbers from level "0" to the prior to level "k" and L.sub.i means a terminal node numbers in a level "i".
DESCRIPTION OF THE PREFERRED EMBODIMENT A description will be given below in detail, with reference to the accompanying drawings, of the mechanical structure, the circuitry configuration, and the operation of a method and an apparatus for decoding a variable length code regarding an embodiment of the present invention.
FIG. 5 illustrates the configuration for a variable length code decoding apparatus according to one embodiment of the present invention. Referring to FIG. 5, the variable length code decoding apparatus according to one embodiment of the present invention comprises a packing part 51, a boundary line sampling part 52, a register 53, a code length detecting element 54, a multiplexer 55, a latch 56, an adder 57, and a memory 58. Packing part 51 receives a to-be-decoded coding bit string in which many variable length codewords are contained based on the Huffman code tree structure, packing part 51 packs the received to-be-decoded coding bit string in the longest codeword length, and shifts a decoded codeword out by means of a barrel shifter 511 therein to pack a successive coding bit string with the exception of the decoded codeword in the to-be-decoded coding bit string in the longest codeword length. Boundary line sampling part 52 receives the packed to-be-decoded coding bit string of the longest codeword length from packing part 51 for sampling a boundary line of a codeword and calculates PT.sub.k using an expression (1) which will be described later to output the calculated PT.sub.k into multiplexer 55, and outputs the MSBs of the calculated PT.sub.k into code length detecting element 54 in order to judge whether the calculated PT.sub.k is positive or negative. A method for calculating the PT.sub.k is as follows. ##EQU3## where, the PT.sub.k denotes node positions in accordance with binary input bits γ.sub.1, γ.sub.2, γ.sub.3 . . . γ.sub.k of from 1 to k in a level "k" of the Huffman tree (the top of each level is a node position "0", and the node position increases "1" each as the level descend downward therefrom), the γ.sub.1 is a bit value of each bit string (γ.sub.1, γ.sub.2, γ.sub.3 . . . ), and the L.sub.i is a total terminal node number in a level "i". That is, when the longest codeword length is `M`, boundary line sampling part 52 calculated all PT.sub.i of 1≦i≦M in parallel. All PT.sub.k in a codeword have a positive value and the positive values means a node position. However, all PT.sub.i beyond a boundary line of a codeword have a negative value. Therefore, a value subtracting 1 from "i" of PT.sub.i which have a negative value first in all PT.sub.i becomes a coded codeword length. In register 53, S.sub.i including S.sub.1, S.sub.2, S.sub.3 . . . S.sub.M, is stored in a first register 531, a second register 532, a third register 533 . . . a M-th register 53M, respectively. Register 53 outputs a S.sub.i stored in one register among the first register 531, the second register 532, the third register 533 . . . the M-th register 53M into a first latch 561 of latch 56 according to the level of an output signal from code length detecting element 54.
Code length detecting element 54 detects a variable length codeword length for decoding from the decoding bit string from boundary line sampling part 52 according to the MSBs of the calculated node position values PT.sub.k by boundary line sampling part 52, and for generating a first selection signal for selecting a node position value corresponding to the detected variable length codeword length and a second selection signal in order to select and enable the register from the at least one register 53 to store total terminal node numbers from level "0" to a prior level in which a node corresponding to the detected variable length codeword length is located. S.sub.k is a calculated value by means of an expression (2) which will be described later and means a total terminal node number from level "0" to a prior level to level "i". ##EQU4##
FIG. 6 shows a circuitry diagram of the code length detecting element as shown in FIG. 5. Code length detecting element 54 includes a plurality of XOR gates 61, 62, 63 . . . and 6M which logically-exclusive-OR combine MSBs of PT.sub.k provided from boundary line sampling part 52 in order to enable one register among register 53. Multiplexer 55 sequentially outputs node position values PT.sub.k from boundary line sampling part 52 selected in response to the first selection signal for outputting S.sub.k from code length detecting element 54 into a second latch 562 of latch 56. Latch 56 includes first and second latches 561 and 562. Latch 56 latches (stores temporarily) one S.sub.i from register 53 and one PT.sub.i from multiplexer 55. Adder 57 adds one PT.sub.i to one S.sub.i, from latch 56 using an expression (3) which will be described later to output the added value A.sub.ij into memory 58.
A.sub.ij =S.sub.i +PT.sub.i                                (3)
where, A.sub.ij is a memory address which a codeword of a terminal node locates at "j" position of "i" level in a canonical Huffman code tree. In other words, adder 57 adds a second latch value in which a node position value S.sub.1 corresponding to a codeword searched boundary line in a level of a node corresponding to a codeword searched boundary line is stored to a first latch value in which a total terminal node number of from level 0 to the prior level to a level in which anode corresponding to the codeword searched boundary line is stored. In memory 58, decoding codewords are stored from a root of the canonical code tree according to a node position of a coded codeword, outputs the corresponding decoding codeword using the A.sub.ij from adder 57 as an address, and has an ROM, and RAM or a programmable logic array (PLA).
At step S71, packing part 51 received a to-be-decoded coding bit string `101100001110 . . . ` to pack only the received bit string `101100` from the received to-be-decoded coding bit string as many as the longest codeword length (M) six and then outputs the packed bit string `101100` into boundary line sampling part 52. Then, at step S72, boundary line sampling part 52 receives the packed to-be-decoded coding bit string of the longest codeword length from packing part 51 for sampling a boundary line of a codeword and calculates node position values PT.sub.k using the expression (1) in parallel. In this embodiment, since the longest codeword length is six bits as shown in FIG. 4, boundary line sampling part 52 calculates all PT.sub.i of 1≦i≦6 range using γ.sub.1 γ.sub.2 γ.sub.3 γ.sub.4 γ.sub.5 γ.sub.6. PT.sub.1 is calculated by substituting `1` into `k` using the expression (1) as follows. ##EQU5##
In the meantime, since the γ.sub.1 is a binary code `1` and the L.sub.0 and L.sub.1 which represent a terminal node number in each level are a decimal code `0` and `1`, respectively, the PT.sub.1 value can be obtained as follows.
PT.sub.1 =2.sup.0.1-2.sup.1.0=1
PT.sub.4 is calculated as follows by substituting `4` into `k` using the same manner because the γ.sub.1 γ.sub.2 γ.sub.3 γ.sub.4 is a binary code `1011`, and the L.sub.-, L.sub.1, L.sub.2 and L.sub.3 which represent terminal node numbers in each level have decimal codes `0`, `1`, `0` and `3`, respectively. ##EQU6##
When the decimal code `-3` is converted into a complement of two, the decimal code `-3` is represented as "1011101" by the six bits. Because the furthest left bit is a MSB is `1`, it can be noted that PT.sub.4 has a negative value. Each values of PT.sub.2, PT.sub.3, PT.sub.5 and PT.sub.4 can be calculated in the same manner as above. The result is shown in the following Table 2.
TABLE 2______________________________________PT.sub.kPT.sub.k  decimal     binary(MSB &#8594; LSB)                            sign______________________________________PT.sub.1  1           000001        positivePT.sub.2  0           000000        positivePT.sub.3  1           000001        positivePT.sub.4  -3          111101        negativePT.sub.5  -8          111000        negativePT.sub.6  -18         101110        negative______________________________________
At this time, boundary line sampling part 52 outputs the calculated PT.sub.1, PT.sub.2, PT.sub.3, PT.sub.4, PT.sub.5 and PT.sub.6 into multiplexer 55 to use the addresses of an decoding codeword. Also, boundary line sampling part 52 outputs MSBs 0, 0, 0, 1, 1 and 1 of the calculated values of PT.sub.1, PT.sub.2, PT.sub.3, PT.sub.4, PT.sub.5 and PT.sub.6 into code length detecting element 54 in order to judge whether the calculated values of PT.sub.1, PT.sub.2, PT.sub.3, PT.sub.4, PT.sub.5 and PT.sub.6 are positive or negative. That is, in the present invention, since the node numbers have been stored in first, second, third, fourth, fifth, sixth, . . . Mth registers 531, 532, 533, 534, 535, 536 . . . 53M of register 53, code length detecting element 54 receives MSBs 0, 0, 0, 1, 1 and 1 of the calculates values of PT.sub.1, PT.sub.2, PT.sub.3, PT.sub.4, PT.sub.5 and PT.sub.6 from boundary line sampling part 52 to control the corresponding register. That is, code length detecting element 54 receives a first bit `0` of the MSBs 0, 0, 0, 1, 1 and 1 through a first input terminal of a first XOR 61, a second bit `0` thereof through a second terminal of first XOR 61 and a first terminal of a second XOR 62, a third bit `0` thereof through a second terminal of second XOR 62 and a first terminal of a third XOR 63, a fourth bit `1` thereof through a second terminal of third XOR 63 and a first terminal of a fourth XOR 64, a fifth bit `1` thereof through a second terminal of fourth XOR 64 and a first terminal of a fifth XOR 65, a sixth bit `1` thereof through a second terminal of fifth XOR 65 and a first terminal of a sixth XOR 66, and a sixth bit `1` thereof through a first terminal of sixth XOR 66 and `1` through a second terminal of sixth XOR 66 to enable only the third XOR 63 as `1`. Accordingly, a S.sub.3 "1" is outputted into first latch 561 from third XOR 63 which has been enabled as above.
As shown in Table 2, PT.sub.1, PT.sub.2 and PT.sub.3 have positive signs because the MSBS thereof is "0". The decimal codes `1`, `0`, and `1` of the PT.sub.1, PT.sub.2, and PT.sub.3 indicate node positions in the corresponding level, respectively. PT.sub.4, PT.sub.5 and PT.sub.6 have negative signs because the MSBs thereof is "1". Therefore, code length detecting element 54 can calculate a level of the tree structure in which a final bit of the current decoding codeword is located by searching a position generating `1`, that is, a negative value firstly in PT.sub.k from boundary line sampling part 52. That is, a first codeword length is calculated from the inputted bit string. In an embodiment according to the present invention, the codeword length "3" (that is, "101" from "101100001110 . . . ) located in a third level indicating a decoding codeword length first is achieved by subtracting "2" from "i" (i-1=4-1), that is, "4" generating a negative value first at step S73. Then, a total node number S.sub.3 in a level from level "0" to a prior level in which a node in a tree structure corresponding to the decoding codeword "101" of the codeword length "3" is located and calculated by means of the expression (2) at step S74. ##EQU7##
Then, code length detecting element 54 generates a second selection signal for selecting the calculated PT.sub.3, that is, a node position in a level in which a node of the tree structure of the detected codeword for decoding, from boundary line sampling part 52 based on the calculated codeword length `3` to output the generated second selection signal into multiplexer 55. Then, multiplexer 55 selects the PT.sub.3 value to output second latch 562.
Then, at the step S75, adder 57 adds PT.sub.3 from a second latch 562 to S.sub.3 from a first latch 561 to output the added value A.sub.33 into memory 58. The added value A.sub.33 is an address of memory 58 in which a decoding codeword corresponding to a coding codeword searching a boundary line of a code is stored. Therefore, at the step S76, memory 58 receives the address A.sub.33 =2 from adder 57 to output a decoding codeword "c" corresponding to the address "2" so that a codeword is decoded. Then, packing part 51 receives a code length "3" of the decoded codeword "101" from code length sampling part 52 which packs an inputted bit (100001110 . . . ) from a successive bit except the decoded bit string "101" as many as the longest codeword length (M) six (`100001`), to output the packed bit string `100001` into boundary line sampling part 52, and the packed bit string `100001` is decoded in the same manner so that all inputted bit strings 100001110 . . . can be decoded.
In other words, a first, a decoding codeword length is calculated, a memory address in which the codeword is stored is calculated by the expression (3). That is, the memory address is obtained by adding PT.sub.i of the corresponding codeword in the Huffman code tree to S.sub.i thereof. In this embodiment, the code length is three bits. Therefore, the memory address can be obtained from PT.sub.3 +S.sub.3. Since the PT.sub.3 is "1" as shown in a table 2 and the S.sub.3 is "1" as a total terminal none number from a root to a level "2" the memory address becomes "2". Therefore, at a final the step, the system obtains a final decoding symbol by reading the data corresponding to the memory address "2". That is, the user can know a decoding symbol in which is stored the memory address "2" is "c". In other words, it is obtained by the calculating operation that significant three bits γ.sub.1 γ.sub.2 γ.sub.3 (="101") among a coding bit string corresponds to a codeword of a symbol "c". The remaining coding bit string can be decoded by shifting it as many as the code length of the decoded codeword and using the same way as above. That is, because the γ.sub.1 γ.sub.2 γ.sub.3 is decoded, a barrel shifter shifts out the decoded γ.sub.1 γ.sub.2 γ.sub.3 from the decoding bit string and receives successive value γ.sub.3 γ.sub.4 γ.sub.5 γ.sub.6 γ.sub.7 γ.sub.8 γ.sub.9 γ.sub.10 γ.sub.11 . . . ("100001110 . . . ") to decode the received successive value γ.sub.3 γ.sub.4 γ.sub.5 γ.sub.6 γ.sub.7 γ.sub.8 γ.sub.9 γ.sub.10 γ.sub.11 . . . for in the same way. Accordingly, information symbol string of " c b a a e . . . " corresponding to a bit string 101100001110 . . . is obtained.
Hereinafter, the operation of the conventional decoder is more readily understood. It is assumed that the data stream input from data channel 107 to buffer 106 consists of the bit stream a.sub.1 -a.sub.8 b.sub.1 -b.sub.6 c.sub.1 -c.sub.15 d.sub.1 -d.sub.15 e.sub.1 -e.sub.12 f.sub.1 -f.sub.10 g.sub.1 -g.sub.9 h.sub.1 -h.sub.16 . . . , as shown in FIG. 3, where a.sub.1 -a.sub.8 represents the eight bits in the first variable-length word, b.sub.1 -b.sub.6 represents the six bits in the second variable-length word, etc.
Prior to the first clock tick, latch 131 is initialized so that Read output is "1". Latch 121 is also initialized so that first barrel shifter 109 has an initial shift of "16". With "16" input to adder 130 from latch 121 and 16 modulo-16 (equal to "0") also input to adder 130 from latch 131, the output of adder 130, and thus the shift of second barrel shifter 127 is "16", with Carry being "1". With Read being "1", the first data segment, consisting of the 16-bits a.sub.1 -a.sub.8 b.sub.1 -b.sub.6 c.sub.1 c.sub.2, is input on leads 105 to the interface part 102. At this time all the latches, the outputs of barrel shifters 109 and 127, and the outputs of PLA 116 are noise values, represented in FIG. 2 with "X".
At the first clock cycle tick, the previous Carry "1" becomes a Read "1", which retrieves the next data segment from buffer 106 onto leads 105. At this clock tick, however, the previous Carry "1" causes the previous output of buffer 106 to be read into latch 126. Latch 121 remains initialized at "16", so that the shift of first barrel shifter 109 remains "16" and adder 130 remains at "16", together with Read at "1" and Carry at "1". With the sift of second barrel shifter 127 being "16" and the 17th-32nd bits being a.sub.1 -a.sub.8 b.sub.1 -b.sub.6 c.sub.1 c.sub.2 from latch 126, that sequence appears at the output of second barrel shifter 127. Latches 100, 111 and 125 contain noise, as does the output of first barrel shifter 109 and the decoded word and codeword length outputs of PLA 116.
At the second clock tick, the previous output of second barrel shifter 127 is latched into latch 111. Since Read is still "1" and the previous carry was "1", the next data segment (the third) is retrieved from buffer 106, the data segment (the first) in latch 126 is latched into latch 125, and the second data segment is latched into latch 126. Latch 121 is still initialized so that the shift of first barrel shifter 109 is "16". This maintains the output of adder 130 at "16" and Carry and Read at "1". Since the previous output of second barrel shifter 127 consisted of the first data segment, at the second clock tick that segment appears in latch 111 and in the 17th-32nd input positions of first barrel shifter 109. The "16" at the shift input to first barrel shifter 109 thereby transfers this first segment to the barrel shifter output on leads 112. The "16" at the shift input of second barrel shifter 127 transfers the second data segment, c.sub.3 -c.sub.5 d.sub.1 -d.sub.13, in latch 126 to the output of second barrel shifter 127. The codeword table 117 in PLA 116 recognizes the first eight bits in the first segment as codeword "A". The decoded word table 119 outputs this fixed-length decoded word, A, on leads 103. Codeword length table 118 outputs the length, "8", of this word on leads 120.
On the third clock tick, this first data segment is latched into latch 110, and thus into the first 16-inputs of first barrel shifter 109. The previous decoded length, "8", is latched into latch 121, which is therefore the shift of first barrel shifter 109. The output of first barrel shifter 109 shifted to the 9th-24th input bits, or the sequence b.sub.1 -b.sub.6 c.sub.1 -c.sub.5 d.sub.1 -d.sub.5. The Carry "1" from at the second clock tick becomes a Read "1" at this third tick, thereby retrieving the next data segment from buffer 106. This previous Carry "1", upon the occurrence of the third tick, transfers the previous segments from buffer 106 to latch 126, and from latch 126 to latch 125. The "8" at the output of latch 121 is added by adder 130 to the previous modulo-16 output of latch 131 (equal to "0") to form a new output equal to "8". The shift of second barrel shifter 127 now is "8", with Carry being "0". The output of second barrel shifter 127 now begins with its 9th input, which is d.sub.6. This sequence is thus continuous with the sequence at the output of first barrel shifter 109, which sequences together will form the inputs to first barrel shifter 109 at the next clock tick. During this third clock cycle, codeword B is recognized in the first 6-bits input to codeword table 117, and the fixed-length decoded word B is output on leads 103 and the codeword length "6" is output by codeword length table 118.
Since the previous Carry was "0", at the fourth clock tick the next data segment is not retrieved from buffer 106 and the contents of latches 125 and 126 remain the same as in the previous clock cycle. The previous output of first barrel shifter 109 is transferred into latch 110 beginning with bit b.sub.1, and the previous output of second barrel shifter 127 is shifted into latch 111, beginning with d.sub.6. The "6" now at the output of latch 121 shifts the first barrel shifter 109 output to the 7th-22nd bits, beginning with bit c.sub.1 and ending with bit d.sub.11. This same "6" is added by adder 130 to the previous "8", to produce a shift of "14" to second barrel shifter 127. The output of second barrel shifter 127 thus begins with the 15th bit input, or d.sub.12, which is next bit following the last bit in first barrel shifter 109. Since the accumulated codeword lengths is still less than "16", the Carry output is still "0". The codeword C is output by decoded word table 119 and its codeword length of "5" is output by codeword length table 118.
AT the fifth clock tick the previous output of barrel shifter 112 is latched into latch 110, beginning with bits c.sub.1 -c.sub.3, and the previous output of second barrel shifter 127 is latched into latch 111. The output window of first barrel shifter 109 is shifted 5-bits in accordance with the previous codeword length thus beginning with bit d.sub.1. the "5" in latch 121 is accumulated with the previous "14" in latch 131 to yield "19" at the output of adder 130, which shifts second barrel shifter 127 to the 20th-35th bits and produces a carry of "1". The codeword D is output by decoded word table 119 and its length of "15" is output by codeword length table 118.
At the sixth clock tick, Read is "1" since the previous Carry was "1" and the next data segment is retrieved from buffer 106 and input to second barrel shifter 127 as the previous segments are shifted into latch 126 and latch 125. In the same manner as previously described the output of first barrel shifter 109 is shifted to begin with the first bit of the next-to -be-decoded word, e.sub.1. Codeword E is decoded and a Carry is generated when the modulo-16 previous accumulated codeword length, "15", to produce an accumulated codeword length of "18".
SUMMARY OF THE INVENTION Therefore, a first object of the present invention is to provide a method for decoding a variable length code at a high speed using a Huffman code tree without changing the memory or the design thereof storing codewords based on a Huffman tree when decoded codewords are changed.
Preferably, the node position values are calculated by an expression ##EQU1## at the step b), wherein the PT.sub.k denotes node positions in accordance with binary input bits γ.sub.1, γ.sub.2, γ.sub.3 . . . γ.sub.k from 1 to k in a k level of the Huffman tree, the γ.sub.1 is bit value of each bit string γ.sub.1, γ.sub.2, γ.sub.3 . . . , and the L.sub.i is a total terminal node numbers in a level "i". More preferably, the code length is calculated by subtracting "1" from the node position value which has a negative value firstly among the calculated node position values at the step c) becomes a coded codeword length. Also, wherein the total terminal node numbers S.sub.k of a prior level to a level in which a node corresponding to the detected codeword length is calculated by means of ##EQU2## at the step d), where, S.sub.k means the total terminal node numbers from level "0" to the prior level "k" and L.sub.i means a terminal node numbers in a level "i".
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3918047 *Mar 28, 1974Nov 4, 1975Bell Telephone Labor IncDecoding circuit for variable length codesUS5173695 *Jun 29, 1990Dec 22, 1992Bell Communications Research, Inc.High-speed flexible variable-length-code decoderUS5245338 *Jun 4, 1992Sep 14, 1993Bell Communications Research, Inc.High-speed variable-length decoderUS5394144 *Jun 8, 1993Feb 28, 1995Daewoo Electronics Co., Ltd.Variable length code decoding apparatusUS5428356 *Sep 21, 1993Jun 27, 1995Sony CorporationVariable length code decoder utilizing a predetermined prioritized decoding arrangementUS5432512 *Dec 30, 1993Jul 11, 1995Daewoo Electronics Co., Ltd.Apparatus for decoding variable length codesUS5561690 *Nov 29, 1994Oct 1, 1996Daewoo Electronics Co., Ltd.High speed variable length code decoding apparatus* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5835035 *Sep 9, 1997Nov 10, 1998Philips Electronics North America CorporationHigh performance variable length decoder with two-word bit stream segmentation and related methodUS5841381 *Dec 4, 1997Nov 24, 1998Canon Kabushiki KaishaHuffman coding/decoding using an intermediate code numberUS5901177 *Aug 30, 1996May 4, 1999Daewoo Electronics Co., Ltd.High speed variable length code decoding apparatus and methodUS5949356 *Dec 23, 1996Sep 7, 1999Lg Electronics, Inc.High speed variable length code decoderUS5982306 *Dec 2, 1997Nov 9, 1999Daewoo Electronics Co., Ltd.Variable-length coding method and apparatus thereofUS6040790 *May 29, 1998Mar 21, 2000Xerox CorporationMethod of building an adaptive huffman codeword treeUS6160918 *Oct 2, 1997Dec 12, 2000At&T Corp.Method and apparatus for fast image compressionUS6188797 *May 27, 1997Feb 13, 2001Apple Computer, Inc.Decoder for programmable variable length dataUS6292114 *Jun 10, 1999Sep 18, 2001Intel CorporationEfficient memory mapping of a huffman coded list suitable for bit-serial decodingUS6580828Jun 30, 1999Jun 17, 2003Logitech Europe, S.A.Fast decodingUS6657569 *Jan 22, 2002Dec 2, 2003Honeywell International, Inc.Canonical Huffman encoded data decompression algorithmUS6771193 *Aug 22, 2002Aug 3, 2004International Business Machines CorporationSystem and methods for embedding additional data in compressed data streamsUS6771196 *Nov 12, 2002Aug 3, 2004Broadcom CorporationProgrammable variable-length decoderUS6771824 *Dec 28, 1999Aug 3, 2004Lucent Technologies Inc.Adaptive variable length decoding methodUS6839005 *Nov 12, 2003Jan 4, 2005Broadcom CorporationLow memory and MIPS efficient technique for decoding Huffman codes using multi-stage, multi-bits lookup at different levelsUS6995696 *Jan 25, 2005Feb 7, 2006Broadcom CorporationSystem, method, and apparatus for variable length decoderUS7002494 *Nov 23, 2004Feb 21, 2006Broadcom CorporationLow memory and MIPS efficient technique for decoding Huffman codes using multi-stage, multi-bits lookup at different levelsUS7009644Dec 15, 1999Mar 7, 2006Logitech Europe S.A.Dynamic anomalous pixel detection and correctionUS7039249 *Mar 14, 2002May 2, 2006Fuji Xerox Co., Ltd.Code converter, encoder, image output device and method thereofUS7043088Aug 3, 2004May 9, 2006Lucent Technologies Inc.Adaptive variable length decoding methodUS7095341 *Aug 3, 2004Aug 22, 2006Broadcom CorporationProgrammable variable-length decoderUS7199733 *Mar 8, 2005Apr 3, 2007Ali CorporationVariable length decoding apparatus and method for the image format of a digital video cameraUS7545293 *Aug 17, 2007Jun 9, 2009Qualcomm IncorporatedMemory efficient coding of variable length codesUS7573407Aug 17, 2007Aug 11, 2009Qualcomm IncorporatedMemory efficient adaptive block codingUS7634636 *Jun 22, 2006Dec 15, 2009Intel CorporationDevice, system and method of reduced-power memory address generationUS8291150 *May 9, 2007Oct 16, 2012Mitsubishi Electric CorporationTable device, variable length coding apparatus, variable length decoding apparatus, and variable length coding and decoding apparatusUS20100057810 *May 9, 2007Mar 4, 2010Mitsubishi Electric CorporationTable device, variable length coding apparatus, variable length decoding apparatus, and variable length coding and decoding apparatusUS20100131475 *Nov 20, 2009May 27, 2010Fujitsu LimitedComputer product, information retrieving apparatus, and information retrieval methodWO2002082661A2 *Jan 22, 2002Oct 17, 2002Honeywell Int IncCanonical huffman encoded data decompression algorithm* Cited by examinerClassifications U.S. Classification341/67, 341/65International ClassificationH03M7/42, G06T9/00Cooperative ClassificationH03M7/425, G06T9/005European ClassificationG06T9/00S, H03M7/42DLegal EventsDateCodeEventDescriptionDec 22, 2011ASAssignmentEffective date: 20111215Owner name: MAPLE VISION TECHNOLOGIES INC., CANADAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:DAEWOO ELECTRONICS CORPORATION;REEL/FRAME:027437/0345May 13, 2009FPAYFee paymentYear of fee payment: 12May 12, 2005FPAYFee paymentYear of fee payment: 8Jan 14, 2003ASAssignmentOwner name: DAEWOO ELECTRONICS CORPORATION, KOREA, REPUBLIC OFFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:DAEWOO ELECTRONICS CO., LTD.;REEL/FRAME:013645/0159Effective date: 20021231Owner name: DAEWOO ELECTRONICS CORPORATION 686 AHYEON-DONG, MAMay 17, 2001FPAYFee paymentYear of fee payment: 4May 31, 1996ASAssignmentOwner name: DAEWOO ELECTRONICS CO., LTD., KOREA, REPUBLIC OFFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:NAM, SEUNG-HYUN;REEL/FRAME:008029/0278Effective date: 19960523May 31, 1996AS02Assignment of assignor's interestOwner name: DAEWOO ELECTRONICS CO., LTD. 541, 5-GA, NAMDAEMOOMOwner name: NAM, SEUNG-HYUNEffective date: 19960523RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google