Decompressing dynamic huffman coded bit streams

• US 7,764,205 B2
• Filed: 08/26/2008
• Issued: 07/27/2010
• Est. Priority Date: 08/27/2007
• Status: Active Grant

• Current Assignee: Comtech EF Data (Comtech Telecommunications Corporation)
• Original Assignee: Comtech Aha Corporation (Comtech Telecommunications Corporation)
• Inventors: Owsley, Patrick A., Banister, Brian, Franklin, Jason, Sjoholm, Seth, Hungerford, Nathan, Coulter, Ed
• Primary Examiner(s): Nguyen; Linh V
• Application Number:
  US12/198,312
• Publication Number:
  US 20090058694A1
• Time in Patent Office: 700 Days
• Field of Search: 341/51, 341/63, 341/65, 341/67, 341/106
• US Class Current: 341/65
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A method and system for decompressing dynamic Huffman coded bit streams is disclosed.

Claims

1. A method, comprising:

receiving one or more input bits;

searching storage locations in a ternary content addressable memory (TCAM) for matches between the input bit or input bits and a code word;

determining if the input bit or input bits matches the code word stored in the TCAM;

locating a symbol stored in a memory corresponding to the matched code word;

outputting the symbol that corresponds to the matched code word;

outputting a length N of the code word that matches the input bit or input bits;

shifting the input bits by N bits, in response to the length of the code word, in order to expose the next potential code word match or literal in the input bits; and

receiving a state signal that indicates whether the input bit or input bits correspond to a Huffman coded symbol representing a distance or a length or a literal.

2. The method of claim 1, wherein a plurality of TCAMs operate simultaneously.

6. The method of claim 1, wherein the code words are for a dynamically generated Huffman code.

3. A method comprising:

receiving one or more input bits;

searching storage locations in a ternary content addressable memory (TCAM) for matches between the input bit or input bits and a code word;

determining if the input bit or input bits matches the code word stored in the TCAM;

locating a symbol stored in a memory corresponding to the matched code word;

outputting the symbol that corresponds to the matched code word;

outputting a length N of the code word that matches the input bit or input bits; and

shifting the input bits by N bits, in response to the length of the code word, in order to expose the next potential code word match or literal in the input bits, wherein each of the plurality of TCAMs output a symbol that corresponds to a respective matched code word, each individual TCAM outputs a length of the respective matched code word, and each of the plurality of TCAMs is supplied an input bit or input bits which are offset such that no two TCAMs receive the same input bits.

4. The method of claim 3, wherein one or more output lengths of the respective matched code words are added together to form a total shift length signal, the total shift length signal being fed back to shift the input bits by the length of the total shift length signal.

5. A method comprising:

receiving one or more input bits;

searching storage locations in a ternary content addressable memory (TCAM) for matches between the input bit or input bits and a code word;

determining if the input bit or input bits matches the code word stored in the TCAM;

locating a symbol stored in a memory corresponding to the matched code word;

outputting the symbol that corresponds to the matched code word;

outputting a length N of the code word that matches the input bit or input bits;

shifting the input bits by N bits, in response to the length of the code word, in order to expose the next potential code word match or literal in the input bits; and

receiving a state signal that indicates whether the input bit or input bits correspond to a Huffman coded symbol representing a distance or a length or a literal, wherein two Huffman codebooks are used, a first codebook being used to signal literals or lengths, and a second codebook being used to signal distances.

7. A method comprising:

receiving one or more input bits;

searching storage locations in a ternary content addressable memory (TCAM) for matches between the input bit or input bits and a code word;

determining if the input bit or input bits matches the code word stored in the TCAM;

locating a symbol stored in a memory corresponding to the matched code word;

outputting the symbol that corresponds to the matched code word;

outputting a length N of the code word that matches the input bit or input bits;

shifting the input bits by N bits, in response to the length of the code word, in order to expose the next potential code word match or literal in the input bits; and

receiving a state signal that indicates whether the input bit or input bits correspond to a Huffman coded symbol representing a distance or a length or a literal, wherein a plurality of TCAMs operate simultaneously and wherein the distance code word and the length code word are output in a same clock cycle, or a literal code word and a length code word are output in the same clock cycle, or two literal code words are output in the same clock cycle.

8. A method comprising:

receiving one or more input bits;

searching storage locations in a ternary content addressable memory (TCAM) for matches between the input bit or input bits and a code word;

determining if the input bit or input bits matches the code word stored in the TCAM;

locating a symbol stored in a memory corresponding to the matched code word;

outputting the symbol that corresponds to the matched code word;

outputting a length N of the code word that matches the input bit or input bits; and

shifting the input bits by N bits, in response to the length of the code word, in order to expose the next potential code word match or literal in the input bits, wherein the offset position into the input bits is selected for each TCAM according to the frequency of code words in a code book at each code word length.

9. A system, comprising:

a plurality of ternary content addressable memory (TCAM) that stores a code word and a symbol associated with the code word;

a plurality of decode logic modules that receives an address from one of the plurality of the TCAMs when one of the plurality of the TCAMs detects a match between an input bit or input bits and a code word; and

a shift length calculation module that receives as an output from the decode logic module a length of the code word;

wherein the shift length calculation module shifts the input bits by N bits, in response to the length of the code word, in order to expose the next potential code word match in the input bit or input bits; and

wherein the plurality of TCAMs and the plurality of decode logic modules operate simultaneously and in parallel, and the input bits of at least one of the TCAMs comprise a shifted version of the input bits of one of the plurality of TCAMs.

10. The system of claim 9, wherein each of the plurality of TCAMs output a symbol that corresponds to a respective matched code word, each individual TCAM outputs a length of the respective matched code word.

11. The system of claim 10, wherein each output length of the respective matched code words are combined in the shift length calculation module to form a total shift length signal, the total shift length signal being fed back to shift the input bits by the length of the total shift length signal.

12. The system of claim 9, further comprising receiving a state signal that indicates whether the input bit or input bits correspond to a distance or a length or a literal.

13. The system of claim 9, wherein the code words are dynamic Huffman codes.

15. The system of claim 9, wherein an offset into the input bits is chosen for the TCAM based upon a weighting according to the length of the code words.

16. The system of claim 9, wherein the TCAM output is tied directly to a random access memory.

14. A system comprising:

a plurality of ternary content addressable memories (TCAMs) configured to store a code word and a symbol associated with the code word;

a decode logic module that receives an address from one of the plurality of TCAMs when the TCAMs detect a match between an input bit or input bits and a code word;

a shift length calculation module that receives as an output from the decode logic module one or more lengths of the one or more code words; and

wherein the shift length calculation module shifts the input bits by N bits, in response to the length of the one or more code words, in order to expose the next potential code word match in the input bit or input bits;

wherein a distance code word and a length code word are output in a same clock cycle, or a literal code word and a length code word are output in the same clock cycle, or two literal code words are output in the same clock cycle; and

wherein the plurality of TCAMs operate simultaneously and in parallel, and the input bits of at least one of the plurality of TCAMs comprise a shifted version of the input bits of one of the plurality of TCAMs.

17. A system comprising:

a plurality of ternary content addressable memories (TCAMs) configured to store a code word and a symbol associated with the code word;

wherein the plurality of TCAMs operate simultaneously and in parallel, and the input bits of at least one of the plurality of TCAMs comprise a shifted version of the input bits of one of the plurality of TCAMs; and

wherein the outputs of a plurality of TCAMs is used to decode a plurality of sequentially coded symbols in the same clock cycle.