Method and apparatus for variable length coding

• US 20030146858A1
• Filed: 02/05/2002
• Published: 08/07/2003
• Est. Priority Date: 02/05/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hum, Herbert, Chen, Yen-Kuang, Hammarlund, Per H., Macy, William W., Holliman, Matthew J., Huff, Thomas
• Granted Patent: US 6,798,364 B2
• Time in Patent Office: Days
• US Class Current: 341/63
• CPC Class Codes: G11B 20/1426 conversion to or from block codes or representations thereof
• CPC Class Codes: H03M 5/145 Conversion to or from block codes or representations thereof
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
• 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/29 involving scalability at the object level, e.g. video object layer [VOL]
• CPC Class Codes: H04N 19/34 Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A method and apparatus for variable length coding is described. A method comprises receiving a group of data having a group of set values, identifying a group of positions of the group of set values within the group of data without branching, for each of the group of positions, encoding a run of non-set values preceding each of the group of positions.

Claims

1. A method comprising:

receiving a group of data having a group of set values;

identifying a group of positions of the group of set values within the group of data;

for each of the group of positions, encoding a run of non-set values preceding each of the group of positions.

2. The method of claim 1 further comprising encoding a second run of non-set values with an ending symbol.

3. The method of claim 1 further comprising encoding a group of signs corresponding to the group of set values.

4. The method of claim 1 wherein the group of positions are identified without non-loop related conditional branches.

5. The method of claim 4 wherein identifying the group of positions without non-loop related conditional branches comprises:

performing a logic operation of each value in the group of data; and

tracking the group of positions with a result of the logic operation.

6. The method of claim 4 wherein the identifying the group of positions without non-loop related conditional branches comprises:

performing a logic operation of each value in the group of data;

setting a flag to a result of the logic operation; and

tracking the group of positions using a conditional instruction with the flag.

7. A method comprising:

loading a group of data into a buffer, the group of data having a group of one or more set bits;

identifying a position of a first set bit in the buffer without non-loop related conditional branching;

encoding a run of non-set bits preceding the position; and

shifting the run of non-set bits and the first set bit out of the buffer.

8. The method of claim 7 further comprising encoding a second run of set values with an ending symbol.

9. The method of claim 7 further comprising encoding a sign bit corresponding to the first set bit at the position in a second buffer.

10. The method of claim 7 wherein loading a group of data into the buffer comprises:

loading a group of source data into a first buffer, the group of source data including the group of data;

loading a mask for a bit-plane into a second buffer;

selecting the group of data from the group of source data with the mask; and

extracting the group of data into the buffer.

11. The method of claim 7 wherein identifying the first set bit comprises:

shifting each bit of the group of data out of the buffer;

comparing each shifted bit with a compare bit to determine if each bit is one of the group of set bits;

tracking each of the group of set bits when detected with the comparing; and

incrementing a counter for each shifted bit.

12. The method of claim 7 wherein the first set bit is identified with one or more look-up tables.

13. The method of claim 7 further comprising

identifying multiple positions of first set bits in the buffer without non-loop related conditional branching;

and

simultaneously encoding runs of non-set bits preceding the positions.

14. An apparatus comprising:

a buffer to host a group of data having a group of one or more set bits; and

a variable length coding (VLC) module coupled with the memory, the VLC module to identify the group of set bits'"'"' positions and to encode each run of non-set bits with respect to the group of set bits'"'"' positions.

15. The apparatus of claim 14 further comprising the VLC module to encode a second run of non-set bits with an ending symbol.

16. The apparatus of claim 14 further comprising the VLC module to encode a group of sign bits corresponding to the group of set bits.

17. The apparatus of claim 14 further comprising a group of one or more look-up tables for the VLC module to identify the group of set bits'"'"' positions.

18. The apparatus of claim 14 wherein the VLC module to identify each of the group of set bits'"'"' positions comprises

for each of the group of set bits,

to load the group of data into a memory,

to flip all bits of the group of data,

to set all bits in positions after one of the group of set bits position to non-set bits, and

to add the set bits in the memory in an adder tree.

19. A machine-readable medium that provides instructions, which when executed by a group of processors of one or more processors, cause said group of processors to perform operations comprising:

receiving a group of data having a group of set values;

identifying a group of positions of the group of set values within the group of data;

for each of the group of positions, encoding a run of non-set values preceding each of the group of positions.

20. The machine-readable medium of claim 19 further comprising encoding a second run of non-set values with an ending symbol.

21. The machine-readable medium of claim 19 further comprising encoding a group of signs corresponding to the group of set values.

22. The machine-readable medium of claim 19 wherein the group of positions are identified without non-loop related conditional branches.

23. The machine-readable medium of claim 22 wherein identifying the group of positions without non-loop related conditional branches comprises:

performing a logic operation of each value in the group of data; and

tracking the group of positions with a result of the logic operation.

24. The machine-readable medium of claim 22 wherein the identifying the group of positions without non-loop related conditional branches comprises:

performing a logic operation of each value in the group of data;

setting a flag to a result of the logic operation; and

tracking the group of positions using a conditional instruction with the flag.

25. A machine-readable medium that provides instructions, which when executed by a group of processors of one or more processors, cause said group of processors to perform operations comprising:

loading a group of data into a buffer, the group of data having a group of one or more set bits;

identifying a position of a first set bit in the buffer without non-loop related conditional branching;

encoding a run of non-set bits preceding the position; and

shifting the run of non-set bits and the first set bit out of the buffer.

26. The machine-readable medium of claim 25 further comprising encoding a second run of set values with an ending symbol.

27. The machine-readable medium of claim 25 further comprising encoding a sign bit corresponding to the first set bit at the position in a second buffer.

28. The machine readable medium of claim 25 wherein loading a group of data into the buffer comprises:

loading a group of source data into a first buffer, the group of source data including the group of data;

loading a mask for a bit-plane into a second buffer;

selecting the group of data from the group of source data with the mask; and

extracting the group of data into the buffer.

29. The machine-readable medium of claim 25 wherein identifying the first set bit comprises:

loading the group of data into a memory;

flipping all bits of the group of data;

setting all bits after the first zero bit to zero; and

adding the set bits in the second memory in an adder tree, the set bits being one bits.

30. The machine-readable medium of claim 25 wherein the first set bit is identified with one or more look-up tables.