Huffman tree decompression

Patent metadata

Field	Value
Publication number	US-9787323-B1
Application number	US-201715474748-A
Country	US
Kind code	B1
Filing date	Mar 30, 2017
Priority date	Dec 11, 2016
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

To decompress encoded data, a Huffman code tree stored in a data header may need to be decompressed and rebuilt. A bit length histogram table is used in a hardware design to more efficiently decompress the Huffman code tree. The bit length histogram table relates each bit length used by the Canonical Huffman Code (CHC) symbols to a corresponding number of symbols in the encoding that have that bit length. Performing decompression using bit length histogram table allows part of the Huffman tree decompression to be performed in a single pass.

First claim

What is claimed is:

1. An integrated circuit to decode data compressed with a variable length code expressed in canonical form, comprising:
storage elements for a first table to associate a plurality of unencoded symbols to a corresponding plurality of coded symbol bitlengths, each of the plurality of coded symbol bitlengths corresponding to a count of bits used by the variable length code to encode a corresponding unencoded symbol;
storage elements for a second table that associates each of the corresponding plurality of bitlengths to a respective starting index;
circuitry to generate the second table;
circuitry to store the second table in the storage elements for the second table;
storage elements for a decode lookup table;
circuitry to generate the decode lookup table based on the first table and the second table; and,
circuitry to store the decode lookup table in the storage elements for the decode lookup table.

2. The integrated circuit of claim 1 , further comprising:
storage elements for a third table that associates each of the corresponding plurality of bitlengths to a respective number of unencoded symbols having a respective coded symbol bitlength;
circuitry to generate the third table based on the first table; and,
circuitry to store the third table in the storage elements for the third table.

3. The integrated circuit of claim 2 , wherein the second table is generated based on the third table.

4. The integrated circuit of claim 1 , the canonical form corresponds to a canonical Huffman code.

5. The integrated circuit of claim 1 , further comprising:
circuitry to receive a coded symbol; and,
decode circuitry to, based on the coded symbol, the second table, and the decode lookup table, select an unencoded symbol from the that corresponds to the coded symbol.

6. The integrated circuit of claim 5 , further comprising:
storage elements for a fourth table that associates each of the corresponding plurality of bitlengths to a respective base code symbol; and,
circuitry to generate the fourth table based on the first table.

7. The integrated circuit of claim 6 , further comprising:
circuitry to receive a coded symbol; and,
circuitry to select an unencoded symbol value from the decode lookup table based on the coded symbol and an index value stored in the fourth table.

8. A method of generating a decode lookup table to decode a variable length code expressed in canonical form, comprising:
receiving a first table that associates a plurality of unencoded symbols to a corresponding plurality of coded symbol bitlengths, each of the plurality of coded symbol bitlengths corresponding to a count of bits used by the variable length code to encode a corresponding unencoded symbol;
generating a second table that associates each of the corresponding plurality of bitlengths to a respective starting index; and,
generating the decode lookup table based on the first table and the second table.

9. The method of claim 8 , further comprising:
based on the first table, generating a third table that associates each of the corresponding plurality of bitlengths to a respective number of unencoded symbols having a respective coded symbol bitlength.

10. The method of claim 9 , wherein the second table is based on the third table.

11. The method of claim 8 , wherein the canonical form corresponds to a canonical Huffman code.

12. The method of claim 8 , further comprising:
receiving a coded symbol; and,
based on the coded symbol, the second table, and the decode lookup table, decoding the coded symbol by selecting an unencoded symbol from the symbol lookup table that corresponds to the coded symbol.

13. The method of claim 12 , wherein selecting the unencoded symbol comprises:
generating a fourth table that associates each of the corresponding plurality of bitlengths to a respective base code symbol.

14. The method of claim 13 , further comprising:
receiving a coded symbol;
using a coded symbol bitlength associated with the coded symbol and the fourth table to generate an index into the decode lookup table; and,
based on the index, selecting an unencoded symbol from the decode lookup table that corresponds to the coded symbol.

15. An integrated circuit to decompress data compressed with a variable length coding scheme, comprising:
decompression circuitry to receive the compressed data and to, based on a symbol lookup table, produce decompressed data; and,
table decompression circuitry to receive a representation of the symbol lookup table, the representation of the symbol lookup table including a plurality of coded symbol bitlengths corresponding to a count of bits used by the variable length coding to encode a corresponding unencoded symbol, the table decompression circuitry to produce a symbol lookup table suitable for decoding from the representation of the symbol lookup table by at least:
generating a cumulative histogram table that associates each of the corresponding plurality of bitlengths to a respective starting index in the symbol lookup table; and,
generating the symbol lookup table based on the representation of the symbol lookup table and the cumulative histogram table.

16. The integrated circuit of claim 15 , wherein the table decompression circuitry further:
generates, based on the representation of the symbol lookup table, a histogram table that associates each of the corresponding plurality of bitlengths to a respective number of unencoded symbols having a respective coded symbol bitlength.

17. The integrated circuit of claim 16 , wherein the table decompression circuitry further:
generates, based on the representation of the symbol lookup table, a base code table that associates each of the corresponding plurality of bitlengths to a respective base code symbol in the symbol lookup table.

18. The integrated circuit of claim 17 , wherein the representation of the symbol lookup table is stored in a bitlength table that associates the plurality of unencoded symbols to the corresponding plurality of coded symbol bitlengths.

19. The integrated circuit of claim 18 , wherein the table decompression circuitry processes multiple entries in the bitlength table concurrently.

20. The integrated circuit of claim 15 , wherein the symbol lookup table of the variable length coding scheme represents a canonical Huffman tree.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Havlik Robert W
• Erickson Michael J
• Vattakandy Amar
• Gladding Derek E

Classifications

• H03M7/425 Primary

  for the decoding process only · CPC title

• H03M7/6011

  Encoder aspects · CPC title

• H03M7/6005

  Decoder aspects · CPC title

• H03M7/4037

  Prefix coding · CPC title

• H03M7/40

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title