Variable length decoding using lookup tables

• US 5,253,053 A
• Filed: 12/31/1990
• Issued: 10/12/1993
• Est. Priority Date: 12/31/1990
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Chu, Ke-Chiang, Normile, James O., Wright, Daniel W., Yeh, Chia L.
• Primary Examiner(s): Peng, John K.
• Application Number:
  US07/636,498
• Time in Patent Office: 1,016 Days
• Field of Search: 358/133, 382/56
• US Class Current: 375/240.23
• CPC Class Codes: H03M 7/425 for the decoding process only
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 7/54 the signals being synchronous H04N21/23602, H04N21/23614, H04N21/2365, H04N21/2368, H04N21/4341, H04N21/4342, H04N21/4347, H04N21/4348 take precedence

Abstract

A method and apparatus for decoding a variable length codeword (VLC) by reading a VLC, the VLC having a maximum length of X bits. The VLC is used as an index into a first table, wherein the first table contains decoded values for all possible VLC'"'"'s with Y bits not equal to any value in a first set of values. Y is typically less than X and comprises, in the preferred embodiment, the most significant bits of the VLC. If the first Y bits of the VLC are not equal to any value in a first set of values then a second value is returned from the first table. If the first Y bits of the VLC are equal to any value in a first set of values, then a pointer to a second table is returned from the first table. The VLC is used as an index into the second table, and a third value is returned from the second table.

Claims

1. In a data processing apparatus, a method for decoding a variable length codeword (VLC), said VLC being a portion of an encoded bitstream in said data processing apparatus comprising the following steps:

a. reading a VLC from said encoded bitstream, the VLC having a maximum length of X bits;

b. using the VLC as an index into a first table, the first table containing decoded values for all possible VLC'"'"'s with first Y bits not equal to any value in a first set of values, wherein Y is less than X, and if the first Y bits of the VLC are not equal to any value in the first set of values then returning a second decoded value from the first table; and

c. if the first Y bits of the VLC are equal to any value in the first set of values, then returning a pointer to a second table from the first table, using the VLC as an index into the second table, and returning a third decoded value from the second table.

2. The method of claim 1 wherein the VLC contains video information.

3. The method of claim 2 wherein the VLC is encoded according to the Motion Picture Experts Group (MPEG) standard.

4. The method of claim 2 wherein the VLC is encoded according to the Joint Photographer Experts Group (JPEG) standard.

5. The method of claim 2 wherein the VLC is encoded according to the CCITT standard.

6. In a data processing apparatus, a method for decoding a variable length codeword (VLC), said VLC being a portion of an encoded bitstream in said data processing apparatus comprising the following steps:

a. reading a VLC from said encoded bitstream, the VLC having a maximum length of X bits;

b. using the VLC as an index into a first table, the first table containing decoded values for all possible VLC'"'"'s having first Y bits not equal to any value in a first set of values, wherein Y is less than X, and if the first Y bits of the VLC are not equal to any value in a first set of values then returning a second decoded value from the first table;

c. if the first Y bits of the VLC are equal to any value in the first set of values, then returning a pointer to a second table from the first table, using the VLC as an index into the second table, and if first Z bits of the VLC are not equal to any value in a third set of values, wherein Z is less than X, then returning a fourth decoded value from the second table; and

d. if first Z bits of the VLC are equal to any value in the third set of values, then returning a pointer to a third table from the second table, using the VLC as an index into the third table, and returning a fifth decoded value from the third table.

7. The method of claim 6 wherein the VLC contains video information.

8. The method of claim 7 wherein the VLC is encoded according to the Motion Picture Experts Group (MPEG) standard.

9. The method of claim 7 wherein the VLC is encoded according to the Joint Photographer Experts Group (JPEG) standard.

10. The method of claim 7 wherein the VLC is encoded according to the CCITT standard.

11. A data processing apparatus for decoding a variable length codeword (VLC), said VLC being a portion of an encoded bitstream in said data processing apparatus comprising:

a. a means for reading a VLC from said encoded bitstream, the VLC having a maximum length of X bits;

b. a first table containing decoded values for all possible VLC'"'"'s with first Y bits not equal to any value in a first set of values, wherein Y is less than X, the first table providing a second decoded value responsive to receiving the VLC if the first Y bits of the VLC are not equal to any value in the first set of values; and

c. means for returning a pointer to a second table from the first table if the first Y bits of the VLC are equal to any value in the first set of values, means for using the VLC as an index into the second table, and the second table providing a third decoded value responsive to receiving the VLC.

12. A data processing apparatus for decoding a variable length codeword (VLC) X bits in length, comprising a plurality of lookup tables, each lookup table having:

a) entries containing decoded values for Y bits in the VLC, wherein Y is less than X; and

b) at least one of the entries in one lookup table containing a pointer to a subsequent lookup table for the Y bits in the VLC.

13. The apparatus of claim 12 wherein the Y bits comprise Y least significant bits in the VLC.

14. In a data processing system, a method of decoding a variable length codeword (VLC), said VLC being a portion of an encoded bitstream in said data processing apparatus comprising the following steps:

a. retrieving a VLC from said encoded bitstream, said VLC having a first length;

b. applying the VLC to a first lookup table, the first lookup table containing entries associating first combinations of X bits of said VLC with a first set of decoded values, a first entry for a first value of said X bits of said VLC containing a reference to a second lookup table, said second lookup table containing entries associating combinations of Y bits of said VLC with a second set of decoded values, said X and Y bits comprising different portions of said VLC, and X and Y being less than said first length and representing different portions of said VLC; and

c. if said X bits of said VLC are equal to said first value then retrieving said first entry, applying said Y bits of said VLC to said second lookup table, and retrieving a second decoded value from said second lookup table, otherwise retrieving a first decoded value from said first lookup table.

15. The method of claim 14 wherein said second lookup table further comprises a second entry for a second value of said Y bits of said VLC containing a reference to a third lookup table, said third lookup table containing entries associating combinations of Z bits of said VLC with a third set of decoded values, said Z bits comprising different portions of said VLC than said X and Y bits, Z being less than said first length, said method further comprising the additional step of determining if said Y bits of said VLC are equal to said second value then retrieving said second entry, applying said Z bits of said VLC to said third lookup table, and retrieving a third decoded value from said third lookup table.

16. The method of claim 14 wherein the first and second lookup tables reside in a non-volatile memory.

17. The method of claim 15 wherein the first, second, and third lookup table reside in a non-volatile memory.

18. The method of claim 14 wherein the VLC is encoded in Huffman type encoding.

19. The method of claim 14 wherein the VLC is encoded according to Motion Picture Experts Group (MPEG) specifications.

20. The method of claim 14 wherein the VLC is encoded according to International Consultative Committee on Telegraphy and Telephony (CCITT) specifications.

21. The method of claim 14 wherein the VLC is encoded according to Joint Photographer'"'"'s Experts Group (JPEG) specifications.

22. The method of claim 14 wherein the X bits comprise the X most significant bits of the VLC.

23. The method of claim 14 wherein the Y bits comprise the Y least significant bits of the VLC.

24. The method of claim 15 wherein the Z bits comprise the Z least significant bits of the VLC.

25. In a data processing system, a method of decoding a codeword which is part of an encoded bitstream in said data processing apparatus comprising the following steps:

a. retrieving a codeword from said encoded bitstream, said codeword having a first length;

b. applying the codeword to a first lookup table, the first lookup table containing entries associating first combinations of X bits of said codeword with a first set of decoded values, a first entry for a first value of said X bits of said codeword containing a reference to a second lookup table, said second lookup table containing entries associating combinations of Y bits of said codeword with a second set of decoded values, said X and Y bits comprising different portions of said codeword, and X and Y being less than said first length and representing different portions of said codeword; and

c. if said X bits of said codeword are equal to said first value then retrieving said first entry, applying said Y bits of said codeword to said second lookup table, and retrieving a second decoded value from said lookup table, otherwise retrieving a first decoded value from said first lookup table.

26. The method of claim 25 wherein said second lookup table further comprises a second entry for a second value of said Y bits of said codeword containing a reference to a third lookup table, said third lookup table containing entries associating combinations of Z bits of said codeword with a third set of decoded values, said Z bits comprising different portions of said codeword than said X and Y bits, Z being less than said first length, said process further comprising the additional step of determining if said Y bits of said codeword are equal to said second value then retrieving said second entry, applying said Z bits of said codeword to said third lookup table, and retrieving a third decoded value from said third lookup table.