Efficient decoding of n-tuple variable bit length symbols

• US 20070126608A1
• Filed: 12/01/2005
• Published: 06/07/2007
• Est. Priority Date: 12/01/2005
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: PortalPlayer USA, Inc. (NVIDIA Corporation)
• Inventors: Sriram, Partha
• Granted Patent: US 7,372,378 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• CPC Class Codes: H03M 7/425 for the decoding process only

Abstract

Methods and systems that leverage the advantages of Huffman coding to increase processing efficiency of a data-stream while simultaneously minimizing storage requirements are provided. Decoding efficiency and table storage requirements can be balanced to produce systems that can be adapted for use in high-end network infrastructure applications and for low-resourced portable consumer devices. The systems and methods are operative in decoding data streams using multi-symbol codes and sign information, including AAC and MP3 data streams. A hierarchical structure of tables is described as having primary tables, secondary tables, tertiary tables and so on. Optimization balances processing requirements, table storage requirements and the described systems and methods may be implemented on a variety of processing platforms.

Claims

1. A method for decoding a data stream comprising the steps of:

repeating, until a termination condition is encountered, the steps of forming an index including one or more bits received from the data stream, retrieving an element in a selected table based on the index, and unless the termination condition is encountered, selecting a next selected table based on information included in the element; and

extracting one or more symbols from information in the element.

2. A method according to claim 1, wherein the termination condition is a bit setting in the element.

3. A method according to claim 1, wherein the termination condition is an error code included in the element.

4. A method according to claim 1, wherein bit-length of the index is determined by a size field in the information.

5. A method according to claim 4, wherein the size field indicates a number of additional bits to be obtained for forming a next index, wherein the next index is for identifying an element in the next selected table.

6. A method according to claim 1, wherein the selected table is initially a predetermined primary table.

7. A method according to claim 1, wherein the next selected table is identified using an offset from a previous selected table.

8. A method according to claim 1, and further comprising the step of obtaining sign bits associated with the one or more symbols, wherein the number of sign bits is provided in the element.

9. A method according to claim 1, wherein the one or more symbols includes two symbols.

10. A method according to claim 1, wherein the one or more symbols includes four symbols.

11. A system for decoding a data stream comprising:

one or more tables, each table including a plurality of elements;

a prefetcher for receiving encoded bits from the data stream;

a sequencer for obtaining a codeword from the encoded bits and for using sequential portions of the codeword to locate an element in the one or more tables that decodes the codeword.

12. The system of claim 11, wherein each sequential portion indexes a selected table from the one or more tables to obtain a desired element.

13. The system of claim 11, wherein the plurality of elements includes a combination of terminating elements and non-termination elements.

14. The system of claim 13, wherein certain of the terminating elements include one or more decoded symbols.

15. The system of claim 13, wherein certain of the terminating elements include error codes.

16. The system of claim 13, wherein each non-terminating element in each of the one or more tables identifies a different table.

17. The system of claim 16, wherein each non-terminating element identifies a number of bits of the codeword to be used for indexing the different table.

18. The system of claim 11, wherein the size of each table in the one or more tables is configured to optimize an average number of lookups per codeword (“

ALPC”

) associated with the data stream.

19. The system of claim 11, wherein the size of each table in the one or more tables is configured to optimize an average number of lookups per codeword (“

ALPC”

) associated with at least one selected table of the one or more tables.

20. A method for decoding a data stream comprising the steps of:

repeating, until a termination condition is encountered, the steps of forming an index including one or more bits received from the data stream, retrieving an element in a selected table based on the index, and unless the termination condition is encountered, selecting a next selected table based on information included in the element;

extracting one or more symbols from information in the element; and

obtaining sign bits associated with the one or more symbols, wherein the number of sign bits is provided in the element;

wherein

tables are selected from a hierarchical set of tables, and wherein

each table in the set has an associated table size that is configured to optimize an average number of lookups per codeword (“

ALPC”

) associated with at least one table.