Parallel huffman decoder

Patent metadata

Field	Value
Publication number	US-9252805-B1
Application number	US-201514672135-A
Country	US
Kind code	B1
Filing date	Mar 28, 2015
Priority date	Mar 28, 2015
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

A main data input and a lookahead input are held in a holding register. Consecutive overlapping portions of the main data input and the lookahead input are provided to a plurality, M, of half-decoders, which include a subset of frequently-occurring code words of a Huffman code. When no code word not available in the half-decoders is encountered, the half-decoders decode, in parallel, in a single clock cycle, M of the frequently-occurring code words. When a code word not available in the half-decoders is encountered, input intended for a corresponding one of the half-decoders, which input includes the code word not available in the corresponding one of the half-decoders, is applied to an input of a full decoder implemented in ternary content-addressable memory. The full decoder includes all code words of the Huffman code.

First claim

What is claimed is:

1. A parallel Huffman data decoder for decoding data encoded in accordance with a Huffman code, said parallel Huffman data decoder comprising:
a holding register having a main portion holding a main data input, a lookahead portion holding a lookahead input, and a plurality of outputs;
a plurality, M, of half-decoders, each having an input coupled to a corresponding one of said plurality of outputs of said holding register, and an output, said inputs each obtaining from said outputs of said holding register consecutive overlapping portions of data in said main portion and said lookahead portion of said holding register;
a full decoder implemented in ternary content-addressable memory, said full decoder having an input selectively connectable to obtain a given one of said overlapping portions of data, and an output;
a decoder selection and sequencing unit having a plurality of inputs coupled to said outputs of said half-decoders and said output of said full decoder, a selection output that controls said selective connection of said full decoder input, and a plurality of output lanes;
wherein:
said full decoder includes all code words of said Huffman code;
said half-decoders includes a subset of frequently-occurring code words of said Huffman code;
said half-decoders decode, in parallel, in a single clock cycle, when no code word not available in said half-decoders is encountered, M of said frequently-occurring code words; and
when a code word not available in said half-decoders is encountered, said decoder selection and sequencing unit causes to be applied to said input of said full decoder, input intended for a corresponding one of said half-decoders, which input includes said code word not available in said corresponding one of said half-decoders.

2. The parallel Huffman data decoder of claim 1 , wherein said half-decoders are implemented in a less expensive technology than said ternary content-addressable memory.

3. The parallel Huffman data decoder of claim 2 , wherein said less expensive technology comprises static random access memory.

4. The parallel Huffman data decoder of claim 2 , wherein said less expensive technology comprises dynamic random access memory.

5. The parallel Huffman data decoder of claim 1 , further comprising a lookahead register having a data input to obtain a data stream, and having an output coupled to said main portion of said holding register, wherein said holding register obtains said lookahead input by tapping said data stream and bypassing said lookahead register.

6. The parallel Huffman data decoder of claim 1 , further comprising a multiplexer having a first input coupled to said holding register, a selection input, and an output coupled to said input of said full decoder, wherein said decoder selection and sequencing unit causes to be applied to said input of said full decoder, said input intended for said corresponding one of said half-decoders, which input includes said code word not available in said corresponding one of said half-decoders, by sending a selection signal to said selection input.

7. The parallel Huffman data decoder of claim 1 , wherein said overlapping portions of data overlap by one bit.

8. A design structure tangibly embodied in a non-transitory machine readable medium for designing, manufacturing, or testing an integrated circuit, the design structure comprising a parallel Huffman data decoder for decoding data encoded in accordance with a Huffman code, said parallel Huffman data decoder in turn comprising:
a holding register having a main portion holding a main data input, a lookahead portion holding a lookahead input, and a plurality of outputs;
a plurality, M, of half-decoders, each having an input coupled to a corresponding one of said plurality of outputs of said holding register, and an output, said inputs each obtaining from said outputs of said holding register consecutive overlapping portions of data in said main portion and said lookahead portion of said holding register;
a full decoder implemented in ternary content-addressable memory, said full decoder having an input selectively connectable to obtain a given one of said overlapping portions of data, and an output;
a decoder selection and sequencing unit having a plurality of inputs coupled to said outputs of said half-decoders and said output of said full decoder, a selection output that controls said selective connection of said full decoder input, and a plurality of output lanes;
wherein:
said full decoder includes all code words of said Huffman code;
said half-decoders includes a subset of frequently-occurring code words of said Huffman code;
said half-decoders decode, in parallel, in a single clock cycle, when no code word not available in said half-decoders is encountered, M of said frequently-occurring code words; and
when a code word not available in said half-decoders is encountered, said decoder selection and sequencing unit causes to be applied to said input of said full decoder, input intended for a corresponding one of said half-decoders, which input includes said code word not available in said corresponding one of said half-decoders.

9. The design structure of claim 8 , wherein, in said parallel Huffman data decoder, said half-decoders are implemented in a less expensive technology than said ternary content-addressable memory.

10. The design structure of claim 9 , wherein, in said parallel Huffman data decoder, said less expensive technology comprises static random access memory.

11. The design structure of claim 9 , wherein, in said parallel Huffman data decoder, said less expensive technology comprises dynamic random access memory.

12. The design structure of claim 8 , wherein said parallel Huffman data decoder further comprises a lookahead register having a data input to obtain a data stream, and having an output coupled to said main portion of said holding register, wherein said holding register obtains said lookahead input by tapping said data stream and bypassing said lookahead register.

13. The design structure of claim 8 , wherein said parallel Huffman data decoder further comprises a multiplexer having a first input coupled to said holding register, a selection input, and an output coupled to said input of said full decoder, wherein said decoder selection and sequencing unit causes to be applied to said input of said full decoder, said input intended for said corresponding one of said half-decoders, which input includes said code word not available in said corresponding one of said half-decoders, by sending a selection signal to said selection input.

14. The design structure of claim 8 , wherein, in said parallel Huffman data decoder, said overlapping portions of data overlap by one bit.

15. A method for decoding, in parallel, data encoded in accordance with a Huffman code, said method comprising:
holding in a holding register a main data input and a lookahead input;
providing to a plurality, M, of half-decoders, consecutive overlapping portions of said main data input and said lookahead input, said half-decoders including a subset of frequently-occurring code words of said Huffman code;
when no code word not available in said half-decoders is encountered, decoding, in parallel, in a single clock cycle, M of said frequently-occurring code words;
when a code word not available in said half-decoders is encountered, applying to an input of a full decoder implemented in ternary content-addressable memory, input intended for a corresponding one of said half-decoders, which input includes said code word not available in said corresponding one of sa

Assignees

• IBM

Inventors

• Abali Bulent
• Blaner Bartholomew

Classifications

• H03M7/40 Primary

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

• H03M7/4037 Primary

  Prefix coding · CPC title

• H03M7/6005

  Decoder aspects · CPC title

• H03M7/6023

  Parallelization · CPC title