Entropy coding

In <a href="/facts/Information_theory/qNLH3U5P">information theory</a>, an entropy coding (or entropy encoding) is any <a href="/facts/Lossless_compression/LS702KsN">lossless data compression</a> method that attempts to approach the lower bound declared by <a href="/facts/Claude_Shannon/EremsCws">Shannon's</a> <a href="/facts/Source_coding_theorem/MHSHNrcI">source coding theorem</a>, which states that any lossless data compression method must have an expected code length greater than or equal to the entropy of the source.
More precisely, the source coding theorem states that for any source distribution, the expected code length satisfies 
 
 
 
 
 E
 
 x
 ∼
 P
 
 
 ⁡
 [
 ℓ
 (
 d
 (
 x
 )
 )
 ]
 ≥
 
 E
 
 x
 ∼
 P
 
 
 ⁡
 [
 −
 
 log
 
 b
 
 
 ⁡
 (
 P
 (
 x
 )
 )
 ]
 
 
 {\displaystyle \operatorname {E} _{x\sim P}[\ell (d(x))]\geq \operatorname {E} _{x\sim P}[-\log _{b}(P(x))]}
 
, where 
 
 
 
 ℓ
 
 
 {\displaystyle \ell }
 
 is the function specifying the number of symbols in a code word, 
 
 
 
 d
 
 
 {\displaystyle d}
 
 is the coding function, 
 
 
 
 b
 
 
 {\displaystyle b}
 
 is the number of symbols used to make output codes and 
 
 
 
 P
 
 
 {\displaystyle P}
 
 is the probability of the source symbol. An entropy coding attempts to approach this lower bound.
Two of the most common entropy coding techniques are <a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a> and <a href="/facts/Arithmetic_coding/WU0H4oNu">arithmetic coding</a>.
If the approximate entropy characteristics of a data stream are known in advance (especially for <a href="/facts/Signal_compression/7L7tzhTt">signal compression</a>), a simpler static code may be useful.
These static codes include <a href="/facts/Universal_code_(data_compression)/9zn1cM2M">universal codes</a> (such as <a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma coding</a> or <a href="/facts/Fibonacci_coding/GXCLAf7t">Fibonacci coding</a>) and <a href="/facts/Golomb_coding/bUyW4uLN">Golomb codes</a> (such as <a href="/facts/Unary_coding/yHF7r7pE">unary coding</a> or <a href="/facts/Rice_coding/bUyW4uLN">Rice coding</a>).
Since 2014, data compressors have started using the <a href="/facts/Asymmetric_numeral_systems/1tBzSkxj">asymmetric numeral systems</a> family of entropy coding techniques, which allows combination of the compression ratio of <a href="/facts/Arithmetic_coding/WU0H4oNu">arithmetic coding</a> with a processing cost similar to <a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a>.

Entropy coding open-in-new

Entropy coding