Entropy encoding

An entropy encoding is a coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. Typically, entropy encoders are used to compress data by replacing symbols represented by equal-length codes with symbols represented by codes proportional to the negative logarithm of the probability. Therefore, the most common symbols use the shortest codes.

According to Shannon's source coding theorem, the optimal code length for a symbol is −log_bP, where b is the number of symbols used to make output codes and P is the probability of the input symbol.

Three of the most common entropy encoding techniques are Huffman coding, range encoding, and arithmetic coding. If the approximate entropy characteristics of a data stream are known in advance (especially for signal compression), a simpler static code such as unary coding, Elias gamma coding, Fibonacci coding, Golomb coding, or Rice coding may be useful.

See also

• Universal code
• Data compression
• Information theory

External links

• On-line textbook: Information Theory, Inference, and Learning Algorithms, by David MacKay - gives an accessible introduction to Shannon theory and data compression, including the Huffman algorithm and arithmetic coding.

An earlier (open content) version of the above article was posted on PlanetMath.