Method and system for decoding data encoded in a variable length code word

• US 6,219,457 B1
• Filed: 05/26/1998
• Issued: 04/17/2001
• Est. Priority Date: 05/26/1998
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Potu, Brahmaji
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/084,290
• Time in Patent Office: 1,057 Days
• Field of Search: 382/246, 382/244, 382/245, 382/233, 341/65, 341/67, 341/59, 358/427, 358/261.1, 375/240.23, 375/240.25
• US Class Current: 382/246
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding

Abstract

A novel technique for decoding variable length encoded data in a bit stream such as video data compressed in accordance with JPEG, MPEG, or DV standards is disclosed. The disclosed technique preprocesses the input data to generate a pointer to a variable length code table from the encoded code word, the entry in the variable length table providing the information necessary to decode the code word. Preprocessing of the input data includes encoding leading ones or leading zeros and selecting a subset of bits following the leading ones or zeros. The pointer to the variable length code table is generated from a base value corresponding to the symbol type being decoded. The base values for the symbols being decoded may be stored in a first look up table which may contain multiple entries for one or more of the symbol types, the number of entries corresponding to the number of leading ones or zeros.

Claims

1. A method of decoding data encoded in a variable length code word in a system having a first look up table and a variable length code table, said method comprising the steps of:

receiving a plurality of bits comprising at least one encoded code word;

encoding a number of leading bits in the encoded code word;

providing the encoded number of leading bits to a first look up table address generator and to a variable length code table address generator;

generating a first pointer to an entry in the first look up table, said step comprising;

receiving a code word type identification, and

responsive to the code word type identification and the encoded number of leading bits, generating the first pointer that points to one of a plurality of entries in the first look up table;

evaluating the entry in the first look up table pointed to by the first table pointer;

generating a second pointer to an entry in the variable length code table, said step comprising;

selecting a plurality of bits in the encoded code word following the leading bits,

responsive to said step of evaluating the entry in the first look up table pointed to by the first pointer, determining a base address, and

combining the encoded number of leading bits, the selected bits, and the base address to generate the second pointer; and

evaluating the entry in the variable length code table pointed to by the generated second pointer to determine the number of magnitude bits in the variable length code word.

4. The method of claim 1, wherein said step of generating a first pointer to an entry in the first look up table comprises generating a first pointer responsive to the received code word type identification offset by the number of leading bits in the encoded code word.

5. The method of claim 1, wherein said step of combining the base address and the selected bits comprises addition.

6. The method of claim 1, wherein said step of evaluating the entry in the variable length code table pointed to by the generated second pointer comprises:

determining the total number of bits in the encoded code word;

determining the encoded run length in the encoded code word; and

determining the number of magnitude bits in the encoded code word.

7. The method of claim 6, wherein said step of receiving a plurality of bits comprising at least one encoded code word comprises placing the plurality of bits in an input buffer, said method further comprising shifting the total number of bits in the encoded code word out of the input buffer.

8. The method of claim 7, wherein the input buffer includes an output coupled to a magnitude buffer, said method further comprising receiving the magnitude bits from the magnitude buffer.

9. The method of claim 1, wherein the encoded code word may be one of four types, a DC chroma type, a DC luma type, an AC chroma type, or an AC luma type, and the first look up table comprises entries for each of the types.

10. The method of claim 9, wherein the first look up table has one entry corresponding to a DC chroma type and one entry corresponding to a DC luma type.

11. The method of claim 10, wherein the first look up table has a plurality of entries corresponding to an AC chroma type and a plurality of entries corresponding to an AC luma type.

12. The method of claim 1, wherein said step of combining the encoded number of leading bits, the selected bits, and the base address comprises concatenating the base address with the encoded number of leading bits and the selected bits for a DC code word.

13. The method of claim 1, wherein said step of combining the encoded number of leading bits, the selected bits, and the base address comprises adding the base address and the selected bits for an AC code word.

2. A method of decoding data encoded in a variable length code word in a system having a first look up table and a variable length code table, said method comprising the steps of:

receiving a plurality of bits comprising at least one encoded code word;

preprocessing at least one of the plurality of bits comprising at least one encoded code word, wherein said preprocessing step comprises;

generating a first table pointer to an entry in the first look up table, said step comprising;

receiving a code word type identification, and

responsive to the code word type identification, generating the first table pointer that points to one of a plurality of entries in the first look up table,

evaluating the entry in the first look up table pointed to by the first table pointer, and

further processing at least one of the plurality of bits comprising at least one encoded word;

generating a pointer to an entry in the variable length code table from said preprocessing, wherein said generating step comprises;

encoding the number of leading ones in the encoded code word,

selecting a plurality of bits in the encoded code word following the leading ones,

responsive to said step of evaluating the entry in the first look up table pointed to by the first table pointer, determining a base address, and

combining the encoded number of leading ones, the selected bits, and the base address, and

evaluating the entry in the variable length code table pointed to by the generated pointer.

3. The method of claim 2, wherein said step of combining the encoded number of leading ones, the selected bits, and the base address comprises concatenation.

14. A system for decoding data encoded in a variable length code word having one or more leading one or leading zero bits, said system comprising:

an input buffer;

an encoder coupled to said input buffer;

a first look up table address generator coupled to said encoder;

a first look up table responsive to said first look up table address generator;

an extra bits selector coupled to said first look up table and to said input buffer;

a variable length code table address generator coupled to said first look up table, said extra bits selector, and said encoder, wherein said variable length code table address generator concatenates inputs from said extra bits selector and said encoder to generate an address for an AC code word; and

a variable length code table responsive to said variable length code table address generator.

15. The system of claim 14, wherein said input buffer is coupled to a magnitude bits buffer.

16. The system of claim 14, wherein said first look up table has a single entry for DC luminance, a single entry for DC chrominance, sixteen entries for AC luminance, and sixteen entries for AC chrominance.

17. The system of claim 14, wherein said variable length code table address generator concatenates inputs from said first look up table, said extra bits selector, and said encoder to generate an address for a DC code word.

18. The system of claim 14, wherein said encoder counts the number of leading zeros and outputs to said first look up table address generator and to said variable length code table address generator a number corresponding to the number of leading zeros.

19. The system of claim 14, wherein said encoder counts the number of leading ones and outputs to said first look up table address generator and to said variable length code table address generator a four bit number corresponding to the number of leading ones.