Parallelized dynamic Huffman decoder
View Patent ↗Several code detectors in parallel simultaneously examine varying overlapping segments of a data stream containing variable length codes, referred to as a data window. The data window segments directly address memory structures within each of the code detectors without any previous logic stages. Each code detector is responsible for a range of code lengths, and ignores data window bits that are not relevant to its code length range. Each code detector outputs a possible result to a layer of logic that selects the possible result of the single code detector which contains result data corresponding to a variable length code in the data window.
1. A method of decoding a plurality of variable-length codewords in a stream of data bits, the method comprising:
presenting at a plurality of code detectors a data window comprising a number of bits of said stream of data bits;
reading data from each of a plurality of memories that are associated with respective code detectors, the data being read from different memory addresses of each memory, wherein each different memory address corresponds with a different, partially overlapping, portion of the data window;
outputting a possible result from each of said plurality of code detectors, the possible results each comprising the data read from the code detector's respective memories; and
determining which of said plurality of possible results comprises an actual result, wherein said actual result comprises a length of a codeword in said number of bits of said stream of data bits.
2. The method of claim 1 , wherein said length of said codeword is a length of a variable-length codeword.
3. The method of claim 1 , wherein said length of said codeword is a length of a variable-length codeword and associated extra bits.
4. The method of claim 1 , wherein each of said plurality of memories comprises a Random Access Memory (RAM).
5. The method of claim 1 , wherein a Field Programmable Gate Array (FPGA) comprises one or more of said plurality of memories.
6. The method of claim 1 , further comprising:
shifting said data window by said length of said codeword; and
repeating said steps of presenting, reading, outputting, determining, and shifting.
7. The method of claim 1 , wherein said number of bits of said stream of data bits is greater than or equal to a longest possible codeword length.
8. The method of claim 1 , wherein one or more of said variable-length codewords comprises a Huffman code.
9. The method of claim 1 , wherein one or more of said variable-length codewords comprises a distance code.
10. The method of claim 1 , wherein one or more of said variable-length codewords comprises a length code.
11. The method of claim 1 , wherein one or more of said variable-length codewords comprises a Lempel-Ziv code.
12. The method of claim 1 , wherein one or more of said variable-length data blocks comprises extra bits.
13. The method of claim 1 , further comprising:
receiving a codeword and a corresponding decoded code; and
writing said decoded code to one of said plurality of memory devices at an address corresponding to said codeword.
14. The method of claim 13 , further comprising writing a null code at said address corresponding to said codeword after each of said plurality of variable length codewords has been presented at said plurality of code detectors.
15. The method of claim 1 , wherein at least one of said plurality of memory devices stores two or more decode trees.
16. The method of claim 1 , wherein a first of said plurality of code detectors is configured to decode codewords comprising from 1 to 5 bits.
17. The method of claim 16 , wherein a second of said plurality of code detectors is configured to decode codewords comprising from 6 to 8 bits.
18. The method of claim 17 , wherein a third of said plurality of code detectors is configured to decode codewords comprising from 9 to 10 bits.
19. The method of claim 18 , wherein a fourth of said plurality of code detectors is configured to decode codewords comprising from 11 to 13 bits.
20. The method of claim 19 , wherein a fifth of said plurality of code detectors is configured to decode codewords comprising from 14 to 15 bits.
21. The method of claim 1 , wherein said codewords comprise at least one of: GZIP, PKZIP, DEFLATE, LZH and RAR encoded data.
22. The method of claim 1 , wherein each of said addresses comprises one or more bits of said data window.
23. A system for determining a plurality of lengths corresponding to a plurality of Huffman codes in a received bitstream, the system comprising:
a first code detector configured to access exactly N bits of said bitstream, wherein said first code detector is configured to decode Huffman codes having a first range of bit lengths;
a second code detector configured to access more than N bits of said bitstream, wherein said second code detector is configured to decode Huffman codes having a second range of bit lengths, the second range comprising bit lengths that are not included in the first range, and wherein the decoding operations performed by the first code detector and the second code detector are in response to at least the same N bits of the bitstream;
a tree builder coupled to the first and second code detectors and configured to selectively write a plurality of decoded codewords to at least one of said first and second code detectors; and
a select module coupled to said first and second code detectors and configured to receive a first output from said first code detector and a second output from said second code detector and determine which of said outputs corresponds with a Huffman code.
24. The system of claim 23 , wherein said first range and said second range are mutually exclusive.
25. The system of claim 23 , further comprising a shifter configured to receive a digital data stream comprising said plurality of Huffman codes and configured to make portions of said plurality of Huffman codes available for access by said first and second code detectors.
26. The system of claim 23 , wherein said output that corresponds with said Huffman code comprises an indication of a length of said Huffman code.
27. The system of claim 23 , wherein one of said outputs from said first and second code detectors comprises a valid flag indicating that said one of said outputs corresponds with a Huffman code.
28. The system of claim 23 , wherein said output that corresponds with said Huffman code comprises an indication of a number of extra bits associated with said Huffman code.
29. The system of claim 23 , wherein said output that corresponds with said Huffman code comprises an indication of a sum of a length of said Huffman code and a number of extra bits associated with said Huffman code.
30. The system of claim 23 , wherein said output that corresponds with said Huffman code comprises an indication of a type of symbol that was coded.
31. The system of claim 23 , wherein said output that corresponds with said Huffman code comprises a literal symbol.
32. An apparatus for decoding a variable length code comprising:
a first memory storing a result data corresponding to a variable length code at a first address comprising a first number of bits in a data block; and
a second memory storing a null code at a second address comprising a second number of bits in said data block, wherein said first address and said second address comprise one or more common bits in said data block,
wherein a plurality of addresses in said first memory each store the result data, wherein said plurality of addresses are N bit addresses, said first address is a N-1 bit address, and N-1 bits of said first address and said plurality of addresses are equal.
33. The apparatus of claim 32 , wherein said plurality of addresses comprises:
addresses where a predetermined bit is set to one and said remaining N-1 bits are equal to said first address; and
addresses where said predetermined bit is set to zero and said remaining N-1 bits are equal to said first address.