Adaptive coding: Difference between revisions

Revision as of 18:24, 29 January 2004

Revision as of 06:29, 24 September 2004

Line 1:

'''Adaptive coding''' is a technique that is frequently used to increase the efficiency of various [[entropy encoding]] methods, by reducing the overhead that the encoder needs to send to the decoder to start the process, and by more accurately reflecting localized changes in the characteristics of the data. It also results in some methods that ordinarily require two passes over the data (such as [[Huffman coding]]) being able to complete its job with just one pass over the data. The cost paid for these advantages is that the encoder and decoder must be more complex to keep their states synchronized, and more computational power is needed to keep adapting the encoder/decoder state.

The recently developed technique of [[arithmetic coding]], in conjunction with a [[Markov model]] of the source, is a powerful method of [[data compression]] in situations where a linear treatment is inappropriate. Adaptive coding allows the model to be constructed dynamically by both encoder and decoder during the course of the transmission, and has been shown to incur a smaller coding overhead than explicit transmission of the model's statistics.

Almost all [[data compression]] methods involve the use of a ''model'', a prediction of the composition of the data. When the data matches the prediction made by the model, the encoder can usually transmit the content of the data at a lower information cost, by making reference to the model. While sometimes the model is implicit in the compression method (for instance, in [[run-length encoding]]), in most methods it is separate, and because both the encoder and the decoder need to use the model, it must be transmitted with the data.

In adaptive coding, the encoder and decoder are instead equipped with identical rules about how they will alter their models in response to the actual content of the data, and otherwise start with a blank slate, meaning that no initial model needs to be transmitted. As the data is transmitted, both encoder and decoder adapt their models, so that unless the character of the data changes radically, the model becomes better-adapted to the data it's handling and compresses it more efficiently.