Apparatus and method for decoding Huffman codes using leading one/zero string length detection

• US 6,563,440 B1
• Filed: 10/19/2001
• Issued: 05/13/2003
• Est. Priority Date: 10/19/2001
• Status: Expired due to Fees

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Kangas, Janne
• Primary Examiner(s): YOUNG, BRIAN K
• Application Number:
  US10/045,693
• Time in Patent Office: 571 Days
• Field of Search: 341/67, 341/65, 341/63, 341/59
• US Class Current: 341/65
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

Decoding Huffman codes is accomplished by identifying consecutive strings of high order ones or zeroes and following consecutive strings of high order ones or zeroes, retrieving a table entry for each string based on its run count and bit value, until the retrieved entry contains the decoding output symbol, or until the remaining bits of the code word number within a predetermined threshold. The remaining bits are used as an offset into a lookup table, but the dimensions of the table have been reduced through elimination of the leading ones and zeroes. The consecutive strings are preferably processed by a hardware accelerator to identify the repeated bit, count the bits in the string and return this information to the host processor. The efficiencies of decoding canonical codes are realized; yet, non-canonical codes can be decoded.

Claims

1. A method for decoding a code word in a series of variable length code words comprising the steps of:

a) detecting the value of a bit in said code word;

b) calculating a current count that starts with said bit and includes, from said series of variable length code words, subsequent, consecutive bits of the same value;

c) based on the current count, retrieving an entry from a decoding table; and

d) based on the retrieved entry, determining whether steps a) through d) are to be repeated for said code word using bits subsequent to those included in the one or more counts in step b).

2. The method of claim 1, wherein, if it is determined in step d) that steps a) through d) are not to be repeated, step d) further comprises determining whether the entry last retrieved contains an output symbol that constitutes a decoding of said code word, and, if not, retrieving, based on at least one bit subsequent to those counted in step b), from a decoding table an entry that contains an output symbol that constitutes a decoding of said code word.

3. The method of claim 1, wherein step d) further includes the step of detecting whether the retrieved entry contains a symbol found indicator, and wherein said detection of said symbol found indicator indicates that steps a) through d) are not to be repeated for said code word.

4. The method of claim 1, wherein step d) further includes the step of detecting whether the retrieved entry contains a branching indicator, and wherein said detection of said branching indicator indicates that steps a) through d) are not to be repeated for said code word.

5. The method of claim 4, further comprising, if said branching indicator has been detected, the step of:

e) retrieving, based on at least one bit subsequent to those counted in step b), from a decoding table an entry that contains an output symbol that constitutes a decoding of said code word.

6. The method of claim 5, wherein, for step e), said at least one bit belong to said code word and consist of a number that is no more than a predetermined threshold.

7. The method of claim 1, wherein said method is operable to decode a code word for which the detected bit values of respective iterations are not all the same.

8. The method of claim 1, wherein the retrieving in step (c) is from a different decoding table from one iteration to the next.

9. The method of claim 1, wherein the counted bits are separated iteration-to-iteration by a single bit in said series of code words.

10. The method of claim 1, wherein said series of variable length code words is received by a mobile terminal and decoded by said method.

11. The method of claim 10, wherein said mobile terminal is a mobile telephone.

12. The method of claim 1, wherein said variable length code words are Huffman-encoded code words.

30. The method of claim 1, further including, if step d) determines that steps a) through d) are to be repeated for said code word, the step of repeating steps a) through d) for said code word using bits subsequent to those included in the one or more counts in step b).

13. A variable length decoding apparatus configured to decode a code word in serially arranged, variable length code words, comprising:

a leading zero/one count calculator for detecting the value of a bit in said code word and calculating a current count that starts with said bit and includes, from said series of variable length code words, subsequent, consecutive bits of the same value; and

a control block configured for retrieving, based on the current count, an entry from a decoding table, and, based on the retrieved entry, determining whether to repeat, using bits subsequent to those counted by the calculator, the steps of invoking the calculator and performing said retrieving and determining for said code word.

14. The apparatus of claim 13, the control block being further configured so that if the control block determines that the invoking, retrieving and determining steps are not to be repeated for said code word using bits subsequent to those counted by the calculator, the control block further determines whether the entry last retrieved contains an output symbol that constitutes a decoding of said code word, and, if not, retrieves, based on at least one bit subsequent to those counted by the calculator, from a decoding table an entry that contains an output symbol that constitutes a decoding of said code word.

15. The apparatus of claim 14, wherein said at least one bit belong to said code word and consist of a number of bits that is no more than a predetermined threshold.

16. The apparatus of claim 15, wherein said apparatus is operable so that said detected bit values of respective iterations are generally not all the same.

17. The apparatus of claim 13, wherein said apparatus is configured so that said detected bit values of respective iterations are generally not all the same.

18. The apparatus of claim 13, wherein said iterative retrievals retrieve from a different decoding table from one iteration to the next.

19. The apparatus of claim 13, further comprising a mobile terminal for receiving from the control block the decoding of said code word.

20. The apparatus of claim 19, wherein said mobile terminal comprises a mobile telephone.

21. The apparatus of claim 13, wherein said variable length code words are Huffman-encoded code words.

22. An apparatus for determining the value of the leading bit of a string and a count of a run that includes said bit comprising:

a value detector for detecting said value;

a first inverter for inverting the bits of said string if said detected value is equal to a pre-selected bit value;

a digit extender for converting to said pre-selected bit value every bit of said string of value different than said pre-selected bit value and of significance lower than that of the most significant bit having said pre-selected bit value;

a second inverter for inverting bits output from said digit extender;

a reversor for reversing the order of said bits inverted by said second inverter to create a reversed string; and

a thermometer code evaluator for calculating a run count of the bits in said reversed string that have said pre-selected value.

23. The apparatus of claim 22, further comprising:

means for selecting said string from serially-arranged, variable length code words; and

means for using said calculated run count and detected value to decode a current one of a said code words.

24. The apparatus of claim 23, wherein said variable length code words are Huffman-encoded code words.

25. The apparatus of claim 22, further comprising a run characterizer for assembling a digital representation of said calculated run count and said detected value.

26. The apparatus of claim 25, wherein said digital representation comprises a binary coded decimal representation of said calculated count.

27. A computer-readable medium of instructions for decoding a code word in serially-arranged variable length code words comprising:

a) detecting means for detecting the value of a bit in said code word;

b) calculating means for calculating a current count that starts with said bit and includes, from said series of variable length code words, subsequent, consecutive bits of the same value;

c) retrieving means for retrieving, based on the current count, an entry from a decoding table; and

d) determining means for determining, based on the retrieved entry, whether means a) through d) are to be re-invoked for said code word using bits subsequent to those counted by the calculating means.

28. The medium of claim 27, wherein the determining means further determines whether the entry last retrieved contains a decoding of said current code word, said medium also including:

e) second retrieving means for retrieving, based on at least one bit subsequent to those counted by the calculating means, from a decoding table an entry that contains a decoding of said current code word, if the determining means has determined that a decoding of said current code word has not already been retrieved.

29. A method for determining the value of the leading bit of a string and a count of a run that includes said bit comprising:

detecting said value;

inverting the bits of said string if said detected value is equal to a pre-selected bit value;

converting to said pre-selected bit value every bit of said string of value different than said pre-selected bit value and of significance lower than that of the most significant bit having said pre-selected bit value;

inverting the string after said conversion;

reversing the order of said bits inverted after conversion, to create a reversed string; and

calculating a run count of the bits in said reversed string that have said pre-selected value.