Entropy coding by adapting coding between level and run-length/level modes

ES 2 297 083 T3

DESCRIPTION

Entropic coding by adaptation of the coding between modes by length of execution and by level.

Field

The present invention relates to adaptive entropic coding of audio data. For example, an audio encoder switches between Huffman encoding of direct levels of quantized audio data and arithmetic encoding of lengths and cadence levels of quantized audio data.

Related application data

The following US Patent applications, filed simultaneously, are related to the present application: 1) US Provisional Patent Application Serial No. 60 / 408,517, entitled "Architecture and Techniques for Audio Coding and Decoding", filed on September 4, 2002, and 2) US Provisional Patent Application Serial no. 60 / 408,432, entitled "Lossy and Lossless Unified Audio Compression", filed on September 4, 2002.

Background

With the introduction of compact discs, digital wireless phone networks, and the provision of audio over the Internet, digital audio has become trivial. Engineers use a variety of techniques to efficiently process digital audio while maintaining the quality of digital audio. Understanding these techniques helps to understand how audio information is represented and processed on a computer.

I. Representation of Audio Information on a Computer

A computer processes audio information as a series of numbers that represent audio information. For example, a simple number can represent an audio sample, which has an amplitude value (that is, a sound intensity) at a particular instant. Several factors affect the quality of the audio information, including sample depth, sample rate, and channel mode.

Sample depth (or precision) indicates the range of numbers used to represent a sample. The greater the number of possible values ​​for the sample, the higher the quality because the number can capture more slight variations in amplitude. For example, an 8-bit sample has 256 possible values, while a 16-bit sample has 65,536 possible values.

Sample rate (usually measured as the number of samples per second) also affects quality. The higher the sampling frequency, the higher the quality because more sound frequencies can be represented. Some common sample rates are 8,000, 11,025, 22,050, 32,000, 44,100, 48,000, and 96,000 samples / second.

Table 1 shows various audio formats with different quality levels, along with corresponding raw bit rate costs.

TABLE 1

Bit rates for different quality audio information

<td>Quality</td><td>Sample Depth (bits / sample)</td><td>Sampling Rate (samples / second)</td><td>Mode</td><td>Gross Bit Rate (bits / second)</td>

<td>Internet telephony</td><td> 8</td><td> 8.000</td><td>monkey</td><td> 64.000</td>

<td>Telephone</td><td> 8</td><td> 11.025</td><td>monkey</td><td> 88.200</td>

<td>CD Audio</td><td> 16</td><td> 44.100</td><td>stereo</td><td> 1.411.200</td>

<td>High quality audio</td><td> 16</td><td> 48.000</td><td>stereo</td><td> 1.536.000</td>

As Table 1 shows, the cost of high quality audio information such as CD audio is high bit rate. High-quality audio information consumes large amounts of computer storage and streaming capacity. However, companies and consumers increasingly depend on computers to create, distribute and reproduce high-quality audio content.

ES 2 297 083 T3

II. Audio Compression and Decompression

Many computers and computer networks lack the resources to process raw digital audio. Compression (also known as encoding) reduces the cost of storing and transmitting audio information by converting the information to a lower bit rate form. Compression can be lossless (where quality is not impaired) or lossy (where quality is impaired, but bit rate reduction through lossless compression is more drastic). Decompression (also called decoding) extracts a reconstructed version of the original information from the compressed form.

In general, the goal of audio compression is to represent audio signals digitally to provide maximum signal quality with the fewest possible bits. A conventional audio encoder / decoder ("codec") system uses subband / transform encoding, quantization, rate control, and variable length encoding to achieve compression. Quantization and other lossy compression techniques introduce potentially audible noise into the audio signal. The audibility of noise depends on how much noise there is and how much of that noise the listener perceives. The first factor mainly refers to the objective quality, while the second factor depends on the human perception of sound. Conventional audio coding then losslessly compresses the quantized data using variable length coding to further reduce the bit rate.

A. Lossy Audio Data Compression and Decompression

Conventionally, an audio encoder uses a variety of different lossy compression techniques. These lossy compression techniques typically include frequency transformations, perceptual weighting / modeling, and quantization. Corresponding decompression includes inverse quantization, inverse weighting, and inverse frequency transforms.

Frequency transformation techniques convert data in a way that makes it easier to separate perceptually important information from perceptually unimportant information. Less important information can then be subjected to more lossy compression, while more important information is reserved, in order to provide the best perceived quality for a given bit rate. A frequency transformer typically receives the audio samples and converts them to frequency domain data, sometimes referred to as frequency coefficients or spectral coefficients.

Most of the energy in natural sounds such as speech and music is concentrated in the low frequency range. This means that statistically the higher frequency ranges will have more frequency coefficients that are zero or close to zero, reflecting the lack of energy in the higher frequency ranges.

Perceptual modeling includes processing audio data in accordance with a model of the human auditory system to improve the perceived quality of the reconstructed audio signal for a given bit rate. For example, an auditory model typically considers the range of human hearing and critical bands. Using the results of perceptual modeling, an encoder configures the noise (eg, quantization noise) of the audio data with the goal of minimizing the audibility of the noise for a given bit rate. While the encoder must sometimes introduce noise (eg quantization noise) to reduce the bit rate, weighting allows the encoder to put more noise in bands where it is less audible, and vice versa.

Quantization maps ranges of input values ​​to single values, introducing irreversible losses of information or quantization noise, as well as allowing an encoder to regulate the quality and bit rate of the output. Sometimes the encoder performs the quantization in conjunction with a rate controller that adjusts the quantization to regulate the bit rate and / or quality. There are several classes of quantization, including adaptive and non-adaptive, scalar and vector, uniform and non-uniform. Perceptual weighting can be considered as a form of non-uniform quantification.

Inverse quantization and inverse weighting reconstruct the weighted, quantized frequency coefficient data to an approximation of the original frequency coefficient data. The inverse frequency transformer then converts the frequency coefficient data into reconstructed time domain audio samples.

B. Lossless Audio Data Compression and Decompression

Conventionally, the audio encoder uses one or more of a variety of different lossless compression techniques. In general, lossless compression techniques include run-length encoding, Huffman encoding, and arithmetic encoding. Corresponding decompression techniques include run-length decoding, Huffman decoding, and arithmetic decoding.

Run-length encoding is a well-known, simple compression technique used for camcorders, text, and other types of content. In general, run-length encoding replaces a sequence (that is, a run) of consecutive symbols that have the same value, with the value and length of the sequence.

ES 2 297 083 T3

In run length decoding, the sequence of consecutive symbols is reconstructed from the run value and run length. Numerous run-length encoding / decoding variations have been developed. For additional information on run-length encoding / decoding and some of its variations, see, for example, Bell et al., Text Compression, Prentice Hall PTR, pages 105-107, 1990; Gibson et al., Digital Compression for Multimedia, Morgan Kaufmann, pages 17.62, 1998; US Patent No. 6,304,928 to Mairs, et al .; US Patent No. 5,883,633 to Gill et al., And US Patent No. 6,233,071 to Chaddha.

Run-level encoding is similar to run-length encoding in that sequences of consecutive symbols that have the same value are replaced by lengths of sequences. The value of the sequences is the predominant value (for example, 0) in the data, and the sequences are separated by one or more levels that have a different value (for example, a value that is not zero).

The results of sequence length encoding (eg, sequence values ​​and sequence lengths) or sequence level encoding can be Huffman encoded to further reduce the bit rate. If so, the Huffman encoded data is Huffman decoded prior to sequence length decoding.

Huffman encoding is another well-known compression technique used for camcorders, text, and other types of content. In general, a Huffman code table associates variable-length Huffman codes with unique symbol values ​​(or unique combinations of values). Shorter codes are assigned to more probable symbol values, and longer codes are assigned to less probable symbol values. The probabilities are calculated for typical examples of some kind of content. Or, the probabilities are calculated for newly coded data or data to be coded, in which case the Huffman codes are adapted to the change probabilities for the unique symbol values. Compared to Huffman encoding, adaptive Huffman encoding typically reduces the bit rate of compressed data by incorporating more precise probabilities for the data, but extra information may also need to be transmitted that specifies Huffman codes.

To encode symbols, the Huffman encoder substitutes symbol values ​​for variable-length Huffman codes associated with the symbol values ​​in the Huffman code table. To decode, the Huffman decoder replaces the Huffman codes with the code values ​​associated with the Huffman codes.

In scalar Huffman encoding, a Huffman code table associates a unique Huffman code with a value, for example, a direct level of a quantized data value. In Huffman vector encoding, a Huffman code table associates a unique Huffman code with a combination of values, for example, a group of direct levels of quantized data values ​​in a particular order. Huffman vector encoding can lead to better bit rate reduction than Huffman scalar encoding (eg, allowing the encoder to fractionally exploit the probabilities of Huffman binary codes). On the other hand, the encryption and decryption code for Huffman vector encoding can be extremely large when the simple codes represent large groups of symbols or the symbols have large ranges of potential values ​​(due to the large number of potential combinations). For example, if the size of the alphabet is 256 (for values ​​from 0 to 255 per symbol), and the number of symbols per vector is 4, the number of potential combinations is 256⁴ = 4,294,967,296. This consumes memory and processing resources when calculating the encryption and decryption code and finding the Huffman codes, and it consumes transmission resources when transmitting the encryption and decryption code.

Numerous encoding / decoding variations of Huffman have been developed. For additional information on Huffman encoding / decoding and some of its variations, see, for example, Bell et al., Text Compression, Prentice Hall PTR, pages 105-107, 1990; Gibson et al., Digital Compression for Multimedia, Morgan Kaufmann, pages 17-62, 1998.

US Patent No. 6,223,162 to Chen et al., Describes multi-level encoding of sequence length of audio data. A frequency transformation produces a series of frequency coefficient values. For portions of a frequency spectrum in which the predominant value is zero, a sequence length multi-level encoder correlates the sequences of zero values ​​with nonzero values, and assigns variable length code words. An encoder uses a specialized encryption and decryption code, regarding the probability of receiving an input sequence of zero-valued spectral coefficients, followed by a non-zero value coefficient. A corresponding decoder associates a variable-length codeword with a sequence of coefficients of zero value and of adjacent coefficients of non-zero value.

US Patent No. 6,377,930 to Chen et al., Describes variable encoding versus variable length of audio data. An encoder assigns a variable length code to a variable size group of frequency coefficient values.

US Patent No. 6,300,888 to Chen et al., Describes entropic encoding mode switching for encoding audio in the frequency domain. A frequency domain audio encoder makes a selection between different entropic encoding modes according to the characteristics of an input stream.

ES 2 297 083 T3

In particular, the input stream is divided into frequency ranges according to statistical criteria derived from the statistical analysis of a typical or real input to be encoded. Each range is assigned an entropy encoder optimized to encode the data type of the range. During encoding and decoding, a mode selector applies the correct procedure to the different frequency ranges. The contours of the partition can be decided in advance, allowing the decoder to know implicitly which decoding procedure to apply to the encoded data. Or, adaptive arrangements can be used, in which the contours are flagged in the output stream to indicate an encoding mode change for subsequent data. For example, a partition contour separates primarily zero-quantized frequency coefficients from primarily non-zero quantized coefficients, and then applies optimized encoders for such data.

For additional details about Chen's patents, see the patents themselves.

Arithmetic coding is another well-known compression technique used for camcorders and other types of content. Arithmetic encoding is sometimes used in applications where the optimal number of bits to encode a given input symbol is a fractional number of bits, and in cases where there is a statistical correlation between certain individual input symbols. Arithmetic encoding generally includes representing an input sequence as a unique number within a given range. Typically, the number is a fractional number between 0 and 1. The symbols in the input sequence are associated with ranges that occupy portions of the space between 0 and 1. The ranges are calculated based on the probability of the symbol occurring particular in the input sequence. The fractional number used to represent the input sequence is constructed with reference to the ranges. Therefore, the probability distributions for the input symbols are important in arithmetic coding schemes.

In context-based arithmetic coding, the different probability distributions for the input symbols are associated with different contexts. The probability distribution used to encode the input sequence changes when the context changes. Context can be calculated by measuring different factors that are expected to affect the probability that a particular input symbol will appear in an input sequence. For additional information on arithmetic encoding / decoding and some of its variations, see Nelson, The Book of Data Compression, “Huffman's Best: Arithmetic Coding,” Chapter 5, pp. 123-65 (1992).

Lossless compression and decompression are used by various codec systems and standards, including versions of Microsoft Corporation's Windows Media Audio [“WMA”] encoder and decoder. Other codec systems are provided or specified by Motion Picture Experts Group's Audio Layer 3 [“MP3”] standard, Motion Picture Experts Group 2's Advanced Audio Coding [“AAC”] standard, and Dolby AC3. For additional information, see the respective standards or technical publications.

The article "ASPEC Coding" by K. Arandenburg, 10 ° Proc. AES Publ. Conference, pp-71-80, describes transformation coding combined with entropic coding.

In any case, the advantages of the prior techniques and systems for lossless compression of audio data do not have the advantages of the present invention.

Summary

In summary, the detailed description is directed to various techniques and tools for adaptive entropic encoding and decoding of audio data. The various techniques and tools can be used in combination or independently. The scope of the invention is defined in independent claims 1, 17, 19, 32, 34 and 41.

In one aspect, an encoder encodes a first portion of an audio data stream in a direct variable-dimension vector Huffman encoding mode, switches to a sequence-level encoding mode at a switch point, and encodes a second portion in sequence-level encoding mode (eg, context-based arithmetic encoding, Huffman encoding, Huffman vector encoding). For example, the first portion consists primarily of non-zero quantized audio coefficients, and the second portion consists primarily of zero-value quantized audio coefficients. The switch point can be predetermined (eg, checking the efficiency of encoding the sequence using the switch point) or adaptively determined. The encoder can send a signal indicative of the switch point in a stream of coded bits.

In another aspect, a decoder decodes a first portion of an encoded sequence in a direct variable dimension vector Huffman decoding mode, switches to a sequence-level decoding mode at a switch point, and decodes a second portion at the sequence-level decoding mode (eg, context-based arithmetic decoding, Huffman decoding, Huffman vector decoding). Prior to switching, the decoder may receive a signal indicative of the switching point.

ES 2 297 083 T3

In another aspect, an encoder or decoder, encodes or decodes a first portion of a sequence in a context-based direct arithmetic mode, switches to a sequence-level mode at a switch point, and encodes or decodes a second portion in sequence level mode. The sequence level mode can be the context-based arithmetic mode.

In another aspect, an encoder selects a first code table from a set of plural code tables based on the number of symbols in a first vector, and represents the first vector with a code from the first code table. The first code table may include codes for representing probable vectors having a number of symbols, and an escape code for least probable vectors. The encoder also encodes a second vector that has a different number of symbols. For example, the first vector has a greater number of symbols than the second vector, and has a higher probability of occurrence than the second vector. To encode the second vector, the encoder may choose a second, different code table based on the number of symbols in the second vector. If the second vector has a symbol, the encoder can represent the second vector using a tableless encoding technique.

In another aspect, a decoder decodes a first vector upon receiving a first code, and looks up the first code in a first code table. If the first code is an escape code, the decoder receives and decodes a second code that is not in the first table. If the first code is not an escape code, the decoder looks for symbols for the first vector in the first code table, and includes them in a decoded data stream. The number of symbols in the first vector forms the basis for whether the first code is an escape code. The decoder can decode the second code by looking for it in a second table. If the second code is an escape code, the decoder receives and decodes a third code that represents the first vector that is not in the second table. If the second code is not an escape code, the decoder looks for symbols for the first vector in the second table and includes the symbols in the decoded data stream.

In another aspect, an encoder encodes coefficients of audio data using a syntax encoding technique. If a coefficient is within a first range of values, the encoder encodes the coefficient with a one-bit code followed by an 8-bit encoded value. For other ranges of values, the encoder encodes the coefficient with a two-bit code followed by a 16-bit encoded value, a three-bit code followed by a 24-bit encoded value, or a different three-bit code followed by a 31-bit encoded value.

In another aspect, in a Huffman vector coding scheme, an encoder determines a Huffman code from a group of such codes for use in encoding a vector, and encodes the vector using the Huffman code. The determination of the code is based on the sum of the values ​​of the audio data symbols in the vector. If the Huffman code is an escape code, it indicates that an n-dimensional vector should be encoded as x x / n-dimensional vectors using at least one different code table. The encoder can compare the sum to a threshold that depends on the number of symbols in the vector. For example, the threshold is 6 for 4 symbols, 16 for 2 symbols, or 100 for 1 symbol.

In another aspect, an encoder receives a stream of audio data and encodes at least part of the stream using context-based arithmetic encoding. A decoder receives an encoded sequence of audio data coefficients and decodes at least part of the encoded sequence using context-based arithmetic decoding.

In another aspect, an encoder encodes coefficients of audio data using context-based arithmetic encoding. One or more contexts have associated probability distributions that represent coefficient probabilities. The encoder adaptively determines a context for a current coefficient based, at least in part, on a mode of representation of the current coefficient, and encodes the current coefficient using the context. For example, if the representation mode is direct, the encoder adaptively determines the context based, at least in part, on the direct levels of previous coefficients (eg, the two coefficients immediately before the current coefficient). If the rendering mode is stream level, the encoder adaptively determines the context based, at least in part, on the percentage of zero-valued coefficients, and the previous sequence length of zero-valued coefficients in the audio stream of entrance. If the representation mode is sequence level, the encoder adaptively determines the context based, at least in part, on the current sequence length of zero-valued coefficients, the previous sequence length of zero-valued coefficients, and the direct levels of previous coefficients.

In another aspect, an encoder or decoder encodes or decodes a first portion of audio data using direct encoding or decoding, keeping a count of consecutive coefficients equal to a predominant value (eg, 0). If the count exceeds a threshold, the encoder or decoder encodes or decodes a second portion of the audio data using sequence level encoding or decoding. The threshold can be static or adaptively determined. The threshold may depend on the size of the coefficient block. For example, the threshold can be 4 for a block of 256 coefficients, or 8 for a block of 512 coefficients.

In another aspect, an encoder or decoder encodes or decodes a first portion of a sequence using a first code table, and a second portion of the sequence using a second code table. The first table is used when the longest sequences of consecutive coefficients equal a predo6 value

ES 2 297 083 T3 miners (eg 0) are the most likely, and the second table is used when shorter sequences of consecutive coefficients of equal value are the most likely. The table that is used can be indicated by a signal bit.

The features and advantages of adaptive entropic encoding and decoding techniques will become apparent from the following detailed description of various embodiments, made with reference to the accompanying drawings.

Brief description of the drawings

Figure 1 is a block diagram of a suitable computing environment in which the described embodiments can be implemented;

Figure 2 is a block diagram of an audio encoder in which the described embodiments can be implemented;

Figure 3 is a block diagram of an audio decoder in which the described embodiments can be implemented;

Figure 4 is a flow chart showing a generalized multi-mode audio coding technique;

Figure 5 is a flow chart showing a multi-mode audio coding technique with adaptive switch point calculation;

Figure 6 is a flow chart showing a generalized multi-mode audio decoding technique;

Figure 7 is a flow chart showing a generalized variable dimension Huffman vector coding technique;

Figure 8 is a flow chart showing a detailed technique for encoding audio data using variable dimension Huffman vector encoding;

Figure 9 is a flowchart showing a technique for variable dimension Huffman vector coding of direct signal levels, where the encoder adaptively determines a switch point for switching to coding of sequence lengths and signal levels;

FIG. 10 is a flow chart showing a generalized variable dimension Huffman vector decoding technique;

Figure 11 is a flow chart showing a detailed technique for decoding encoded vectors using variable dimension Huffman vector encoding;

Figure 12 is a flow chart showing a technique for variable dimension Huffman vector decoding of direct signal levels where the decoder adaptively determines a switch point to switch to decoding of sequence lengths and signal levels. ;

Figures 13A-13D are probability distributions for non-sequence length levels, in a context-based arithmetic coding scheme;

Figures 14A-14H are probability distributions for different sequence lengths in a context-based arithmetic coding scheme;

Figures 15A-15H are probability distributions for encoded levels of sequence length in a context-based arithmetic coding scheme;

Figure 16 is a flowchart showing a technique for context-based, direct arithmetic coding of coefficients, where the encoder determines a switch point to switch to encoding of sequence lengths and levels, and Figure 17 is a flowchart showing a context-based arithmetic decoding technique, where the decoder adaptively determines a switch point to switch to decoding of sequence lengths and signal levels.

Detailed description

In the described embodiments, an audio coder performs various adaptive entropic coding techniques. Adaptive entropic coding techniques improve encoder performance, reducing bit rate and / or improving quality. A decoder executes the corresponding entropic decoding techniques.

ES 2 297 083 T3

While the techniques have been described here as part of a single integrated system, the techniques can be applied separately, potentially in combination with other techniques.

The audio encoder and decoder process discrete audio signals. In the described embodiments, the audio signals are coefficients quantized from frequency transformed audio signals. Alternatively, the encoder and decoder process another kind of discrete audio signal or a discrete signal representing video or other kind of information.

In some embodiments, an audio encoder adaptively switches between encoding of direct signal levels and encoding of sequence lengths and signal levels. The encoder encodes the direct signal levels using scalar Huffman codes, Huffman vector codes, arithmetic coding, or another technique. In sequence-level / length encoding (also known as sequence-level encoding), each sequence length represents a sequence of zero or more zeros, and each signal level represents a non-zero value. In the sequence signal event space, the encoder encodes sequence lengths and levels in that event space, using Huffman codes, arithmetic coding, or another technique. A decoder performs a corresponding adaptive switching during decoding. Adaptive switching occurs when a threshold number of levels of zero value is reached. Alternatively, the encoder and decoder switch based on additional or different criteria.

In some embodiments, an audio encoder makes use of variable dimension Huffman vector encoding. Variable-dimension Huffman vector encoding allows the encoder to use Huffman codes to represent more likely combinations of symbols that use higher-dimensional vectors, and less likely combinations of symbols that use smaller-dimensional vectors or scalars. A decoder performs the corresponding variable dimension Huffman decoding.

In some embodiments, an audio encoder uses context-based arithmetic encoding. The contexts used by the encoder allow efficient compression of different types of audio data. A decoder performs the corresponding context-based arithmetic decoding.

In the described embodiments, the audio encoder and decoder perform various techniques. Although the operations relating to these techniques are typically described in a particular sequential order for presentation purposes, it will be understood that this manner of description encompasses less important rearrangements in terms of the order of operations. Furthermore, for the sake of simplicity, flow charts do not typically show the various ways in which particular techniques can be used in conjunction with other techniques.

I. Computing Environment

Figure 1 illustrates a generalized example of a suitable computing environment (100) in which the described embodiments can be implemented. Computing environment 100 is not intended to suggest any limitation as to the use or functionality of the invention, since the present invention can be implemented in a wide variety of general purpose or special purpose environments.

With reference to Figure 1, the computing environment (100) includes at least one processing unit (110), and memory (120). In Figure 1, the most basic configuration (130) has been enclosed within a dotted line. The processing unit (110) executes computer executable instructions, and can be a real or virtual processor. In a multi-processing system, multiple processing units execute computer-executable instructions to increase processing power. Memory 120 can be volatile memory (eg, registers, cache, RAM), non-volatile memory (eg, ROM, EEPROM, flash memory, etc.), or any combination of the two. Memory 120 stores software 180 that implements an audio encoder / decoder that performs adaptive entropy encoding / decoding of audio data.

A computing environment can have additional characteristics. For example, the computing environment (100) includes a storage device (140), one or more input devices (160), and one or more communication connections (170). An interconnection mechanism (not shown), such as a bus, a controller, or a network, interconnects the components of the computing environment (100). Typically, the operating system software (not shown) provides an operating environment for other software execution in the computing environment (100), and coordinates the activities of the components of the computing environment (100).

Storage (140) can be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, CD-RWs, DVDs or any other medium that can be used to store information and that can be accessed within of the computational environment (100). Storage 140 stores instructions for software 180 implementing the audio encoder / decoder that performs entropic encoding / decoding of audio data. The input device (s) 150 may be a touch input device such as a keyboard, mouse, pen or trackball, a voice input device, a scanning device. , a network adapter, or other device that provides input to the computing environment (100). For audio, the input device (s) (150) may be a sound card or similar device that accepts an audio input in analog or digital form, or a CD-ROM drive that provide audio samples to the computing environment. They)

ES 2 297 083 T3 output device (s) (160) may be a display screen, printer, speaker, CD / DVD writer, network adapter, or other device that provides output from the computing environment (100).

The communication connection (s) (170) allows communication by means of communication with another computing entity. The communication medium carries information such as computer executable instructions, compressed audio information, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics arranged or changed to encode information in the signal. By way of example, and without limitation, communication means include wired or wireless techniques implemented with an electrical, optical, RF, infrared, acoustic, or other carrier.

The invention can be described in the general context of computer-readable media. Computer-readable media consists of any available media that can be accessed with a computing environment. By way of example, and without limitation, within the computing environment (100), computer-readable media includes memory (120), storage media (140), communication media, and combinations of any of these.

The invention can be described in the general context of computer-executable instructions, such as those included in program modules, that are executed in a computing environment on a real or virtual target processor. In general, program modules include routines, programs, libraries, objects, classes, components, data structures, etc., that perform particular tasks or that implement particular types of abstract data. The functionality of the program modules can be combined or divided into program modules as desired, in various embodiments. Computer-executable instructions for program modules can be executed within a local or distributed computing environment.

For presentation purposes, the detailed description uses terms such as "analyze", "send", "compare" and "check" to describe computer operations in a computing environment. These terms are high-level abstractions for operations performed by a computer, and should not be confused with acts performed by a human being. The actual computer operations that correspond to these terms vary depending on the implementation.

II. Generalized Audio Encoder and Decoder

Figure 2 is a block diagram of a generalized audio encoder (200) in which the described embodiments can be implemented. Encoder 200 performs adaptive entropy encoding of audio data. Figure 3 is a block diagram of a generalized audio decoder (300) in which the described embodiments can be implemented. Decoder 300 decodes encoded audio data.

The relationships shown between modules within the encoder and decoder indicate a flow of information in an example encoder and decoder; no other relationships are shown for simplicity. Depending on the implementation and the type of compression desired, encoder or decoder modules can be added, omitted, divided into multiple modules, combined with other modules, and / or replaced by similar modules. In alternative embodiments, encoders or decoders with different modules and / or with other configurations perform adaptive entropic encoding and decoding of audio data.

A. Generalized Audio Encoder

The generalized audio encoder (200) includes a selector (208), a multi-channel pre-processor (210), a mosaic divider / configurator (200), a frequency transformer (230), a modeler (240) of perception, a weigher (242), a multi-channel transformer (250), a quantizer (260), an entropy encoder (260), a controller (280), a mixed / pure lossless encoder (272) and an encoder (274) associated entropy, and a bitstream multiplexer (290) ["MUX"]. The following is a description of some of the encoder modules (200). For description of other encoder 200 modules of some embodiments, see the applications referenced in the Related Application Data section.

Encoder 200 receives a time series of input audio samples 205 at a sampling depth and frequency in pulse code modulated ["PCM"] format. The input audio samples (205) can be multi-channel audio (eg, stereo, surround mode) or mono. The encoder (200) compresses the audio samples (205) and multiplexes the information produced by the various modules of the encoder (200) to output a stream of bits (295) in a format such as a Windows Media Audio format [ "WMA"] or Advanced Streaming Format ["ASF"]. Alternatively, encoder 200 works with other input and / or output formats.

Initially, selector 208 chooses between multiple encoding modes for audio samples 205. In Figure 2, selector 208 switches between two modes: a mixed / pure lossless encoding mode and a lossy encoding mode. The lossless encoding mode includes the mixed / pure lossless encoder 272, and is typically used for high quality (and high bit rate) compression. The lossy coding mode includes components such as the weigher (242) and the quantizer (260), and is typically used for compression of adjustable quality (and controlled bit rate). The selection decision in selector 208 depends on user input (e.g. a user selecting lossless encoding

ES 2 297 083 T3 to make high-quality audio copies) or other criteria. In other circumstances (for example, when lossy compression fails to deliver adequate quality or overproduces bits), the encoder 200 may switch from lossy encoding to mixed / pure lossless encoding for one frame. or a set of pictures.

The frequency transformer (230) receives the audio samples (205) and converts them to frequency domain data. The frequency transformer (230) outputs blocks of frequency coefficient data for the weighting (242), and outputs collateral information such as block sizes for the MUX (290). The frequency transformer (230) outputs the frequency coefficients and collateral information to the perception modeler (240).

The perception modeler (240) models properties of the human auditory system to improve the perceived quality of the reconstructed audio signal for a certain bit rate. In general, the perception modeler (240) processes the audio data in accordance with an auditory model, and then provides information to the weigher (242) that can be used to generate weighting factors for the audio data. The perception shaper (240) uses any one of several auditory models and passes arousal pattern information or other information to the weigher (242).

As the quantization band weigher, the weighting factor (242) generates weighting factors for a quantization matrix based on the information received from the perception modeler (240), and applies the weighting factors to the data received from the transformer (230 ) of frequency. The weight (242) outputs collateral information such as the set of weighting factors for the MUX (290). As the channel weigher, the weighted 242 then generates channel-specific weighting factors, based on the information received from the perception modeler (240), and also based on the quality of the locally reconstructed signal. These scalar weights allow the reconstructed channels to have approximately uniform quality. The weigher (242) outputs weighted blocks of coefficient data for the multichannel transformer (250), and outputs collateral information such as the set of channel weighting factors for the MUX (290). Alternatively, encoder 200 uses another form of weighting or non-continuous weighting.

For multi-channel audio data, the multiple channels of noise-shaped frequency coefficient data produced by the weigher 242 are many times correlated. To take advantage of this correlation, the multi-channel transformer 250 can apply a multi-channel transformation to the audio data. The multi-channel transformer (250) produces collateral information for the MUX (290) indicating, for example, the multi-channel transforms used and the parts of the multi-channel transformed frames.

The quantizer (260) quantizes the output of the multi-channel transformer (250), producing quantized coefficient data for the entropy encoder (270) and collateral information including quantization step sizes for the MUX (290). Quantization introduces irreversible information losses, but also allows the encoder (200) to regulate the quality and bit rate of the output bit stream (295) in conjunction with the controller (280). In some embodiments, quantizer 260 is an adaptive, uniform, scalar quantizer. In alternative embodiments, the quantizer is a non-uniform quantizer, a vector quantizer, and / or a non-adaptive quantizer, or uses a different form of adaptive, uniform, scalar quantization.

Entropy encoder (270) losslessly compresses quantized coefficient data received from quantizer (260). In some embodiments, the entropy encoder 270 uses adaptive entropy coding as described in the section that follows. The entropy encoder (270) can calculate the number of bits spent encoding the audio information and pass this information to the speed / quality controller (280).

Controller 280 works with quantizer 260 to regulate the bit rate and / or quality of the encoder 200 output. Controller 280 receives information from other encoder modules 200 and processes the received information to determine given current conditions of the desired quantization factors. The controller (280) outputs the quantization factors for the quantizer (260) in order to satisfy quality and / or bit rate requirements.

The lossless mixed / pure lossless encoder (272), and associated entropy encoder (274), compress audio data for mixed / pure lossless encoding mode. Encoder 200 uses mixed / pure lossless encoding mode for an entire sequence, or switches between encoding modes on a frame-by-frame or other basis.

The MUX (290) multiplexes the collateral information received from the other modules of the audio encoder (200) along with the entropy encoded data received from the entropy encoder (270). The MUX (290) outputs the information in a WMA format or in another format that is recognized by an audio decoder. The MUX (290) includes a virtual buffer that stores the bit stream (295) to be outputted by the encoder (200). The current buffer fill amount, the rate of change of the buffer fill amount, and other characteristics of the buffer can be used by the controller 280 to regulate the quality and / or speed. bit rate for different applications (eg constant quality / variable bit rate, or constant low bit rate / variable quality).

ES 2 297 083 T3

B. Generalized Audio Decoder

Referring to Figure 3, the generalized audio decoder (300) includes a bit stream demultiplexer (310) ["DEMUX"], one or more entropy decoders (320), a mixed / lossless decoder (322) pure, a configuration decoder (330), an inverse multi-channel transformer (340), an inverse quantizer / weigher (340), an inverse frequency transformer (360), an overlapper / adder (370), and a post processor ( 380) multi-channel. Decoder 300 is sometimes simpler than encoder 300 because decoder 300 does not include modules for speed / quality control or perception modeling. The following is a description of some of the decoder modules (300). For a description about other modules of the decoder 300 of some of the embodiments, see the applications referenced in the Related Application Data section.

The decoder (300) receives a stream of bits (305) of compressed audio information in a WMA or other format. The bit stream (305) includes entropy encoded data, as well as collateral information from which the decoder (300) reconstructs the audio samples (395).

The DEMUX (310) analyzes the information in the bit stream (305) and sends information to the decoder modules (300). The DEMUX 310 includes one or more buffers to compensate for short-term variations in bit rate due to fluctuations in audio complexity, network fluctuations, and / or other factors.

The entropy decoder (s) (320) losslessly decompresses entropy codes received from the DEMUX (310). For the sake of simplicity, an entropy decoder module has been depicted in Figure 3, although different entropy decoders can be used for lossy and lossless encoding modes, or even within modes. Also, for the sake of simplicity, Figure 3 does not show the mode selection logic. The entropy decoder (320) typically applies the inverse of the entropy coding technique used in the encoder (200). When decoding compressed data in lossy encoding mode, the entropy decoder 320 produces quantized frequency coefficient data.

The mixed / pure lossless decoder (322) and associated entropy decoder (s) (320) decompress lossless encoded audio data for mixed / pure lossless encoding mode. Decoder 300 uses a particular decoding mode for an entire sequence, or switches decoding modes on a frame-by-frame or other basis.

The inverse multi-channel transformer (340) receives the entropy decoded quantized frequency coefficient data from the entropy decoder (s) (320) as well as collateral information from the DEMUX (310) indicating, for For example, the multi-channel transformation used and the transformed parts or frames.

The inverse quantizer / weigher (350) receives quantization factors, as well as quantization matrices from the DEMUX (310), and receives quantized frequency coefficient data from the multi-channel transformer (340). The inverse quantizer / weigher 350 decompresses the quantization factor / matrix information that has been received as necessary, and then performs the inverse quantization and weighting.

The inverse frequency transformer (360) receives the frequency coefficient data presented at the output by the inverse quantizer / weigher (350), as well as all collateral information from the DEMUX (310). The inverse frequency transformer (360) applies the inverse of the frequency transformation used in the encoder, and outputs blocks for the overlapper / adder ( 370).

The overlapper / adder (370) receives decoded information from the inverse frequency transformer (360) and / or from the mixed / pure lossless decoder (322). The overlapper / adder (370) overlaps and adds audio data as necessary, and interleaves frames or other sequences of audio data encoded in different modes.

III. Adaptive Entropy Entropy Encoding / Decoding Mode Switching

Sequence-level encoding methods are often more efficient than direct-level encoding when an input sequence contains many occurrences of a single value (eg, 0). However, since non-zero quantized transform coefficients are common in audio data input sequences, especially at the lower frequencies, sequence level coding is not efficient across the entire frequency range. Also, in higher quality audio, non-zero quantized transform coefficients are more common even at higher frequencies. (In higher quality audio, the quantization levels are typically smaller.) Therefore, in some embodiments, an encoder such as encoder 200 of Figure 2 performs a multi-mode encoding technique that can make use of sequence level encoding for a portion of the data input sequence. audio, and direct level encoding for another portion of the sequence. A decoder, such as decoder 300 of Figure 3, executes a corresponding multi-mode decoding technique.

ES 2 297 083 T3

A. Adaptive Entropy Coding Mode Switching

Referring to Figure 4, in a multi-mode encoding technique 400, the encoder first encodes signal levels into an input stream 410 directly. For example, the encoder performs variable dimension Huffman encoding, context-based arithmetic encoding, or other entropic encoding technique directly on signal levels.

At a switch point during encoding, the encoder changes the encoding scheme 420. The encoder can change the encoding scheme at a predetermined switch point, or the encoder can analyze the input data to determine an appropriate point to change the encoding schemes. For example, the encoder can analyze an input sequence to find the best point at which to switch to sequence level encoding, by sending the switch point to the decoder in the output bit stream. Or, the encoder may calculate the switch point adaptively by counting consecutive zeros (or alternatively, another predominant value) in the input data, and switch to sequence level encoding when a particular threshold number of consecutive zeros has been counted. The decoder can calculate the switch point in the same way, so that the switch point need not be included in the bit stream. Or, the encoder and decoder use some other criteria to determine the switch point.

After the switch point, the encoder encodes the remaining signal levels using sequence level encoding (430). For example, the encoder performs Huffman encoding, context-based arithmetic encoding, or other entropy encoding technique on sequence lengths and signal levels. The encoder may use the same technique (eg, context-based arithmetic encoding) before and after the switch point, or the encoder may use different techniques.

In addition, although Figure 4 and several other Figures in the application show a single switch point, additional switch points can be used to divide the input data into more than two chunks. For example, additional adaptive switch points can be set for incremental thresholds of consecutive zeros. Different coding schemes can then be applied to the different slices. Or, the encoder can experiment with different segmentation points in the sequence, weighing the encoding efficiencies for the different segmentation configurations together with the costs of signaling the different configurations for the decoder.

Figure 5 shows a multi-mode coding technique (500) with adaptive switch point calculation according to one implementation. The adaptive switch point depends on a count of consecutive zero-value coefficients. The input data are signal levels for quantized transform coefficients, incrementing from the lowest frequency coefficient to the highest frequency coefficient. In practice, the position of the switch point depends on the signal being compressed and the bit rate / quality of the encoding. Alternatively, the input data is another form and / or other organization of audio data.

To begin with, the encoder initializes several variables. Specifically, the encoder sets a sequence count variable to 0 (510) and sets a configuration state variable to "direct" (512).

The encoder receives the next QC coefficient as input (520). The encoder then checks (530) if the coefficient QC is zero. If the QC coefficient is not zero, the encoder resets the sequence count (538). In another case (that is, if the QC coefficient is zero), the encoder increments the sequence count variable (532), and checks if the current sequence count exceeds the sequence count threshold (534). The sequence count threshold can be static or it can depend on a factor such as the size of a block of coefficients (for example, a sequence count threshold of 4 for a sequence of 256 coefficients, 8 for a sequence of 512 coefficients , etc.), or it may be adaptive in some other way. If the sequence count exceeds the threshold, the encoder changes the encoding state to sequence level encoding ["RLE"] (536).

The encoder then encodes the QC coefficient if appropriate (540). (In some cases, groups of coefficients are coded together using a technique such as Huffman vector coding. In those cases, the encoder may delay the coding of the QC coefficient).

The encoder then checks (550) if the encoder should switch encoding modes. In particular, the encoder checks the encoding status. If the encoding state is no longer direct (for example, if the encoder has changed the encoding state to RLE as a result of reaching a zero coefficient threshold number), the encoder begins sequence-level encoding of the coefficients (560). (Again, in cases where groups of coefficients are coded together, the encoder may delay the switching decision until a convenient breakpoint is reached for a group of coefficients.)

If the encoder does not switch encoding modes, the encoder checks whether encoding of the coefficients has finished (570). If so, the encoder exits. Otherwise, the encoder enters the next coefficient (520) for the encoding process to continue.

ES 2 297 083 T3

B. Adaptive Entropy Decoding Mode Switching

Referring to Figure 6, in a multi-mode decoding technique (600), the decoder directly decodes encoded signal levels (610). For example, the decoder performs variable dimension Huffman decoding, context-based arithmetic decoding, or other entropy decoding technique on directly encoded signal levels.

At a switch point during decoding, the decoder changes the decoding scheme (620). If the switch point is predetermined, the decoder may receive, in the form of a banner or other notification mechanism, data that explicitly tells the decoder when to change the decoding schemes. Or, the decoder can adaptively calculate when to change the decoding schemes based on the input data it receives. If the decoder calculates the switch point, the decoder uses the same calculation technique used by the encoder to ensure that the decoding scheme changes at a correct point. For example, the decoder counts consecutive zeros (or alternatively, another predominant value) to determine the switch point adaptively. In one implementation, the decoder uses a technique corresponding to the encoding technique shown in Figure 5. Or, the decoder uses some other criteria to determine the switch point.

After the switch point, the decoder decodes the remaining sequence level encoded signal levels (630). For example, the decoder performs Huffman decoding, context-based arithmetic decoding, or other entropy decoding technique on encoded sequence lengths and signal levels. The decoder may use the same technique (eg, context-based arithmetic decoding), before and after the switch point, or the decoder may use different techniques.

IV. Huffman Variable-Dimension Encoding and Decoding

While symbols such as direct signal levels can be encoded using scalar Huffman encoding, that alternative is limited when the optimal number of bits to encode a symbol is a fractional number. Huffman scalar encoding is also limited by the inability of Huffman scalar codes to account for statistical correlation between symbols. Huffman vector encoding produces better bit rate reduction than Huffman scalar encoding (for example, allowing the encoder to exploit fractional probabilities in Huffman binary codes). And in general, higher-dimensional vectors produce better bit rate reduction than smaller-dimensional vectors. However, if a code is assigned to each possible symbol combination, the size of the encryption and decryption code increases exponentially as the dimension of the vector increases. For example, in a 32-bit system, the number of possible combinations for a 4-dimensional vector is (2³²)⁴. The search time to match a vector and find a Huffman code also increases dramatically as the size of the encryption and decryption code increases.

In some embodiments, to reduce the size of the encryption and decryption code, an encoder such as encoder 200 of Figure 2 uses a variable dimension Huffman vector encoding technique. Instead of assigning an encryption and decryption code to every possible n-dimensional combination, codes are assigned to a limited number of most probable n-dimensional vectors. If no code is assigned to a particular n-dimensional vector, the n-dimensional vector is then coded in the form of smaller-dimensional vectors (for example, two vectors of dimension n / 2), as scalars with Huffman codes, or as scalars using the no-table technique to represent discrete values. A decoder such as decoder 300 of Figure 3 reconstructs a vector by finding the code (s) for the vector and finding the associated values.

For example, in the case of 4-dimensional vectors with 256 possible values ​​per symbol, the encoder encodes the 500 most probable 4-dimensional vectors with Huffman codes, and uses an escape code to indicate other vectors. The encoder encodes the 500 most probable 2-dimensional vectors with Huffman codes and uses an escape code to indicate other vectors, which are divided and encoded with Huffman scalar codes. Thus, the encoder uses 501 + 501 + 256 codes.

In terms of determining which vectors or scalars are represented by Huffman codes in a table, and in terms of assigning own Huffman codes for the table, the encryption and decryption code construction can be static, adaptive to the previously encoded data. , or adaptive for the data to be encoded.

A. Variable-Dimension Huffman Vector Coding

Referring to Figure 7, an encoder uses a variable dimension Huffman vector coding technique (700) ["VDVH"]. For example, the encoder uses technique (700) to directly encode signal levels for frequency coefficients of audio data. Alternatively, the encoder uses technique (700) to encode another form of audio data. For simplicity, Figure 7 does not show the construction of the encryption and decryption code. The construction of the encryption and decryption code can be static, adaptive for the data previously encoded, or adaptive for the data to be encoded.

ES 2 297 083 T3

The encoder obtains (710) the next vector of n symbols. For example, the encoder gets the following 4 symbols in series.

The encoder checks (720) whether the encryption and decryption code includes a code for the vector. If so, the encoder uses (730) a simple Huffman code to encode the vector. For example, to determine how to encode an n-dimensional vector, the encoder checks an n-dimensional vector code table for a code associated with the vector. Since higher dimensional vectors typically produce bit rate savings, the encoder uses Huffman codes for the most probable n-dimensional vectors. But, to limit the size of the table, only some of the n-dimensional vectors have associated codes.

If the encryption and decryption code does not include a code for the vector, the encoder divides (740) the vector into smaller vectors and / or scalars, and encodes the smaller vectors and / or scalars. For example, the encoder divides a vector of n symbols into x vectors of n / x symbols. For each vector of n / x symbols, the encoder recursively repeats the coding technique, exiting when the vector of n / x symbols or its component vectors / scalars have been encoded with Huffman codes or (for scalars) using a technique of no-table to represent discrete values.

The encoder then checks (750) if there are any additional vectors to encode. If not, the encoder exits. Otherwise, the encoder obtains (710) the next vector of n symbols.

I. Implementation Example

Figure 8 shows a detailed technique (800) for encoding vectors using VDVH encoding in one implementation. In technique (800), the encoder sums the integer values ​​of the symbols into a vector of symbols to determine whether to encode the vector using a simple Huffman code, or to divide the vector into smaller vectors / scalars. This effectively limits the encryption and decryption code size, and speeds up code searching.

An encryption and decryption code table for n-dimensional vectors ["n-dim"] includes an escape code. The Li codes are for each vector for which the sum of the vector components (which are integers) is below a threshold T₁ particular. For example, suppose that n is 4 and the threshold T₁ for 4-dim vectors it is 6. The encryption and decryption code table for 4-dim vectors includes the escape code and 126 codes, one for each possible vector whose components (for example, the absolute values ​​of the components) add less than 6 - (0, 0, 0, 0), (0, 0, 0, 1), etc. Limiting the size of the table based on the sum of the components of the vectors is effective, in general, because the most probable vectors are those whose sums of components are smaller.

If the encryption and decryption code table for the n-dim vectors does not have a Huffman code for a particular n-dim vector, the encoder escapes the output bit stream and encodes the n-dim vector as smaller dimension vectors or scalars, looking for those smaller dimension vectors or scalars in other encryption and decryption code tables. For example, the smallest dimension is n / 2 unless n / 2 is 1, in which case the vector n-dim is divided into scalars. Alternatively, the n-dim vector is divided in some other way.

The encryption and decryption code table for smaller dimension vectors includes Huffman codes for L₂ smaller dimensional vectors, as well as an escape code. The L₂ codes are for each vector for which the sum of vector components is below a threshold T₂ particular for the smallest dimension table. For example, suppose that the smallest dimension is 2 and that the threshold T₂ for 2-dim vectors it is 16. The encryption and decryption code table for 2-dim vectors includes the escape code and 136 codes, one for each possible vector whose components (for example, the absolute values ​​of the components) add up to less of 16 - (0, 0), (0, 1), etc.

If the encryption and decryption code table for smaller-dimensional vectors does not have a Huffman code for a particular smaller-dimensional vector, the encoder escapes the output bit stream and encodes the vector as vectors or even smaller scales, using other encryption and decryption code tables. This process is repeated decreasing to a scalar level. For example, division is by a power of 2, descending to the scalar level. Alternatively, the vector is divided in some other way.

At the scalar level, the encryption and decryption code table includes Huffman codes for L₃ scalars as well as an escape code. The L₃ codes are for each scalar that is below a threshold T₃ (which assumes that small values ​​are the most probable). For example, suppose that the threshold T₃ for scalars it is 100. The encryption and decryption code table for scalars includes 100 codes and an escape code. If a scalar does not have an associated code in the scalar code table, the scalar is encoded with the escape code, and with a value (eg literal) according to a no-table technique. Using all the numerical examples given in this section, the tables would have to include a total of 126 + 1 + 136 + 1 + 100 + 1 = 365 codes.

The dimensional sizes for the tables, the vector division factors, and the thresholds for the sums of the vector components are implementation dependent. Other implementations use different vector sizes,

ES 2 297 083 T3 different division factors, and / or different thresholds. Alternatively, an encoder uses criteria other than vector component sums to switch vector sizes / code tables for encryption and decryption, in VDVH encoding.

Referring to Figure 8, the encoder first obtains an (810) n-dim vector. The n-dim vector comprises n symbols, each symbol having, for example, a value representing the quantized level for a frequency coefficient of audio data.

The encoder sums the vector components (812) and compares the sum to a threshold (820) for ndim vectors. If the sum is less than or equal to the threshold, the encoder encodes the n-dim vector with a Huffman code from a code table (822), and continues until encoding is complete (824). If the sum is greater than or equal to the threshold, the encoder sends an escape code (826) and divides the n-dim vector into two smaller vectors with dimensions of n / 2 (830).

The encoder gets the next n / 2-dim vector (840) and adds the components of the n / 2-dim vector (842). The encoder checks the sum against a threshold associated with n / 2-dim vectors (850). If the sum is less than or equal to the threshold, the encoder encodes the vector n / 2-dim with a Huffman code from a code table (852) for vectors n / 2-dim, and obtains the following vector n / 2-dim (840) if the encoder has not finished encoding the n / 2-dim (854) vectors. If the sum is greater than the threshold for n / 2-dim vectors, the encoder sends another escape code (856).

The encoder generally follows this pattern in vector processing, both to encode each vector and to divide the vector into smaller dimensional vectors. In cases where the encoder divides a vector into two scalar (1-dimensional) components (860), the encoder obtains the next scalar (870) and compares the value of the scalar with a threshold associated with scalar values ​​(880). If the scalar value is less than or equal to the threshold (880), the encoder encodes the scalar using a Huffman code from a code table (882) for scalars. If the scalar value is greater than the threshold, the encoder encodes the scalar using a syntax technique (884). The encoder then obtains the next scalar (870) if it has not finished processing the scalars (886).

Alternatively, the encoder uses tables with different dimensional sizes, divides vectors in some way other than a power of 2, and / or uses criteria other than the sum of vector components to switch vector sizes / cipher and decryption code tables, in VDVH encoding.

2. Adaptive Switching

Figure 9 shows a technique (900) for direct VDVH coding of signal level coefficients, where the encoder adaptively determines a switch point to switch to coding of sequence lengths and signal levels, in accordance with one implementation. The adaptive switch point depends on a count of consecutive zero-valued coefficients. The input data are signal levels for quantized transform coefficients, progressing from the lowest frequency coefficient to the highest frequency coefficient. Alternatively, the input data is of another form and / or organization than the audio data.

To begin with, the encoder initializes several variables. Specifically, the encoder sets a sequence count variable to 0 (910), sets a current vector variable to empty (912), and sets a variable dimension direct Huffman vector encoding state variable [“DVDVH”] ( 914).

The encoder receives the next QC coefficient as input (920). The encoder then checks (930) if the coefficient is zero. If the QC coefficient is not zero, the encoder resets to the sequence count (938) and adds the QC coefficient of the current vector (940). In another case (that is, if the QC coefficient is zero), the encoder increments the sequence count variable (932), and checks if the current sequence count exceeds the sequence count threshold (934). The sequence count threshold can be static or it can depend on a factor such as the size of a block of coefficients (eg, four zeros in an input sequence of 256 coefficients), or it can be adaptive in some other way. For example, the threshold can be increased or decreased, with or without relation to the number of coefficients in an input sequence. If the sequence count exceeds the threshold, the encoder changes the encoding state to sequence level encoding ["RLE"] (936), and the QC coefficient is added as a component to the current vector (940).

Adding the QC coefficient to the current vector increases the dimension of the vector. The encoder determines (950) whether the current vector is ready to encode by comparing the number of components in the current vector with the maximum dimension for the current vector. If so, the encoder encodes the current vector using DVDVH (960) encoding. If the current vector is smaller than the maximum dimension, but the QC coefficient is the last in a sequence, the encoder can fill in the current vector and encode it using DVDVH (960) encoding. The maximum dimension is implementation dependent. In one implementation, it is 8. However, the maximum dimension can be increased or decreased depending, for example, on the amount of resources available to create, store or transmit an encryption and decryption code.

ES 2 297 083 T3

After encoding the vector, the encoder checks the encoding status (970). If the encoding state is no longer DVDVH (for example, if the encoder has changed the encoding state to RLE as a result of exceeding the threshold number of zero coefficients), the encoder begins encoding the coefficients as lengths and levels of sequence (980). Sequence level coding can be carried out in a number of ways, including, for example, Huffman coding, Huffman vector coding, or context-based arithmetic coding. In some embodiments, sequence-level coding is carried out using Huffman coding with two Huffman code tables, where one table is used to encode data in which the shortest sequences are the most likely, and one table is used to encode data in which the longest sequences are the most likely. The encoder processes each table and chooses codes from one of the tables, indicating with a signal bit which of the tables is the one used by the encoder.

If the encoding state has not changed or the current vector is not ready to encode, the encoder determines (990) if there are more coefficients that need to be encoded. If so, the encoder enters the next coefficient (920) and continues the encoding process.

B. Variable-Dimension Huffman Vector Decoding

Figure 10 shows a VDVH decoding technique (1000) corresponding to the VDVH encoding technique (700) shown in Figure 7. For example, a decoder uses technique (1000) to decode signal levels directly encoded for frequency coefficients. of audio data. Alternatively, the decoder uses the technique to decode another form of audio data.

The decoder obtains (1010) the following Huffman code for an n-dimensional vector Huffman coding table. For example, the decoder gets the following Huffman code for 4 symbols in sequence.

The decoder checks (1020) if the Huffman code is the escape code for the n-dimensional Huffman vector coding table. If not, the decoder gets (1030) the n symbols represented by the Huffman code. For example, the decoder obtains the 4 symbols associated with the Huffman code in a 4-dimensional vector Huffman encryption and decryption code.

If the code is the escape code, the n-dimensional encryption and decryption code does not include a code for the vector, and the decoder obtains (1040) Huffman codes for smaller vectors and / or scalars. For example, the decoder obtains codes for x vectors of n / x symbols. For each vector of n / x symbols, the decoder recursively repeats the decoding technique, exiting when the vector or its component vectors / scalars are encoded.

The decoder then checks (1050) whether there are additional codes for the n-dimensional Huffman vector coding table that need to be decoded. If there aren't, the decoder exits. In another case, the decoder obtains (1010) the next such Huffman code.

I. Implementation Example

Figure 11 shows a detailed technique (1100) for decoding encoded vectors using VDVH encoding in one implementation. The decoding technique (1100) corresponds to the coding technique (800) shown in Figure 8.

Referring to Figure 11, the decoder obtains the following code for an n-dim vector Huffman code table (1110). The decoder checks if the code is the escape code for the n-dim vector Huffman code table (1120). If not, the decoder gets the n symbols represented by the code in the n-dim vector table (1122). The decoder continues until the decoder has finished processing the encoded data (1124).

If the code is the escape code for the n-dim vector Huffman code table, the decoder decodes the n-dim vector as two n / 2-dim vectors using a n / 2 vector Huffman code table. dim. Specifically, the decoder gets the following code for the n / 2-dim vector Huffman code table (1130). The decoder checks if the code is the escape code for the vector n / 2-dim Huffman code table (1140). If not, the decoder gets the n / 2 symbols represented by the code in the n / 2-dim vector Huffman code table (1142). The decoder continues to process the codes for the n / 2-dim vector Huffman code table until the processing of such codes is complete (1144).

If the code is the escape code for the n / 2-dim vector Huffman code table, the decoder decodes the n / 2-dim vector as two n / 4-dim vectors, which can be scalars, and so on.

The decoder generally follows this higher-dimensional vector decoding pattern as two smaller-dimensional vectors when escaping codes are detected, until the vectors to be decoded are scalar (1-dim vectors). At that point, the decoder gets the following code for a Huffman scalar table (1150). The decoder checks if the code is the escape code for the table of

ES 2 297 083 T3 Huffman scalar code (1160). If not, the decoder gets the scalar represented by the code in Huffman's scalar code table (1162). The decoder continues to process the codes for the scalars until the processing of those codes has been completed (1164). If the code is the escape code for the Huffman scalar code table, the scalar is encoded using a tableless technique, and the decoder gets the value (1170).

Alternatively, the decoder uses tables with different dimensional sizes and / or uses tables that divide the vectors in some way other than power of 2 in VDVH decoding.

2. Adaptive Switching

Figure 12 shows a technique (1200) for decoding vectors that have been encoded using VDVH encoding in accordance with one implementation, in which the decoder adaptively determines a switch point to switch to decoding of sequence lengths and signal levels. The adaptive switch point depends on a count of consecutive zero-value coefficients in the data, which are signal levels for quantized transform coefficients, progressing from the lowest frequency coefficient to the highest frequency coefficient. Alternatively, the data is another form and / or organization of audio data.

To begin with, the decoder initializes several variables. Specifically, the decoder sets a sequence count to 0 (1210) and sets a decoding state to DVDVH (1212).

The decoder decodes the next vector by looking up the code for that vector in a Huffman coding table 1220. For example, the decoder performs the decoding technique (1100) shown in Figure 11. The decoder then updates the sequence count based on the decoded vector 1230 (specifically, using the number of zero values ​​in the decoded vector to reset, increment, or otherwise adjust the sequence count).

The decoder checks if the sequence count exceeds a threshold (1240). The sequence count threshold can be static or it can depend on a factor such as the size of a block of coefficients (eg, four zeros in a 256 coefficient input sequence), or it can be adaptive in some other way. If the sequence count exceeds the threshold, the decoder begins decoding the encoded coefficients using sequence level decoding (1250). Sequence-level decoding can be accomplished in a number of ways, including, for example, Huffman decoding, Huffman vector decoding, or context-based arithmetic decoding.

In some embodiments, sequence level decoding is carried out using Huffman decoding with two potential Huffman code tables, where one table is used to decode data where shorter sequences are most likely, and one table is used to decode data in which longer sequences are more likely. When the decoder receives a code, a signal bit present in the code indicates which table the encoder used, and the decoder looks up the code in the appropriate table.

If the sequence count does not exceed the threshold, the decoder continues to process vectors until decoding is complete (1260).

V. Context-Based Arithmetic Encoding and Decoding

In some embodiments, an encoder such as encoder 200 of Figure 2 uses context-based arithmetic encoding ["CBA"] to encode audio data streams. In CBA coding, different probability distributions are associated with the input symbols, with different contexts. The probability distribution used to encode the input sequence changes when the context changes. Context can be calculated by measuring the different factors that are expected to affect the probability that a particular input symbol will appear in an input sequence. A decoder such as decoder 300 of Figure 3 performs the corresponding arithmetic decoding.

When encoding coefficients directly (that is, as direct levels), the encoder uses factors that include the values ​​of the previous coefficients in the sequence to calculate the context. When encoding coefficients using sequence-level encoding, the encoder uses factors that include the lengths of the current sequence and previous sequences, in addition to the values ​​of the previous coefficients, to calculate the context. The encoder uses a probability distribution associated with the computed context to determine the appropriate arithmetic code for the data. Thus, using the various factors in the calculation of the contexts, the encoder determines the contexts adaptively with respect to the data and with respect to the mode (ie, direct, sequence level) of representation of the data.

In alternative embodiments, the encoder may use additional factors, may omit some factors, or may use the factors mentioned above in other combinations.

ES 2 297 083 T3

A. Example of Context Implementation

Tables 2-5 and Figures 13A-13D, 14A-14H, and 15A-15H, show contexts and probability distributions, respectively, used in CBA encoding and decoding, according to an implementation example. Alternatively, CBA encoding and decoding use different contexts and / or different probability distributions.

Although the discussion that follows is focused on the context calculation in the encoder according to the implementation example, the decoder performs the corresponding context calculation during decoding using the previously encoded audio data.

As noted above, the encoder may encode coefficients using CBA encoding if the encoder is encoding direct levels only or sequence lengths and direct levels. In one implementation, however, the techniques for calculating contexts vary depending on whether the encoder is encoding direct levels only or sequence lengths and direct levels. Additionally, when encoding sequence lengths and direct levels, the encoder uses different contexts depending on whether the encoder is encoding a sequence length or direct level.

The encoder uses a fourth context system to compute contexts during direct level arithmetic encoding using casual context. The encoder calculates the context for a current L [n] level based on the value of the previous level (L [n-1]) and the level just before the previous level (L [n-2]). This context calculation is based on the assumption that: 1) if previous levels are low, the current level is likely to be low, and 2) the middle two levels are likely to be better predictors of the current level than other levels. Table 2 shows the contexts associated with the values ​​of the two previous levels in the fourth context system. Figures 13A-13D show the probability distribution for current levels for these contexts.

TABLE 2

Contexts for Direct Level CBA Encoding / Decoding

<td>L [n-1]</td><td>L [n-2]</td><td>Context</td>

<td> = 0</td><td> = 0</td><td> 0</td>

<td> = 0</td><td> &gt; 1</td><td> 1</td>

<td> = 1</td><td>Any</td><td> 2</td>

<td> &gt;2</td><td>Any</td><td> 3</td>

The probability distribution in Figures 13A-13D assumes that when the previous two levels are zero or near zero, the current level is more likely to be zero or near zero.

The encoder can also use CBA encoding when performing level sequence length encoding. When encoding a sequence length, the factors used by the encoder to calculate the context include the percentage of zeros in the input sequence (total execution over part of, or over all, the sequence) and the length of the previous sequence of zeros (R [n-1]). The encoder calculates a zero percent index based on the zero percent of the input sequence, as shown below in Table 3:

TABLE 3

Zero percent indexes for CBA encoding / decoding of sequence lengths

<img file="ES2297083T3_D0001.tif" />

The encoder uses the zero percent index along with the previous sequence length to calculate the context for encoding the current sequence length, as shown in Table 4 below. Figures 14A - 14H show probability distributions for different sequence length values ​​associated with these contexts.

ES 2 297 083 T3

TABLE 4

Contexts for CBA encoding / decoding of sequence lengths

<img file="ES2297083T3_D0002.tif" />

For example, in an input sequence where 91% of the levels are zero (resulting in a zero percent index of 0), and where the length of the previous zero sequence was 15, the context is 14. The probability distributions in Figures 14A-14H show that when the percentage of zeros in an input sequence is higher, the longer sequence lengths are more likely. The probability distributions also assume that within a given zero percentage index, sequence lengths that follow a zero sequence length are more likely to be shorter than sequence lengths that follow a greater sequence length. from zero.

When encoding a level in sequence level data, the factors used by the encoder to calculate the context include the length of the current sequence (R [n]), the length of the previous sequence (R [n-1]) , and the values ​​of the two previous levels (L [n-1]) and (L [n-2]). This context calculation is based on the observation that the current level depends on the previous two levels as long as the spacing (that is, the sequence lengths) between the levels is not too great. Also, if the previous levels are lower, and if the previous sequences are shorter, the current level is likely to be low. When the previous sequences are longer, the previous level has less effect on the current level.

The context associated with the values ​​of the current sequence length, the previous sequence length, and the two previous levels, is shown below in Table 5. Figures 15A - 15H show probability distributions for levels associated with these contexts. .

TABLE 5

Contexts for CBA level encoding / decoding in sequence level encoding

<td>R [n]</td><td>R [n-1]</td><td>L [n-1] .........</td><td>L [n-2]</td><td>Context</td>

<td> &gt;2</td><td>Any</td><td>Any</td><td>Any</td><td> 0</td>

<td> &lt;2</td><td> &gt;2</td><td> = 1</td><td>Any</td><td> 1</td>

<td> &lt;2</td><td> &gt;2</td><td> = 2</td><td>Any</td><td> 2</td>

<td> &lt;2</td><td> &gt;2</td><td> &gt;2</td><td>Any</td><td> 3</td>

<td> &lt;2</td><td> &lt;2</td><td> = 1</td><td> = 1</td><td> 4</td>

<td> &lt;2</td><td> &lt;2</td><td> = 1</td><td> &gt; 1</td><td> 5</td>

<td> &lt;2</td><td> &lt;2</td><td> = 1</td><td>Any</td><td> 6</td>

<td> &lt;2</td><td> &lt;2</td><td> &gt;2</td><td>Any</td><td> 7</td>

For example, in an input sequence in which the length of the current sequence of zeros is 1, the length of the previous sequence of zeros is 2, and the previous level is 1, the context is 1. The probability distributions of Figures 15A-15H show that when the previous levels are lower, and when the current and previous sequence lengths are shorter, the current level is more likely to be zero or near zero.

ES 2 297 083 T3

B. Adaptive Switching

Figure 16 shows a technique (1600) for direct CBA coding of signal level coefficients, in which the encoder adaptively determines a switch point to switch to coding of sequence lengths and signal levels in accordance with one implementation. . The adaptive switch point depends on the count of consecutive zero-valued coefficients. The input data are signal levels for quantized transform coefficients, progressing from the lowest frequency coefficient to the highest frequency coefficient.

To begin with, the encoder initializes various variables. Specifically, the encoder sets a sequence count variable to 0 (1610) and sets a context-based direct arithmetic (DCBA) encoding state variable (1612).

The encoder receives the following QC coefficient as input (1620). The encoder then checks (1630) if the coefficient is zero. If the coefficient is not zero, the encoder resets the sequence count (1638) and encodes the coefficient using DCBA encoding (1640).

In another case (that is, if the QC coefficient is zero), the encoder increments the sequence count variable (1632), and checks if the current sequence count exceeds the sequence count threshold (1634). The sequence count threshold can be static or it can depend on a factor such as the size of a block of coefficients (eg, four zeros in a 256 coefficient input sequence), or it can be adaptive in some other way. For example, the threshold can be increased or decreased, with or without relation to the number of coefficients in an input sequence. If the sequence count exceeds the threshold, the encoder changes the encoding state to sequence level encoding ["RLE"] (1636). The encoder then encodes the coefficient using DCBA (1640) encoding.

After encoding the coefficient, the encoder checks the encoding status (1650). If the encoding state is no longer DCBA (for example, if the encoder has changed the encoding state to RLE as a result of exceeding a threshold number of zero coefficients), the encoder begins encoding the coefficients as lengths and levels of sequence (1660). Sequence level coding can be performed in a number of ways including, for example, Huffman coding, Huffman vector coding, or CBA coding (potentially with different contexts than CBA coding, as described above). In some embodiments, sequence-level encoding is performed using Huffman encoding with two Huffman code tables, where one table is used to encode data in which shorter sequences are more likely, and one table is used to encode data in which longer sequences are more likely. The encoder processes each table, and chooses codes from one of the tables, with a signal bit indicating which table the encoder used.

If the encoding state has not changed, the encoder determines (1670) whether there are more coefficients to be encoded. If so, the encoder enters the next coefficient (1620) and continues the encoding process.

C. Context-based Arithmetic Decoding

Figure 17 shows a technique (1700) for decoding coefficients that have been encoded using CBA encoding in accordance with one implementation, in which the decoder adaptively determines a switch point to switch to decoding of sequence lengths and levels. signal. The adaptive switch point depends on a count of consecutive zero-valued coefficients in the data, which are signal levels for quantized transform coefficients, progressing from the lowest frequency coefficient to the highest frequency coefficient. Alternatively, the data is another form and / or organization of audio data.

To begin with, the decoder initializes several variables. Specifically, the decoder sets a sequence count to 0 (1710) and sets a context-based direct arithmetic (DCBA) decoding state (1712).

The decoder decodes the next quantized coefficient using DCBA (1720) by looking for the number that the encoder has used to represent the coefficient in arithmetic coding, and extracting the value of the coefficient from that number. The decoder then updates the sequence count based on the decoded coefficient (1730) (specifically, based on whether the decoded coefficient is a zero value to reset or increase the sequence count).

The decoder checks if the sequence count exceeds a threshold (1740). The sequence count threshold can be static or it can depend on a factor such as the size of a block of coefficients (eg, four zeros in a 256 coefficient input sequence), or it can be adaptive in some other way. If the sequence count exceeds the threshold, the decoder begins decoding the encoded coefficients using sequence level decoding (1750). Sequence-level decoding can be carried out in a number of ways, including, for example, Huffman decoding, Huffman vector decoding, or CBA decoding (potentially with different contexts than the above CBA decoding, as described above). above). In some embodiments, sequence level decoding is performed using sequence decoding.

ES 2 297 083 T3

Huffman with two potential tables of Huffman code, where one table is used to decode data in which shorter sequences are more likely, and a table is used to decode data in which longer sequences are more likely. When the decoder receives a code, a signal bit present in the code indicates which table has been used by the encoder, and the decoder looks up the code in an appropriate table.

If the sequence count does not exceed the threshold, the decoder continues to process coefficients until the decoding has finished (1760).

SAW. No-Table Coding

In some embodiments that use Huffman encoding, an encoder such as encoder 200 in Figure 2 uses an escape code for a Huffman code table to indicate that a particular symbol (or combination of symbols) does not have an associated code in the table. Sometimes an escape code is used to indicate that a particular symbol (for example, a scalar value for a level that is not represented in a scalar table of Huffman code for levels, a sequence length that is not represented in a Huffman code scalar table for sequence lengths, etc.), must be encoded without using any Huffman tables. In other words, the symbol must be encoded using a "tableless" encoding technique.

In some embodiments that use arithmetic encoding, an escape code is sometimes used to indicate that a particular symbol has not been arithmetically encoded. The symbol could be encoded using a code from a Huffman table, or it could be encoded using a "tableless" encoding technique.

Some tableless coding techniques use fixed-length codes to represent symbols. However, the use of fixed length codes can lead to unnecessarily long codes.

In some embodiments, therefore, symbols such as quantized transform coefficients are represented by variable length codes in a tableless encoding technique when the symbols are not otherwise encoded. A decoder such as decoder 300 of Figure 3 executes a corresponding tableless decoding technique.

For example, Table 6 shows a pseudo-code for an implementation of such a syntax coding technique.

TABLE 6

Pseudo-code for tableless coding technique in an implementation

If (value &lt;2⁸) {

Send "0";

Send value using 8 bits;

} or if (value &lt;2¹⁶) {

Send "10";

Send value using 16 bits}

or if (value &lt;2²⁴) {

Send "110";

Send value using 24 bits;

} or if (value &lt;2³¹) {

Send Ί11 ”;

Send value using 31 bits;

}

ES 2 297 083 T3

The number of bits that the encoder uses to encode the coefficient depends on the value of the coefficient. The encoder sends a one-, two-, or three-bit value to indicate the number of bits used to encode the value, and then sends the encoded value itself using 8, 16, 24, or 31 bits. The total number of bits that the encoder uses to encode the coefficient, is in the range of 9 bits for a value less than 2⁸, at 34 bits for a value greater than or equal to 2²⁴, but less than 2³¹.

For a series of coefficients, the average number of bits sent will be equal to:

P (0 &lt;C &lt;2⁸) * 9 + P (2⁸ &lt;C &lt;2¹⁶) * 18 + P (2¹⁶ &lt;C &lt;2²⁴) * 27 + P (2²⁴ &lt;C &lt;2³¹)*34.

where P (m &lt;C &lt;n) is the probability of occurrence, in an input sequence, of a coefficient C within the indicated range. Therefore, significant bit savings are possible when a large percentage of the coefficients are small (for example, less than 2¹⁶).

Alternatively, the encoder and decoder use another tableless encoding / decoding technique.

Having described and illustrated the principles of our invention with reference to the various described embodiments, it will be understood that the described embodiments can be modified in structure and detail without departing from such principles. It will be understood that the programs, processes, or procedures described herein are not related to or limited to any type of computing environment, unless otherwise indicated. Various types of general-purpose or specialized computing environments can be used with, or conducting, operations in accordance with the teachings described herein. The elements of the described embodiments shown in software can be implemented in hardware, and vice versa.

In view of the many possible embodiments to which the principles of our invention can be applied, we claim all such embodiments as our invention since they may fall within the scope of the claims that follow and their equivalents.