Entropy Coding: Huffman & Arithmetic

Entropy coding is the reversible last step of lossless compression. A model assigns probabilities to symbols or contexts; a coder converts those probabilities into bits. Huffman coding gives each symbol an integer-length prefix codeword, while arithmetic coding represents a whole sequence as a subinterval whose width is its modeled probability.

Neither method discovers structure by itself. If a compressor predicts pixels, tokens, or match lengths well, the entropy coder records those predictions efficiently. If the model says every byte is equally likely, no clever bit writer can manufacture compression. This model/coder boundary is the most important design fact in the subject.

Probability is a bit budget #

For an event with probability $p$, its self-information is

$$I(p)=-\log_2 p.$$

Halving the probability adds one bit because identifying one outcome among twice as many equally plausible alternatives requires one more binary decision. For a discrete source $X$ with probabilities $p_i$, the mean ideal information is Shannon entropy

$$H(X)=-\sum_i p_i\log_2p_i.$$

This is a lower bound on the expected length of any uniquely decodable binary code for that source model. It is not a promise that one observed file will compress to exactly $NH$ bits: headers, model description, termination, finite precision, block boundaries, and model mismatch all cost bits, while a particular sample can be more or less surprising than the mean.

Prefix codes and the Kraft condition #

A code is prefix-free when no codeword is the prefix of another. A decoder can then walk a binary tree until it reaches a leaf, emit that symbol, and restart at the root without separators.

For binary codeword lengths $\ell_i$, a prefix code exists exactly when the Kraft inequality holds:

$$\sum_i2^{-\ell_i}\le1.$$

Each length-$\ell$ word occupies a fraction $2^{-\ell}$ of the infinite binary tree below the root. Prefix-free leaves cannot overlap, so their fractions must fit within one tree. Equality means the code is complete: no additional leaf can be added without violating the prefix property.

Huffman greedily merges the least probable symbols #

Huffman's algorithm repeatedly combines the two smallest weights into a parent whose weight is their sum. Reversing those merges creates a binary tree; every left/right edge adds one bit to the descendants. The greedy step is optimal because two least-probable symbols can be placed as deepest siblings in some optimal tree, reduced to one combined symbol, and solved recursively.

For probabilities

merge D+C → 0.30, then merge that node with B → 0.60, then merge with A → 1.00.

flowchart TD
  R[1.00] -->|0| A[A · 0.40]
  R -->|1| X[0.60]
  X -->|0| B[B · 0.30]
  X -->|1| Y[0.30]
  Y -->|0| C[C · 0.20]
  Y -->|1| D[D · 0.10]

One resulting code is:

The source entropy is

$$H\approx1.846\ \text{bit/symbol},$$

so the integer-length penalty here is about $0.054$ bit/symbol. For a binary Huffman code on individual source symbols,

$$H\le L<H+1.$$

The gap can approach one bit when one symbol is extremely likely, because a nonempty prefix code still spends at least one whole bit per occurrence. Blocking several symbols together reduces that rounding penalty per original symbol, but grows the alphabet and table.

Canonical Huffman stores lengths, not a tree #

Many different bit assignments have the same optimal lengths. A canonical code makes the assignment deterministic:

1. sort symbols by code length, then by a declared symbol order;
2. give the first symbol the all-zero code of its length;
3. increment the previous code as an integer;
4. when the length increases, left-shift by the difference.

For lengths A:1, B:2, C:3, D:3, the canonical codes are exactly 0, 10, 110, 111. The bitstream need only transmit the length sequence—or a compressed representation of it—because the decoder reconstructs the same codes.

RFC 1951 uses this idea for DEFLATE. It transmits literal/length and distance code lengths in a specified order and even Huffman-codes the length sequence itself. The format also specifies least-significant-bit handling for packed fields, while Huffman codes are packed in the opposite logical order. This is why a mathematically correct tree is not sufficient for bit-compatible output.

Arithmetic coding spends fractional bits across symbols #

Huffman rounds each symbol to a whole number of bits. Arithmetic coding avoids per-symbol rounding by narrowing one interval for the entire sequence. Partition $[0,1)$ according to cumulative probabilities. For

$$P(A)=0.5,\qquad P(B)=0.3,\qquad P(C)=0.2,$$

use subranges A:[0,0.5), B:[0.5,0.8), C:[0.8,1).

Encode sequence BAC:

1. start with $[0,1)$;
2. B selects $[0.5,0.8)$;
3. within that range, A selects $[0.5,0.65)$;
4. within that range, C selects $[0.62,0.65)$.

Any number in the final interval identifies the sequence when the decoder knows the same model and stopping rule. For example $0.625=0.101_2$ lies in $[0.62,0.65)$. The interval width is

$$0.3\cdot0.5\cdot0.2=0.03,$$

and the ideal description length is

$$-\log_2(0.03)\approx5.06\ \text{bits}.$$

Arithmetic coding therefore approaches the information of the whole sequence rather than rounding each symbol separately. It does not literally transmit an infinite-precision fraction; a real encoder emits bits whenever all numbers in the current interval share a prefix.

Integer range updates must match exactly #

An implementation maintains integer bounds and cumulative counts. With inclusive bounds low..high, total model count $T$, and symbol cumulative counts $C_{lo},C_{hi}$, one common update is

$$R=high-low+1,$$

$$high'=low+\left\lfloor\frac{R C_{hi}}{T}\right\rfloor-1, \qquad low'=low+\left\lfloor\frac{R C_{lo}}{T}\right\rfloor.$$

Encoder and decoder must use the same inclusive/exclusive convention and rounding. They then renormalize:

• if the interval lies wholly in the lower or upper half, emit/remove that common leading bit;
• if it lies in the middle two quarters, defer an underflow bit and rescale the middle interval;
• rescale adaptive counts before their total becomes too large for the register precision.

The middle-half case is the subtle one: the leading bits differ now but are forced to become complements once the interval eventually leaves the middle. Witten, Neal, and Cleary describe this as delayed coding; omitting it can stall interval growth or lose precision.

Termination and framing are part of the code #

The decoder needs to know when to stop. Common contracts are:

• an explicit uncompressed symbol count in a block header;
• an end-of-stream symbol that participates in the model;
• a container-supplied compressed length plus a format-specific flush rule.

Choosing any value in the final arithmetic interval is not enough unless the emitted prefix distinguishes that interval from every alternative continuation allowed by the stopping rule. Likewise, a Huffman decoder that reaches the end in the middle of a codeword must report truncation rather than invent padding.

Entropy-coded streams are fragile under corruption. A wrong Huffman bit may resynchronize at a later leaf but silently change several symbols. Arithmetic coding usually loses model synchronization and corrupts the remainder of the block. Formats therefore bound damage with blocks, restart points, lengths, checksums, or independently decodable chunks.

Model quality dominates coder choice #

The comparison must hold the model constant. A range coder paired with a poor order-0 model can lose to Huffman paired with a strong LZ or contextual model. The coder only realizes the probabilities it is given.

Compression sits before channel protection #

Channel coding adds structured redundancy so a noisy link can detect or repair errors; entropy coding removes statistical redundancy so fewer bits need transmission. The normal order is

flowchart LR
  S[source symbols] --> M[predict or model]
  M --> E[entropy encode]
  E --> F[frame and checksum]
  F --> C[channel encode]
  C --> CH[physical channel]
  CH --> D[channel decode]
  D --> V[verify frame]
  V --> X[entropy decode]

Trying to compress after encryption or effective channel coding usually fails because both deliberately make output look statistically uniform. Applying FEC after compression is also safer: the compressed stream is highly sensitive to a bit error, so it needs protection and an integrity check around it.

Verification checklist #

1. Verify a hand-built Huffman tree, its lengths, canonical assignment, and Kraft sum independently.
2. Test empty input, one-symbol alphabets, all symbols equal, maximum allowed length, and tied frequencies with a fixed tie rule.
3. Compare encoded bit count with $-\log_2P(sequence)$ plus declared headers and flush overhead.
4. For arithmetic coding, trace low, high, cumulative counts, emitted bits, and underflow count for a published short vector.
5. Run encoder output through an independent decoder, then the independent encoder's output through your decoder.
6. Flip, delete, and truncate bits; require a bounded failure or checksum error rather than silent acceptance.
7. Fuzz model counts near rescaling and integer-range boundaries with overflow checking enabled.

Entropy coding is successful only when three things are reproducible: the probability model, the exact code construction and bit order, and the termination/container contract. Compression ratio alone cannot prove any of them.