Canonical huffman encoded data decompression algorithm

• US 20030006918A1
• Filed: 01/22/2002
• Published: 01/09/2003
• Est. Priority Date: 04/04/2001
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Barnett, Mark L.
• Granted Patent: US 6,657,569 B2
• Time in Patent Office: Days
• US Class Current: 341/67
• CPC Class Codes: H03M 7/425 for the decoding process only
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

An apparatus and method for parallel decompression of compressed canonical Huffman encoded data.

Claims

1. A decompression device for canonical Huffman encoded data, the device comprising:

first data register means for storing a plurality of FIRSTCODE data values;

second data register means for storing a plurality of SYMBOL POINTER data values;

comparing means coupled for comparing different FIRSTCODE data values with corresponding bits of a string of compressed data;

means for combining the bits of compressed data with one of the FIRSTCODE and one of the SYMBOL POINTER data values selected as a function of an output of the comparing means and outputting an address; and

symbol table means coupled for receiving the address and outputting a corresponding symbol.

2. The device of claim 1 wherein the combining means further comprises a means for adding and subtracting the bits of compressed data and associated FIRSTCODE data values with associated SYMBOL POINTER data values.

3. The device of claim 1 wherein the combining means further comprises:

an addition means for adding the selected SYMBOL POINTER data value to the string of compressed data bits; and

a subtraction means for subtracting the selected FIRSTCODE data value from a result of the addition means.

4. The device of claim 1 wherein the combining means further comprises:

a subtraction means for subtracting the selected FIRSTCODE data value from the string of compressed data bits; and

an addition means for adding a result of the subtraction means to the selected SYMBOL POINTER data value.

5. The device of claim 1 wherein the address output by the combining means further comprises an address associated with a successful comparing of different FIRSTCODE data values with corresponding bits of a string of compressed data.

6. The device of claim 1, further comprising means for selecting one of the FIRSTCODE data values and one of the SYMBOL POINTER data values as a function of a successful comparing of one of the FIRSTCODE data values with an associated bit of the compressed data.

7. The device of claim 6, further comprising means for determining a successful comparing of one of the FIRSTCODE data values with an associated bit of the compressed data.

8. The device of claim 1 wherein the comparing means further comprises means for simultaneously comparing a plurality of the FIRSTCODE data values with a corresponding plurality of the bits of the compressed data.

9. The device of claim 1 wherein the comparing means further comprises means for sequentially examining a plurality of comparison results for determining a successful comparison.

10. The device of claim 1, further comprising means for reporting the outputting by the symbol table means of the symbol corresponding to the received address.

11. The device of claim 1, further comprising:

a memory means for storing a compressed canonical Huffman encoded data file; and

means for operating a logic device; and

wherein the decompression device is coupled to the memory means for receiving the plurality of FIRSTCODE and SYMBOL POINTER data values, decompressing compressed data, and outputting the resolved symbol.

13. The device of claim 12 wherein the intercoupled addition and subtraction blocks operate in response to an input from the multiplexer.

14. The device of claim 12 wherein the intercoupled addition and subtraction blocks are operable for generating the resolved symbol address according to one of a first structure and a second structure, wherein:

according to the first structure;

one of the addition blocks is coupled to each of the SYMBOL POINTER data registers for adding the value stored in the SYMBOL POINTER data register associated with a successful comparison to the corresponding bit of the string of compressed data bits, and

one of the subtraction blocks is coupled to each of the addition blocks and to the corresponding FIRSTCODE register and is operable in response to an input from the multiplexer to subtract the value stored in the FIRSTCODE data register associated with a successful comparison from a result of the associated addition block for generating the resolved symbol address; and

according to the second structure;

one of the subtraction blocks is coupled to each of the FIRSTCODE data registers for subtracting the value stored in the FIRSTCODE data register associated with a successful comparison from the string of compressed data bits in response to an input from the multiplexer, and

one of the addition blocks is coupled to each of the SYMBOL POINTER data registers for adding the value stored in the SYMBOL POINTER data register associated with a successful comparison to the result of the associated subtraction block for generating the resolved symbol address.

15. The device of claim 12, further comprising:

a memory device having stored therein a string of data bits compressed as canonical Huffman encoded data in a data file; and

a processor coupled to the memory device and operating a logic device;

wherein the coupling of the decompression device is further coupled to the memory for respectively receiving the data file and for outputting the resolved symbol.

16. The device of claim 15 wherein the decompression device further comprises a coupling for receiving an instruction from the processor.

18. The device of claim 17, further comprising a memory containing a canonical Huffman encoded data file, the memory being coupled to each of the plurality of FIRSTCODE registers for outputting the FIRSTCODE value associated therewith, and coupled to each of the plurality of SYMBOL POINTER registers for outputting the SYMBOL POINTER value associated therewith, and coupled to the multiplexer to receive the address and being structured to responsively output the resolved symbol associated with the received address.

19. The device of claim 17 wherein:

each of the plurality of subtraction blocks is coupled to a different one of the FIRSTCODE registers for subtracting the value of the successful FIRSTCODE register from the string of compressed data bits in response to an input from the multiplexer; and

each of the plurality of addition blocks each coupled to an output of the multiplexer and a different one of the SYMBOL POINTER registers, one of the addition blocks being associated with one of the SYMBOL POINTER registers corresponding to the successful FIRSTCODE register and being structured to add the value from the corresponding SYMBOL POINTER register to the result of the corresponding addition block and to output the address to the multiplexer.

12. A decompression device for decompressing a string of data bits compressed as canonical Huffman encoded data in a data file, wherein the data file includes (i) a string of compressed data bits, (ii) a FIRSTCODE data table, (iii) a SYMBOL POINTER data table, and (iv) a SYMBOL table, and wherein a relationship is fixed between data in the FIRSTCODE data table and the compressed data bits, and a relationship is fixed between the data in the FIRSTCODE data table and the data in a SYMBOL POINTER data table, the device comprising:

(a) a coupling structured for receiving a canonical Huffman encoded data file;

(b) a plurality of FIRSTCODE data registers coupled to receive and store data values from the FIRSTCODE data table portion of the data file;

(c) a plurality of SYMBOL POINTER data registers coupled to receive and store data values from the SYMBOL POINTER data table portion of the data file;

(d) a comparator coupled between each FIRSTCODE register and the string of compressed data bits for comparing the value stored in each FIRSTCODE data register with a corresponding bit of the string of compressed data bits;

(e) a multiplexer coupled to each comparator for determining a successful comparison result and responsively outputting a resolved symbol address associated therewith; and

(f) intercoupled addition and subtraction blocks coupled to the multiplexer and each of the SYMBOL POINTER data registers and the corresponding FIRSTCODE data registers for;

(i) adding the value stored in the SYMBOL POINTER data register associated with a successful comparison result to the corresponding bit of the string of compressed data bits,

(ii) subtracting the value stored in the FIRSTCODE data register associated with a successful comparison from the corresponding bit of the string of compressed data bits,

(iii) generating the resolved symbol address, and

(iv) outputting the resolved symbol address to the SYMBOL table portion of the data file for responsively outputting a corresponding resolved symbol.

17. A device for decompression of compressed data in a canonical Huffman encoded data file, wherein the data file includes:

a string of compressed data bits, a FIRSTCODE data table, a SYMBOL POINTER data table, and a SYMBOL table; and

wherein a relationship is fixed between FIRSTCODE and the compressed data bits according to FIRSTCODE[0] and bit 0, FIRSTCODE [1]and bits 0, 1, FIRSTCODE[2] and bits 0, 1, 2, through FIRSTCODE[N] and bits 0, 1, 2, . . . N; and

a relationship is fixed between FIRSTCODE and SYMBOL POINTER according to FIRSTCODE[0] and SYMBOL POINTER[0], FIRSTCODE[1] and SYMBOL POINTER[1], through FIRSTCODE[N] and SYMBOL POINTER[N], the device comprising;

a plurality of FIRSTCODE registers each having a FIRSTCODE value associated therewith;

a plurality of SYMBOL POINTER registers each having a SYMBOL POINTER value associated therewith;

a plurality of comparators each coupled to a different FIRSTCODE register to accept a FIRSTCODE value therefrom and coupled to accept a string of compressed data bits from a memory having compressed canonical Huffman encoded data stored therein, the comparators being structured to simultaneously compare the FIRSTCODE values with corresponding bits of the string of compressed data bits;

a multiplexer coupled to accept a result of each of the comparators, the multiplexer being structured to sequentially examine the results and to select a successful comparison result;

a plurality of addition blocks each coupled to an output of the multiplexer and a different one of the SYMBOL POINTER registers, one of the addition blocks being associated with one of the SYMBOL POINTER registers corresponding to one of the FIRSTCODE registers having the successful comparison result and being structured to add the value from the corresponding SYMBOL POINTER register to the string of compressed data bits;

a plurality of subtraction blocks each coupled to a different one of the FIRSTCODE registers and to one of the addition blocks corresponding to one of the FIRSTCODE registers, one of the subtraction blocks being associated with the FIRSTCODE register having the successful comparison result and being structured to subtract the value of the successful FIRSTCODE register from the result of the corresponding addition block and to output an address to the multiplexer; and

a SYMBOL table coupled to the multiplexer to receive the address, the SYMBOL table being structured to output a resolved symbol associated with the received address.

20. A method for decompression of canonical Huffman encoded data, the device comprising:

receiving a file of canonical Huffman encoded data, the file including a string of compressed canonical Huffman encoded data bits, a table of FIRSTCODE data values, a table of SYMBOL POINTER data values, and a table of resolved symbols;

storing the FIRSTCODE data values in FIRSTCODE data registers;

storing the SYMBOL POINTER data values in SYMBOL POINTER data registers;

comparing the FIRSTCODE data values with corresponding bits of the compressed data;

examining results of comparing the FIRSTCODE data values with corresponding bits of the compressed data to determine a match;

combining the bits of compressed data with one of the FIRSTCODE data values and one of the SYMBOL POINTER data values selected as a function of determining a match;

generating an address; and

outputting from the table of resolved symbols a symbol corresponding to the generated address.

21. The method of claim 20 wherein combining the bits of compressed data with one of the FIRSTCODE data values and one of the SYMBOL POINTER data values further comprises adding and subtracting of the bits of the compressed data and associated FIRSTCODE data values with associated SYMBOL POINTER data values.

22. The method of claim 20 wherein combining the bits of compressed data with one of the FIRSTCODE data values and one of the SYMBOL POINTER data values further comprises:

adding to the string of compressed data bits a SYMBOL POINTER data value associated with a successful result of comparing the FIRSTCODE data values with corresponding bits of the compressed data; and

subtracting a FIRSTCODE data value from a result of the adding.

23. The method of claim 22 wherein generating the address further comprises generating the address as a function of subtracting the FIRSTCODE data value from the result of the adding.

24. The method of claim 20 wherein combining the bits of compressed data with one of the FIRSTCODE data values and one of the SYMBOL POINTER data values further comprises:

subtracting a FIRSTCODE data value from the string of compressed data bits; and

adding a SYMBOL POINTER data value associated with a successful result of comparing the FIRSTCODE data values to a result of the subtracting.

25. The method of claim 24 wherein generating the address further comprises generating the address as a function of adding the SYMBOL POINTER data value to the result of the subtracting.

26. The method of claim 20 wherein generating an address further comprises generating an address as a function of combining the bits of compressed data with one of the FIRSTCODE data values and one of the SYMBOL POINTER data values.

27. The method of claim 20 wherein comparing the FIRSTCODE data values with corresponding bits of the compressed data further comprises simultaneously comparing two or more of the FIRSTCODE data values with corresponding bits of the compressed data.

28. The method of claim 20 wherein examining results of comparing the FIRSTCODE data values with corresponding bits of the compressed data further comprises sequentially examining a plurality of comparison results for a match between one of the FIRSTCODE data values and a corresponding one of the bits of the compressed data.

29. The method of claim 20, further comprising:

receiving an instruction from a processor to decompress a string of data bits as compressed canonical Huffman encoded data;

receiving the file of canonical Huffman encoded data from a memory associated with the processor; and

operating the method for decompression responsively to the instruction.

30. The method of claim 29, further comprising outputting the resolved symbols to the memory.