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 determining a length of a variable-length codeword in a stream of data bits, the method comprising:
accessing a data window comprising at least 9 bits of the data stream;
reading data from a first memory configured to detect codewords in the data window comprising from 0 to 6 bits, wherein the first memory is accessed using a first memory address comprising 6 bits of the data window;
reading data from a second memory configured to detect codewords in the data window comprising from 7 to 9 bits, wherein the second memory is accessed using a second memory address comprising 9 bits of the data window; and
determining which one of the memories comprises data indicating detection of a codeword in the data window.
2. The method of claim 1 , wherein the data window comprises at least 11 bits of the stream of data bits and the method further comprises:
reading data from a third memory configured to detect codewords in the data window comprising from 10 to 11 bits, wherein the third memory is accessed using a third memory address comprising 10 bits of the data window.
3. The method of claim 2 , wherein the data window comprises at least 14 bits of the stream of data bits and the method further comprises:
reading data from a fourth memory configured to detect codewords in the data window comprising from 12 to 14 bits, wherein the fourth memory is accessed using a fourth memory address comprising 11 bits of the data window.
4. The method of claim 3 , wherein the data window comprises at least 16 bits of the stream of data bits and the method further comprises:
reading data from a fifth memory configured to detect codewords in the data window comprising from 15 to 16 bits, wherein the fifth memory is accessed using a fifth memory address comprising 10 bits of the data window.
5. The method of claim 4 , wherein the first, second, third, fourth, and fifth memories are accessed concurrently using respective memory addresses comprising bits of the same data window.
6. A method of determining a length of a variable-length codeword in a stream of data bits, the method comprising:
receiving a predetermined quantity of data bits of the data stream;
reading data from each of a plurality of memories, the data being read from different memory addresses of each memory, wherein each different memory address corresponds with a different quantity of the data bits; and
determining which one of said different memory addresses comprises data regarding a length of a variable length codeword within the predetermined quantity of data bits.
7. The method of claim 6 , wherein at least some of the plurality of memories are included in an application specific integrated circuit.
8. The method of claim 6 , wherein each of the plurality of memories is embodied in a single physical memory device.
9. The method of claim 6 , wherein at least some of the plurality of memories each comprise a Random Access Memory (RAM).
10. The method of claim 6 , wherein a Field Programmable Gate Array (FPGA) comprises one or more of said plurality of memories.
11. The method of claim 6 , wherein one or more of said variable-length codewords comprises a Huffman code.
12. The method of claim 6 , wherein one or more of said variable-length codewords comprises a Lempel-Ziv code.
13. An apparatus for determining a variable length code length in a digital data stream, the apparatus comprising:
a first data structure storing a first possible result data corresponding to a variable length code in the data stream, the first possible result data being stored at a first address of the first data structure, the first address comprising exactly N bits of the data stream; and
a second data structure storing a second possible result data corresponding to the variable length code, the second possible result data being stored at a second address of the second data structure, the second address comprising the same N bits of the data stream and an additional M bits of the data stream, where M is one or more.
14. The apparatus of claim 13 , wherein the first possible result data indicates a length of a variable length code in the data stream and the second possible result data comprises a null code.
15. The apparatus of claim 13 , wherein the second possible result data indicates a length of a variable length code in the data stream and the first possible result data comprises a null code.
16. The apparatus of claim 13 , wherein the variable length code comprise at least one of: GZIP, PKZIP, DEFLATE, LZH and RAR encoded data.
17. The apparatus of claim 13 , further comprising:
a third data structure storing a third possible result data at a third address, the third address being identified by at least N−1 of the same N bits of the data stream and at least M+1 additional bits of the data stream.
18. The apparatus of claim 17 , wherein only one of the first, second and third possible result data indicate a length of a variable length code in the data stream.
19. A method of determining a length of a variable-length codeword in a stream of data bits, the method comprising:
accessing a data window comprising a number of bits of the stream of data bits;
concurrently reading data from each of a plurality of memories, the data being concurrently read from different memory addresses of each memory, wherein each different memory address corresponds with a different quantity of data bits in the data window; and
determining which of said different memory addresses comprises data regarding a length of a variable length codeword within the data window.
20. The method of claim 19 , wherein the concurrent reading of data from each of the plurality of memories begins during a common clock cycle.
21. The method of claim 19 , wherein the concurrent reading of data from each of the plurality of memories is performed in a single clock cycle.
22. The apparatus of claim 13 , wherein the apparatus comprises one or more of an application specific integrated circuit, a field programmable gate array, and a network interface card.