Multi-level run length coding for frequency-domain audio coding

• US 6,223,162 B1
• Filed: 12/14/1998
• Issued: 04/24/2001
• Est. Priority Date: 12/14/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Ming-Chieh, Chen, Wei-ge
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Azad, Abul K.
• Application Number:
  US09/211,277
• Time in Patent Office: 862 Days
• Field of Search: 705/500, 705/501, 705/502, 705/503, 705/504
• US Class Current: 704/503
• 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

Abstract

A technique for entropy coding information relating to frequency domain audio coefficients. For portions of a frequency spectrum having a predominate value of zero, a multi-level run length encoder statistically correlates sequences of zero values with non-zero values and assigns variable length code words. An encoder uses a specialized code book generated with respect to the probability of receiving an input sequence of zero-valued spectral coefficients followed by a non-zero coefficient. A corresponding decoder associates a variable length code word with a sequence of zero value coefficients adjacent a non-zero value coefficient.

Claims

1. A method of encoding audio data frequency coefficients, the method comprising:

receiving a sequence of audio data frequency coefficient symbols, wherein the sequence includes a run and an adjacent symbol, the run including R symbols each having a first value, and the adjacent symbol having a value L other than the first value;

looking up the sequence within a data structure that assigns a corresponding entropy code to the sequence based jointly upon the values for R and L for the sequence; and

outputting the corresponding entropy code for the sequence.

2. A method according to claim 1, wherein the first value is zero, and L is non-zero.

3. A computer readable medium having encoded thereon instructions for directing a computer to perform the method of claim 1.

4. The method of claim 1 wherein the corresponding entropy code for the sequence is an escape code.

5. A method of decoding entropy encoded audio data frequency coefficients, comprising:

receiving an entropy code representing a sequence of audio data frequency coefficient symbols;

looking up the entropy code within a data structure that assigns a corresponding sequence of symbols to the entropy code, wherein the corresponding sequence includes a run of symbols having a first value, the run repeating for R symbols, and wherein the corresponding sequence further includes an adjacent symbol having a value L other than the first value; and

outputting the sequence of audio data frequency coefficient symbols corresponding to the entropy code.

6. A method according to claim 5 further comprising:

determining whether the entropy code is an escape code; and

when the entropy code is an escape code, identifying an escape code event sequence of audio data frequency coefficient symbols, and outputting such escape code event sequence.

7. A computer readable medium having encoded thereon instructions for directing a computer to perform the method of claim 6.

8. A method of creating an entropy code book for encoding audio data frequency coefficient symbols with an entropy encoder, the method comprising:

creating a data structure containing a plurality of pairings for input sequences of audio data frequency coefficient symbols, where each pairing jointly represents a repeating run of symbols having a first value and an adjacent symbol having a value L other than the first value, where the length of the repeating run is R;

determining a probability of occurrence of each pairing; and

assigning an entropy code to each pairing according to its probability of occurrence.

9. The method of claim 8, further comprising:

setting a probability threshold;

wherein each pairing having a probability of occurrence below the probability threshold is assigned an escape code.

10. A method according to claim 8, wherein R represents a length value for a run of zero value audio frequency coefficient symbols.

11. A computer readable medium having encoded thereon instructions for directing a computer to perform the method of claim 8.

12. A system for encoding audio data frequency coefficients, the system comprising:

means for receiving a sequence of audio data frequency coefficient symbols, wherein the sequence includes a run and an adjacent non-zero coefficient symbol, the run repeating for R zero coefficient symbols;

means for looking up the sequence within a data structure that assigns a corresponding entropy code to the sequence based jointly upon the values for R and L for the sequence;

means for outputting the corresponding entropy code for the sequence.

13. A system according to claim 12, further comprising:

a signal transformer for converting a time-domain input signal to a frequency-domain audio sequence; and

a quantizer for quantizing the frequency-domain audio sequence into the sequence of audio data frequency coefficient symbols.

14. A system for decoding entropy encoded audio data frequency coefficients, comprising:

means for receiving an entropy code representing a sequence of audio data frequency coefficient symbols;

means for looking up the entropy code within a data structure that assigns a corresponding sequence of coefficient symbols to the entropy code, wherein the corresponding sequence includes a run of zero coefficient symbols and an adjacent non-zero coefficient, the run repeating for R symbols; and

means for outputting the corresponding sequence of audio data frequency coefficient symbols.

15. A system according to claim 14, in which the entropy encoded audio data frequency coefficients include entropy codes and escape codes followed by audio data frequency coefficient symbols adjacent each such escape code, the method comprising:

means for determining whether the received entropy code is an escape code;

means for identifying audio data frequency coefficient symbols adjacent such escape code; and

means for outputting such symbols adjacent the escape code.

16. A computer-readable medium storing instructions for performing a method of encoding frequency coefficients for audio data, the method comprising:

receiving a set of frequency coefficients for audio data, the set including one or more sequences of coefficients, wherein for each sequence a pairing jointly represents a run length for the sequence and a non-zero value coefficient within the sequence, the run length indicating a run of zero value coefficients within the sequence;

for each of the one or more sequences,

assigning an entropy code based upon the pairing; and

outputting the entropy code.

17. The computer-readable medium of claim 16 wherein for an improbable sequence, the entropy code is an escape code, the method further comprising:

after outputting the escape code, outputting coefficients representative of the improbable sequence.

18. The computer-readable medium of claim 16 wherein for each of the one or more sequences, the run length is zero or more.

19. The computer-readable medium of claim 16 wherein for each of the one or more sequences, the non-zero value coefficient follows the run of zero value coefficients within the sequence.

20. A computer-readable medium storing instructions for performing a method of decoding entropy-coded frequency coefficients for audio data, the method comprising:

receiving one or more entropy codes for a set of frequency coefficients for audio data;

for each of the one or more entropy codes, assigning a sequence of coefficients to the entropy code, the sequence including a non-zero value coefficient and a run of zero value coefficients, wherein the run length of the run is zero or more; and

outputting coefficients based upon the assigned sequences.

21. The computer-readable medium of claim 20 wherein for the sequence, the non-zero value coefficient follows the run of zero value coefficients.