What Is Entropy Coding?

Entropy coding is a class of lossless data compression techniques that reduce the average bit length required to represent a sequence of symbols by assigning shorter codes to more frequent symbols and longer codes to rarer ones. The method draws directly from Claude Shannon's 1948 source coding theorem, which proves that no lossless code can compress data below the source's Shannon entropy: H = -∑ p_i log₂ p_i bits per symbol. Entropy coders aim to close the gap between a code's average length and this theoretical minimum. Because they introduce no distortion, they are used either alone for lossless file formats or as a final stage after lossy transform coding in image, audio, and video compression pipelines.

Entropy coding sits within the broader discipline of data compression, which encompasses both lossless and lossy schemes. Its inputs are symbol sequences that often exhibit non-uniform statistical distributions; the coder exploits those distributions to achieve compactness. Accurate probability modeling of the source symbols is therefore as important as the coding algorithm itself, and much practical work focuses on building adaptive models that track symbol statistics across the data stream.

Huffman Coding

Huffman coding, introduced by David Huffman in 1952, builds a binary tree in which each leaf represents a source symbol and the path length from root to leaf determines the code word length. Symbols with higher probabilities receive shorter paths. The resulting code is prefix-free, meaning no code word is a prefix of another, which allows unambiguous decoding without separators. Huffman codes achieve the entropy lower bound when all symbol probabilities are exact powers of one-half; in practice, the average code length is within one bit per symbol of the entropy. Canonical Huffman codes, where code words are assigned in a sorted order, simplify table storage and are the form used in deflate compression, the format underlying ZIP and PNG files.

Arithmetic Coding

Arithmetic coding compresses a sequence by mapping the entire message to a single rational number in the interval [0, 1). The interval is progressively subdivided according to symbol probabilities, and the final sub-interval identifies the message. Unlike Huffman coding, arithmetic coding is not constrained to assign an integer number of bits per symbol, allowing it to approach the entropy limit arbitrarily closely for any probability distribution. Evaluation of Huffman and arithmetic coding algorithms for multimedia compression demonstrates that arithmetic coding achieves better compression ratios than Huffman coding at the cost of higher computational complexity. Arithmetic coding is the backend used in the context-adaptive binary arithmetic coder (CABAC) employed by the H.264 and H.265 video standards.

Asymmetric Numeral Systems

Asymmetric numeral systems (ANS) are a family of entropy coding algorithms introduced by Jarosław Duda in 2013 that combine the near-entropy-limit compression of arithmetic coding with decoding speeds approaching those of Huffman coding. The ANS paper on arxiv.org shows how the technique uses integer state machines rather than interval arithmetic, enabling efficient SIMD and GPU implementations. ANS variants, particularly rANS (range ANS) and tANS (table ANS), are now used in Zstandard compression, Apple's LZFSE format, and several modern video codecs. IEEE conference work on ANS as a replacement for Huffman coding provides further analysis of accuracy and throughput trade-offs.

Applications

Entropy coding has applications in a wide range of fields, including:

• Lossless image compression (PNG, JPEG-LS, WebP lossless mode)
• Video compression (CABAC in H.264/H.265, entropy stages in AV1)
• Lossless audio coding (FLAC, Apple Lossless)
• General-purpose file archiving (Zstandard, Brotli, deflate/ZIP)
• Medical imaging, where lossless fidelity is a regulatory requirement
• Network packet compression and database column storage