Low memory and MIPS efficient technique for decoding Huffman codes using multi-stage, multi-bits lookup at different levels
View Patent ↗Present herein is a low memory and MIPS efficient technique for decoding Huffman codes using multi-stage, multi-bits lookup at different levels. A binary tree is cut at levels depending on the quotient of the number of existing nodes and the number of possible nodes.
1. A method for storing a variable length code table in a memory, said method comprising:
(a) calculating a value for each of at least one levels of a binary tree;
(b) comparing the value for each of the at least one levels of the binary tree to a threshold; and
(c) generating at least one new binary tree from a particular one of the at least one levels, if the threshold exceeds the value for the particular one of the at least one levels.
2. The method of claim 1 , further comprising:
performing (a)–(c) for each new binary tree generated during (c).
3. The method of claim 1 , further comprising:
(d) associating a memory location for each possible bit combination for the particular one of the at least one levels.
4. The method of claim 3 , further comprising:
performing (a)–(d) for each new binary tree generated during (c).
5. The method of claim 2 , further comprising:
(e) storing a particular one of a plurality of symbols in each memory location associated with a bit combination associated with a data path along the binary tree that leads to the particular one of the plurality of symbols.
6. The method of claim 5 , further comprising:
(f) storing a link to a particular one of the at least one new binary tree in each memory location associated with a bit combination associated with a data path along the binary tree that leads to the particular one of the at least one of the new binary trees.
7. The method of claim 6 , further comprising:
performing (a)–(f) for each new binary generated during (c).
8. The method of claim 6 , further comprising:
(g) storing a particular one of the plurality of symbols in each memory location associated with a bit combination, wherein the particular one of the plurality of symbols matches a prefix of the bit combination.
9. The method of claim 8 , further comprising:
performing (a)–(g) for each new binary generated during (c).
10. An article of manufacture comprising a computer readable medium, wherein the computer readable medium stores a plurality of instructions, wherein execution of the plurality of instructions causes:
(a) calculating a value for each of at least one levels of a binary tree;
(b) comparing the value for each of the at least one levels of the binary tree to a threshold; and
(c) generating at least one new binary tree from a particular one of the at least one levels, if the threshold exceeds the value for the particular one of the at least one levels.
11. The article of manufacture of claim 10 , wherein execution of the plurality of instructions also causes:
performing (a)–(c) for each new binary tree generated during (c).
12. The article of manufacture of claim 10 , wherein execution of the plurality of instructions also causes:
(d) associating a memory location for each possible bit combination for the particular one of the at least one levels.
13. The article of manufacture of claim 12 , wherein execution of the plurality of instructions also causes:
performing (a)–(d) for each new binary tree generated during (c).
14. The article of manufacture of claim 12 , wherein execution of the plurality of instructions also causes:
(e) storing a particular one of a plurality of symbols in each memory location associated with a bit combination associated with a data path along the binary tree that leads to the particular one of the plurality of symbols.
15. The article of manufacture of claim 14 , wherein execution of the plurality of instructions also causes:
(f) storing a link to a particular one of the at least one new binary tree in each memory location associated with a bit combination associated with a data path along the binary tree that leads to the particular one of the at least one of the new binary trees.
16. The article of manufacture of claim 15 , wherein execution of the plurality of instructions also causes:
performing (a)–(f) for each new binary generated during (c).
17. The article of manufacture of claim 15 , wherein execution of the plurality of instructions also causes:
(g) storing a particular one of the plurality of symbols in each memory location associated with a bit combination, wherein the particular one of the plurality of symbols matches a prefix of the bit combination.
18. The article of manufacture of claim 17 , wherein execution of the plurality of instructions also causes:
performing (a)–(g) for each new binary generated during (c).