Variable to variable length entropy encoding

Details Variable to variable length entropy encoding Variable to variable length entropy encoding

1998-12-14

2002-04-23

Dorvil, Richemond (Department: 2641)

Data processing: speech signal processing, linguistics, language

Audio signal time compression or expansion

C704S504000, C341S063000

Reexamination Certificate

active

06377930

ABSTRACT:

FIELD OF THE INVENTION
The invention generally relates to data compression, and more specifically relates to a form of entropy coding.
BACKGROUND
In a typical audio coding environment, data is represented as a long sequence of symbols which is input to an encoder. The input data is encoded by an encoder, transmitted over a communication channel (or simply stored), and decoded by a decoder. During encoding, the input is pre-processed, sampled, converted, compressed or otherwise manipulated into a form for transmission or storage. After transmission or storage, the decoder attempts to reconstruct the original input.
Audio coding techniques can be generally categorized into two classes, namely the time-domain techniques and frequency-domain ones. Time-domain techniques, e.g., ADPCM, LPC, operate directly in the time domain while the frequency-domain techniques transform the audio signals into the frequency domain where the actual compression happens. The frequency-domain codecs can be further separated into either subband or transform coders although the distinction between the two is not always clear. Processing an audio signal in the frequency domain is motivated by both classical signal processing theories and human perception models (e.g., psychoaoustics). The inner ear, specifically the basilar membrane, behaves like a spectral analyzer and transforms the audio signal into spectral data before further neural processing proceeds.
The frequency-domain audio codecs often take advantage of many kinds of auditory masking that are going on with the human hear system to modify the original signal and eliminate a great many details/redundancies. Since the human ears are not capable of perceiving these modifications, efficient compression is achieved. Masking is usually conducted in conjunction with quantization so that quantization noise can be conveniently “masked.” In modern audio coding techniques, the quantized spectral data are usually further compressed by applying entropy coding, e.g., Huffman coding.
Compression is required because a fundamental limitation of the communication model is that transmission channels usually have limited capacity or bandwidth. Consequently, it is frequently necessary to reduce the information content of input data in order to allow it to be reliably transmitted, if at all, over the communication channel. Over time, tremendous effort has been invested in developing lossless and lossy compression techniques for reducing the size of data to transmit or store. One popular lossless technique is Huffman encoding, which is a particular form of entropy encoding.
Entropy coding assigns code words to different input sequences, and stores all input sequences in a code book. The complexity of entropy encoding depends on the number m of possible values an input sequence X may take. For small m, there are few possible input combinations, and therefore the code book for the messages can be very small (e.g., only a few bits are needed to unambiguously represent all possible input sequences). For digital applications, the code alphabet is most likely a series of binary digits {0, 1}, and code word lengths are measured in bits.
If it is known that input is composed of symbols having equal probability of occurring, an optimal encoding is to use equal length code words. But, it is not typical that an input stream has equal probability of receiving any particular message. In practice, certain messages are more likely than others, and entropy encoders take advantage of this to minimize the average length of code words among expected inputs. Traditionally, however, fixed length input sequences are assigned variable length codes (or conversely, variable length sequences are assigned fixed length codes).
SUMMARY
The invention concerns using a variable-to-variable entropy encoder to code an arbitrary input stream. A variable-to-variable entropy encoder codes variable length input sequences with variable length codes. To limit code book size, entropy-type codes may be assigned to only probable inputs, and alternate codes used to identify less probable sequences.
To optimize searching the code book, it may be organized into sections that are searched separately. For example, one arrangement is to group all stored input sequences in the book according to the first symbol of the input sequence. A hash encoding function, collection of pointers, or other method may be used to immediately jump to a given section of the code book. Each section may further be sorted according to the probability associated with the entry. For example, each section may be sorted with highest probable inputs located first in the section, thus increasing the likelihood that a match will be found quickly.
Matching code cook entries depends on the internal representation of the book. For example, in a tree structure, nodes may represent each character of the input such that reaching a leaf signifies the end and identification of a particular grouping of input symbols. In a table structure, a pattern matching algorithm can be applied to each table entry within the appropriate section. Depending on the implementation of the table and matching algorithms, searching may be facilitated by recognition that only as many input symbols as the longest grouping in the code book section need to be considered. After finding a code book match, the corresponding entropy-type code can be output and the search repeated with the next symbol following the matched input.
Although the illustrated embodiments focus on encoding audio data, the input stream is expected to be any data stream, such as numbers, characters, or a binary data which encodes audio, video or other types of data. For simplicity, the input stream is referenced herein as a series of symbols, where each “symbol” refers to the appropriate measurement unit for the particular input. The input stream may originate from local storage, or from intranets, the Internet, or streaming data (e.g., Microsoft's “NETSHOW”™ client/server streaming architecture).


REFERENCES:
patent: 4122440 (1978-10-01), Langdon, Jr. et al.
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4558302 (1985-12-01), Welch
patent: 4706265 (1987-11-01), Furukawa
patent: 4744085 (1988-05-01), Fukatsu
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5227788 (1993-07-01), Johnston et al.
patent: 5229768 (1993-07-01), Thomas
patent: 5254990 (1993-10-01), Yoshida
patent: 5406279 (1995-04-01), Anderson et al.
patent: 5442350 (1995-08-01), Iyer et al.
patent: 5479562 (1995-12-01), Fielder et al.
patent: 5530866 (1996-06-01), Koblenz et al.
patent: 5532694 (1996-07-01), Mayers et al.
patent: 5534861 (1996-07-01), Chang et al.
patent: 5550541 (1996-08-01), Todd
patent: 5579430 (1996-11-01), Grill et al.
patent: 5623262 (1997-04-01), Normile et al.
patent: 5644305 (1997-07-01), Inoue et al.
patent: 5790706 (1998-08-01), Auyeung
patent: 5819215 (1998-10-01), Dobson et al.
patent: 5825830 (1998-10-01), Kopf
patent: 5831559 (1998-11-01), Agarwal et al.
patent: 5845243 (1998-12-01), Smart et al.
patent: 5872530 (1999-02-01), Domyo et al.
patent: 5883589 (1999-03-01), Takashima et al.
patent: 5884269 (1999-03-01), Cellier et al.
patent: 5907637 (1999-05-01), Murashita
patent: 5933104 (1999-08-01), Kimura
patent: 5959560 (1999-09-01), Said et al.
patent: 5995118 (1999-11-01), Masuda
patent: 6029126 (2000-02-01), Malvar
patent: 6047298 (2000-04-01), Morishita
patent: 6052150 (2000-04-01), Kikuchi
patent: 6100824 (2000-08-01), MacLeod et al.
patent: 6223162 (2001-04-01), Chen et al.
patent: 6300888 (2001-10-01), Chen et al.
patent: 0283735 (1988-09-01), None
patent: 0462363 (1991-12-01), None
patent: 0535571 (1993-04-01), None
patent: 0612156 (1994-04-01), None
patent: 62247626 (1987-10-01), None
patent: 09232968 (1997-09-01), None
patent: WO 98/40969 (1998-09-01), None
Bell et al., Text Compression, “Contents,” “Preface,” “Chapter 8: Dictionary Techniques,” “Chapter 9: Dictionary Versus Statistical Coding,”to “References, ” Prentice Hall Advance Reference Series, pp. v-xi, xiii-xviii, 20

Affiliated with

Also associated with

Rating

Variable to variable length entropy encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variable to variable length entropy encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable to variable length entropy encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2844853