Variable length decoder

• US 6,842,124 B2
• Filed: 09/18/2002
• Issued: 01/11/2005
• Est. Priority Date: 10/17/2001
• Status: Expired due to Term

• Current Assignee: MaxLinear Communications, LLC (f/k/a Entropic Communications, LLC) (Maxlinear Incorporated)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Penna, David E.
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US10/246,169
• Publication Number:
  US 20030118114A1
• Time in Patent Office: 846 Days
• Field of Search: 341/67, 341/106, 341/51, 341/65, 341/59, 375/345, 711/200, 708/277
• US Class Current: 341/67
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• 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

Abstract

Variable length decoding of DCT coefficients in MPEG video data is performed using a standard processor (400) and a small look-up table (LUT 530). The processor performs (520) an integer to floating point conversion on a portion the received bitstream (BS). By this step, lengthy codewords with many leading zeros, which are common in the codebook, are represented in a compressed form by the exponent and mantissa fields (EXP, MAN) of the floating point result (FP). The relevant bits are extracted and used as an index (IX) to address the LUT. This avoids cumbersome bit-oriented logic, while also avoiding a very large LUT that would otherwise be required to represent the same codebook. The entire LUT may thus reside in cache memory (410). In a VLIW processor implementation, decoding of one token is pipelined with the inverse scan and inverse quantisation step of the preceding token(s).

Claims

1. A method of decoding a variable length coded bitstream, said bitstream comprising a concatenation of tokens of differing lengths, wherein a look-up table is employed to obtain decoded values from successive portions of the coded bitstream, wherein longer tokens in the coded bitstream are characterised by strings of identical leading characters (‘

1’

s or ‘

0’

s), and wherein said portions of the coded bitstream are pre-processed to obtain an index for said look-up table, said pre-processing step effectively replacing said strings with a fixed-length field representing the length of the string of leading characters to define the index using fewer bits than a maximum length of said tokens.

2. A method as claimed in claim 1, wherein each token is decoded by a single look-up operation.

3. A method as claimed in claim 2, wherein the step of pre-processing of the token comprises conversion to exponent-plus-mantissa format.

4. A method as claimed in claim 3, wherein the method comprises the steps of:

(a) providing a look-up table (LUT) whose entries include decoded values corresponding to tokens potentially occurring within the coded bitstream;

(b) reading a portion of said coded bitstream;

(c) converting the received portion to exponent and mantissa components;

(d) using portions of said exponent and mantissa as an index to identify a specific entry within said look-up table (LUT) to extract a decoded value corresponding to a variable-length coded token contained within the received portion of the coded bitstream;

(e) using the LUT entry to identify the start position of a next variable-length token and repeating steps (c) and (d) to decode successive tokens until an end token is decoded, reading further portions of said bitstream as necessary.

5. A method as claimed in claim 2, wherein the variable length tokens are selectively inverted prior to the conversion to exponent and mantissa format, in order to convert a token with leading ‘

1’

s into a token with leading ‘

0’

s.

6. A method as claimed in claim 1, wherein there are provided plural look-up tables, selected according to pre-determined characteristics of the bitstream portion being decoded.

7. A method as claimed in claim 1, performed using a programmable processor having a pre-defined integer-to-floating point conversion operation, wherein said pre-processing step includes conversion of a portion of said bitstream from integer to floating point format using said pre-defined operation.

8. A method in claimed hi claim 1, wherein pipeline processing is implemented such that the decoding of one token is performed concurrently with subsequent processing steps of a previously decoded value.

9. A method as claimed in claim 1, wherein the start position of a next token is derived from a token length field within each LUT entry.

10. A method as claimed in claim 1, wherein said LUT entries also include control flags that are used to modify subsequent operation of the method.

21. A record carrier wherein are recorded program instructions for causing a programmable processor to perform the step, of a method according to claim 1, or to implement an apparatus for decoding a variable length coded bitstream, said bitstream comprising a concatenation of tokens of differing lengths, wherein longer tokens in the coded bitstream are characterised by strings of identical leading characters (‘

1’

s or ‘

0’

s), the apparatus comprising;

means for storing a look-up table;

means for receiving successive portions of data representing said coded bitstream;

means for addressing said table in response to the received data so as to obtain decoded values from successive portions of the coded bitstream; and

means for pre-processing said portions of the coded bitstream to obtain an index for said look-up table, said pre-processing step effectively replacing said strings with a fixed-length field representing the length of the stung of leading characters to define the index using fewer bits than a maximiun length of said tokens.

11. An apparatus for decoding a variable length coded bitstream, said bitstream comprising a concatenation of tokens of differing lengths, wherein longer tokens in the coded bitstream are characterised by strings of identical leading characters (‘

1’

s or ‘

0’

s), the apparatus comprising;

means for storing a look-up table;

means for receiving successive portions of data representing said coded bitstream;

means for addressing said table in response to the received data so as to obtain decoded values from successive portions of the coded bitstream; and

means for pre-processing said portions of the coded bitstream to obtain an index for said look-up table, said pre-processing step effectively replacing said strings with a fixed-length field representing the length of the string of leading characters to define the index using fewer bits than a maximum length of said tokens.

12. An apparatus as claimed in claim 11, wherein each token is decoded by a single look-up operation.

13. An apparatus as claimed in claim 12, wherein the pre-processing of the token comprises conversion to exponent-plus-mantissa format.

14. An apparatus as claimed in claim 13, wherein the pre-processing means comprises:

(a) means for converting the received portion to exponent and mantissa components;

(b) means for using portions of said exponent and mantissa as an index to identify a specific entry within said look-up table (LUT) to extract a decoded value corresponding to a variable-length coded token contained within the received portion of the coded bitstream; and

(c) means for using the LUT entry to identify the start position of a next variable-length token,

means (a) and (b) being arranged to operate repetitively to decode successive tokens until an end token is decoded.

15. An apparatus as claimed in claim 12, wherein the pre-processing means is operable to invert the variable length tokens selectively prior to the conversion to exponent and mantissa format, in order to convert a token with leading ‘

1’

s into a token with leading ‘

0’

s.

16. An apparatus as claimed in claim 11, wherein there are provided plural look-up tables, selected by said addressing mean, according to pre-determined characteristics of the bitstream portion being decoded.

17. An apparatus as claimed in claim 11, wherein said means are implemented by a programmable processor having a pre-defined integer-to-floating point conversion operation, wherein said pre-processing step includes conversion of a portion of said bitstream from integer to floating point format using said pre-defined operation.

18. An apparatus as claimed in claim 11, wherein pipeline processing is implemented such that the decoding of one token is performed concurrently with subsequent processing steps of a previously decoded value.

19. An apparatus as claimed in claim 11, wherein the start position of a next token is derived in operation from a token length field within each LUT entry.

20. An apparatus as claimed in claim 11, wherein said LUT entries also include control flags that are used to modify subsequent operation of the apparatus in operation.