VLSI efficient Huffman encoding apparatus and method

1. An electronic device, comprising:

a canonical Huffman coding component configured to generate a first canonical Huffman code of a plurality of literals in a data file, the first canonical Huffman coding including a code length for each literal of the plurality of literals, the code lengths being arranged in an order; and

a length component configured to:

set all code lengths greater than a threshold value equal to the threshold value to obtain a second canonical Huffman code;

determine a benchmark code that is a largest code length lower than the threshold value that, when incremented, causes an overflow probability of the second canonical Huffman coding to be greater than or equal to one; and

increment an adjusted code by one to generate a third canonical Huffman code, the adjusted code having a length less than the benchmark code.

2. The electronic device of claim 1 , wherein the canonical Huffman coding component is further configured to generate the first canonical Huffman code of the plurality of literals without a length limitation.

3. The electronic device of claim 1 , further comprising a Huffman coding component configured to code the data file according to the third canonical Huffman coding.

4. The electronic device of claim 1 , wherein the length component is further configured to generate the third canonical Huffman code by movement of the adjusted code such that the adjusted code is in canonical order for the literal corresponding to the adjusted code.

5. The electronic device of claim 4 , wherein the length component is further configured to move the adjusted code such that the adjusted code is in canonical order by a shift of the adjusted code in a particular direction until the adjusted code is in canonical order.

6. The electronic device of claim 5 , wherein the length component is further configured to move the adjusted code such that code lengths of the third Huffman code having equal lengths are in alphabetical order.

7. A method for compression, comprising:

generating, by a first very large scale integrated (VLSI) circuit configured to perform canonical Huffman coding, a first canonical Huffman code of a plurality of literals in a data file, the first canonical Huffman coding including a code length for each literal of the plurality of literals, the code lengths being arranged in order;

setting, by a second VLSI circuit configured to perform canonical Huffman coding, all code lengths greater than a threshold value equal to the threshold value to obtain a second canonical Huffman code;

determining, by the second VLSI circuit, a benchmark code that is a largest code length lower than the threshold value that when incremented by one causes an overflow probability of the second canonical Huffman coding to be greater than or equal to one; and

incrementing, by the second VLSI circuit, an adjusted code by one to generate a third canonical Huffman code, the adjusted code having a length less than the benchmark code.

8. The method of claim 7 , further comprising, Huffman coding, by a third VLSI circuit configured to perform Huffman coding, the data file according to the third canonical Huffman coding.

9. The method of claim 7 , wherein generating the third canonical Huffman code further comprises moving the adjusted code such that the adjusted code is in canonical order for the literal corresponding to the adjusted code.

10. The method of claim 9 , wherein moving the adjusted code such that the adjusted code is in canonical order comprises, shifting the adjusted code in a particular direction until the adjusted code is in canonical order.

11. The method of claim 10 , wherein code lengths of the third Huffman code having equal lengths are in alphabetical order.

12. An electronic device comprising:

a statistic generating component configured to generate usage statistics for a plurality of literals of an input data file;

a canonical Huffman coding component configured to generate a first canonical Huffman code for the plurality of literals based on the usage statistics, the first Huffman code including a plurality of first Huffman code lengths;

a length component configured to transform the first Huffman code lengths into second Huffman code lengths having a longest code of length N, N being smaller than a longest Huffman code length of the first Huffman code lengths; and

a Huffman coding component configured to Huffman code the data file according to the second Huffman code lengths.

13. The electronic device of claim 12 , wherein the canonical Huffman coding component is further configured to generate the first Huffman code lengths for the plurality of literals without first sorting the usage statistics.

14. The electronic device of claim 12 , wherein the canonical Huffman coding component is further configured to generate the first Huffman code lengths for the plurality of literals by execution of instructions to:

assign a map value I(i) to each literal S(i), the map value assigned sequentially to each literal S(i) in the data set; and

determine a plurality counts P(i), i=1 to N, each corresponding to a literal S(i).

15. The electronic device of claim 14 , wherein the canonical Huffman coding component is further configured to:

find two literals S(a) and S(b) of the plurality of literals S(i) having lowest corresponding counts P(a) and P(b) of the plurality of frequency metrics P(i); and

sum the frequency metrics P(a) and P(b) to obtain a sum Pt.

16. The electronic device of claim 15 , wherein the canonical Huffman coding component is further configured to execute instructions to:

determine a smaller map value I(min) of the map values I(a) and I(b) assigned to literals I(a) and I(b) and a larger map value I(max) of the map values I(a) and I(b);

change one of I(a) and I(b) to be equal to the smaller map value; and

set a count P(min) of the plurality of counts corresponding to the smaller map value I(min) equal to Pt.

17. The electronic device of claim 16 , wherein the canonical Huffman coding component is further configured to execute instructions to:

set a count P(max) of the plurality of counts corresponding to I(max) equal to zero; and

increment bit lengths L(a) and L(b) corresponding to literals S(a) and S(b).

18. The electronic device of claim 17 , wherein the canonical Huffman coding component is further configured to execute instructions to:

determine whether all of the map values I(0) are equal to zero; and

repeat the find action through the increment until all of map values I(i) are equal to zero.

19. The electronic device of claim 12 , wherein the length component is configured to transform the first Huffman code lengths into the second Huffman code lengths having a longest code of length N, N being smaller than a longest Huffman code length of the first Huffman code lengths by execution of instructions to:

set all first Huffman code lengths greater than a threshold value equal to the threshold value to obtain an intermediate canonical Huffman code;

determine a benchmark code that is a largest code length lower than the threshold value that when incremented by one causes an overflow probability of the intermediate canonical Huffman coding to be greater than or equal to one; and

increment an adjusted code by one to generate the second canonical Huffman code, the adjusted code having a length one less than the benchmark code.

20. The electronic device of claim 12 , wherein:

the statistic generating component is a very large scale integrated (VLSI) circuit configured to perform statistical operations;

the canonical Huffman coding component and the length component are VLSI circuits configured to perform canonical Huffman coding; and

the Huffman coding component is a VLSI circuit configured to perform Huffman coding.