Methods and apparatuses for variable length encoding

• US 6,781,529 B1
• Filed: 10/24/2002
• Issued: 08/24/2004
• Est. Priority Date: 10/24/2002
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Oslick, Mitchell, Lin, Chien-Hsin, Lai, Mike, Sarwar, Mushtaq
• Primary Examiner(s): Young, Brian
• Assistant Examiner(s): LAUTURE, JOSEPH J
• Application Number:
  US10/280,225
• Time in Patent Office: 670 Days
• Field of Search: 341/106, 341/67, 341/50, 341/51, 341/59, 341/63, 341/100, 382/233
• US Class Current: 341/106
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

Methods and apparatuses for variable length encoding using a vector processing unit. In one aspect of the invention, a method for execution by a microprocessor to perform variable length encoding includes: receiving a plurality of parameters, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded; generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols; generating a plurality of lengths representing respectively bit lengths of the plurality of first codewords; and outputting the plurality of first codewords and the plurality of lengths; where the above operations are performed in response to the microprocessor receiving a single instruction.

Claims

1. A method for execution by a microprocessor to perform variable length encoding, the method comprising:

receiving a plurality of parameters, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded;

generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols;

generating a plurality of lengths representing respectively bit lengths of the plurality of first codewords; and

outputting the plurality of first codewords and the plurality of lengths;

wherein the above operations are performed in response to the microprocessor receiving a single instruction.

2. A method as in claim 1 wherein the plurality of parameters comprises a plurality of indices and said generating concurrently the plurality of first codewords further comprises:

looking up simultaneously a plurality of entries from a plurality of look up tables respectively using the plurality of indices to generate the plurality of first codewords.

3. A method as in claim 2 further comprising:

configuring a plurality of look up units to finction as the plurality of look up tables.

4. A method as in claim 3 wherein each of the look up tables utilizes more than one of the plurality of look up units.

5. A method as in claim 2 wherein said generating concurrently the plurality of first codewords fuirther comprises:

combining the plurality of parameters and the plurality of entries to generate the plurality of first codewords.

6. A method as in claim 5 wherein each entry of the plurality of entries comprises a first bit segment representing a second codeword and a second bit segment representing a bit length of the second codeword.

7. A method as in claim 6 wherein:

the plurality of parameters further comprises a plurality of sign indicators, each of which indicates a value of a sign bit of a corresponding one of the plurality of symbols;

each of the plurality of entries fuirther comprises a third bit segment indicating whether or not to append a sign bit of a corresponding one of the plurality of symbols; and

a sign bit of a first symbol in the plurality of symbols, which symbol corresponds to a first entry in the plurality of entries, is appended to the second codeword represented by the first bit segment of the first entry when the third bit segment of the first entry indicates to append the sign bit.

8. A method as in claim 6 wherein the plurality of parameters further comprises a plurality of type indicators for the plurality of symbols respectively.

9. A method as in claim 8 wherein a zero is generated as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a first value.

10. A method as in claim 8 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of third codewords is used as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a second value.

11. A method as in claim 8 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of first codewords that represents a first symbol in the plurality of symbols is generated from concatenating one of the plurality of third codewords that corresponds to the first symbol and the second codeword represented by the first bit segment of a first entry in the plurality of entries, which entry corresponds to the first symbol, when one of the plurality of type indicators, which corresponds to the first symbol, has a third value.

12. A machine readable medium containing executable computer program instructions which when executed by a digital processing system cause said system to perform a method to perform variable length encoding, the method comprising:

receiving a plurality of parameters, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded;

generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols;

generating a plurality of lengths representing respectively bit lengths.of the plurality of first codewords; and

outputting the plurality of first codewords and the plurality of lengths;

wherein the above operations are performed in response to a microprocessor receiving a single instruction.

13. A medium as in claim 12 wherein the plurality of parameters comprises a plurality of indices and said generating concurrently the plurality of first codewords further comprises:

looking up simultaneously a plurality of entries from a plurality of look up tables respectively using the plurality of indices to generate the plurality of first codewords.

14. A medium as in claim 13 wherein the method further comprises:

configuring a plurality of look up units to function as the plurality of look up tables.

15. A medium as in claim 14 wherein each of the look up tables utilizes more than one of the plurality of look up units.

16. A medium as in claim 13 wherein said generating concurrently the plurality of first codewords further comprises:

combining the plurality of parameters and the plurality of entries to generate the plurality of first codewords.

17. A medium as in claim 16 wherein each entry of the plurality of entries comprises a first bit segment representing a second codeword and a second bit segment representing a bit length ofthe second codeword.

18. A medium as in claim 17 wherein:

the plurality of parameters further comprises a plurality of sign indicators, each of which indicates a value of a sign bit of a corresponding one of the plurality of symbols;

each of the plurality of entries further comprises a third bit segment indicating whether or not to append a sign bit of a corresponding one of the plurality of symbols; and

a sign bit of a first symbol in the plurality of symbols, which symbol corresponds to a first entry in the plurality of entries, is appended to the second codeword represented by the first bit segment of the first entry when the third bit segment of the first entry indicates to append the sign bit.

19. A medium as in claim 17 wherein the plurality of parameters further comprises a plurality of type indicators for the plurality of symbols respectively.

20. A medium as in claim 19 wherein a zero is generated as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a first value.

21. A medium as in claim 19 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of third codewords is used as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a second value.

22. A medium as in claim 19 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of first codewords that represents a first symbol in the plurality of symbols is generated from concatenating one of the plurality of third codewords that corresponds to the first symbol and the second codeword represented by the first bit segment of a first entry in the plurality of entries, which entry corresponds to the first symbol, when one of the plurality of type indicators, which corresponds to the first symbol, has a third value.

23. A digital processing system to perform variable length encoding, the digital processing system comprising:

means for receiving a plurality of parameters, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded;

means for generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols;

means for generating a plurality of lengths representing respectively bit lengths of the plurality of first codewords; and

means for outputting the plurality of first codewords and the plurality of lengths;

wherein the above means operate in response to a microprocessor receiving a single instruction.

24. A digital processing system as in claim 23 wherein the plurality of parameters comprises a plurality of indices and said means for generating concurrently the plurality of first codewords further comprises:

means for looking up simultaneously a plurality of entries from a plurality of look up tables respectively using the plurality of indices to generate the plurality of first codewords.

25. A digital processing system as in claim 24 farther comprising:

means for configuring a plurality of look up units to function as the plurality of look up tables.

26. A digital processing system as in claim 25 wherein each of the look up tables utilizes more than one of the plurality of look up units.

27. A digital processing system as in claim 24 wherein said means for generating concurrently the plurality of first codewords further comprises:

means for combining the plurality of parameters and the plurality of entries to generate the plurality of first codewords.

28. A digital processing system as in claim 27 wherein each entry of the plurality of entries comprises a first bit segment representing a second codeword and a second bit segment representing a bit length of the second codeword.

29. A digital processing system as in claim 28 wherein:

the plurality of parameters further comprises a plurality of sign indicators, each of which indicates a value of a sign bit of a corresponding one of the plurality of symbols;

each of the plurality of entries further comprises a third bit segment indicating whether or not to append a sign bit of a corresponding one of the plurality of symbols; and

a sign bit of a first symbol in the plurality of symbols, which symbol corresponds to a first entry in the plurality of entries, is appended to the second codeword represented by the first bit segment of the first entry when the third bit segment of the first entry indicates to append the sign bit.

30. A digital processing system as in claim 28 wherein the plurality of parameters further comprises a plurality of type indicators for the plurality of symbols respectively.

31. A digital processing system as in claim 30 wherein a zero is generated as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a first value.

32. A digital processing system as in claim 30 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of third codewords is used as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a second value.

33. A digital processing system as in claim 30 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of first codewords that represents a first symbol in the plurality of symbols is generated from concatenating one of the plurality of third codewords that corresponds to the first symbol and the second codeword represented by the first bit segment of a first entry in the plurality of entries, which entry corresponds to the first symbol, when one of the plurality of type indicators, which corresponds to the first symbol, has a third value.

34. A processing system to perform variable length encoding, the processing system comprising:

a plurality of vector registers; and

a vector execution unit coupled to the plurality of vector registers, in response to receiving a single instruction, the vector execution unit;

receiving a plurality of parameters from the plurality of vector registers, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded,

generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols,

generating a plurality of lengths representing respectively bit lengths of the plurality of first codewords, and

outputting the plurality of first codewords and the plurality of lengths to at least one of the plurality of vector registers.

35. A processing system as in claim 34 wherein

the vector execution unit further comprises a plurality of look up tables;

the plurality of parameters comprises a plurality of indices; and

the vector execution unit looks up simultaneously a plurality of entries from the plurality of look up tables respectively using the plurality of indices to generate concurrently the plurality of first codewords.

36. A processing system as in claim 35 wherein

the vector execution unit comprises a plurality of look up units;

and

the vector execution unit configures the plurality of look up units to function as the plurality of look up tables.

37. A processing system as in claim 36 wherein each of the look up tables utilizes more than one of the plurality of look up units.

38. A processing system as in claim 35 wherein the vector execution unit combines the plurality of parameters and the plurality of entries to generate concurrently the plurality of first codewords.

39. A processing system as in claim 38 wherein each entry of the plurality of entries comprises a first bit segment representing a second codeword and a second bit segment representing a bit length of the second codeword.

40. A processing system as in claim 39 wherein:

the plurality of parameters further comprises a plurality of sign indicators, each of which indicates a value of a sign bit of a corresponding one of the plurality of symbols;

each of the plurality of entries further comprises a third bit segment indicating whether or not to append a sign bit of a corresponding one of the plurality of symbols; and

a sign bit of a first symbol in the plurality of symbols, which symbol corresponds to a first entry in the plurality of entries, is appended to the second codeword represented by the first bit segment of the first entry when the third bit segment of the first entry indicates to append the sign bit.

41. A processing system as in claim 39 wherein the plurality of parameters further comprises a plurality of type indicators for the plurality of symbols respectively.

42. A processing system as in claim 41 wherein a zero is generated as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a first value.

43. A processing system as in claim 41 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbols; and

one of the plurality of third codewords is used as one of the plurality of first codewords to represent a first symbol in the plurality of symbols when one of the plurality of type indicators, which corresponds to the first symbol, has a second value.

44. A processing system as in claim 41 wherein:

the plurality of parameters further comprises a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality of symbol; and

one of the plurality of first codewords that represents a first symbol in the plurality of symbol is generated from concatenating one of the plurality of third codewords that corresponds to the first symbol and the second codeword represented by the first bit segment of a first entry in the plurality of entries, which entry corresponds to the first symbol, when one of the plurality of type indicators, which corresponds to the first symbol, has a third value.