Entropy Coding Playground

Explore how different symbol distributions affect Shannon entropy, compare Huffman coding limits, and learn how entropy governs loss functions and vocabulary uncertainty in modern AI Large Language Models (LLMs).

Starting values — Entropy Coding Playground

Distribution parameter (λ)	1.5

Change any control above and the results recompute from these.

Loading interactive simulation...

Whole bits are what Huffman pays for 🖖

Entropy coding exploits statistical redundancy to represent messages using fewer bits. Shannon's Source Coding Theorem states that the absolute minimum average length of any lossless code is the Shannon entropy: H(X) = −Σ p_i log₂ p_i. Huffman coding is optimal for a given alphabet when symbols are coded individually, but it is constrained to integer-length codewords. This integer constraint means Huffman can deviate from the theoretical entropy by up to 0.086 bits/symbol (and much more if one symbol has p_i ≈ 1). Arithmetic coding (e.g. ANS) overcomes this limit by mapping the entire sequence to fractional intervals.

Connection to LLMs & AI: In modern Language Models (LLMs), entropy is a core concept during both training and generation. LLMs are trained by minimizing the Cross-Entropy Loss between their vocabulary predictions and the actual text. During generation (inference), the LLM outputs a probability distribution over its vocabulary for the next token. The entropy of this distribution measures the model's prediction uncertainty: a flat distribution (high entropy) yields creative or random text, while a peaked distribution (low entropy) yields highly predictable text. Sampling parameters like Temperature directly scale this entropy (lower temperature reduces entropy, higher temperature increases it), while nucleus sampling (Top-p) dynamically bounds cumulative probability to prune high-entropy tails.

Why rare symbols cost more bits 🖖

The real lesson of this tool: the ideal number of bits to encode a symbol is its surprise, −log₂ p. A symbol that appears half the time deserves 1 bit; one with probability 1 in 1000 deserves about 10 bits. Entropy is simply the average surprise across all symbols. That is why skewed distributions (like the Laplacian or exponential presets) compress well while a uniform alphabet cannot — when everything is equally likely, there is no redundancy to remove.

Morse code: entropy coding before Shannon 🖖

Morse code assigned the shortest signal, a single dot, to E, the most common English letter, and long sequences to rare ones like Q and Z. To pick the lengths, Alfred Vail reportedly counted the movable type in a printer's tray to estimate letter frequencies. This was working variable-length entropy coding in the 1840s — roughly a century before Shannon formalized in 1948 why it works.

ONE STAGE OF A CHAIN — WHAT ARRIVES, WHAT LEAVES, WHAT BREAKS DOWNSTREAM

Where This Sits In The Encoding Pipeline

A video encoder is not one algorithm but eight stages in a fixed order, and the order is not arbitrary: each stage exists because the one before it made its job possible. This tool models one of them. The chain below links to the other seven.

Entropy Coding Playground — packs the quantized symbols into as few bits as their statistics permit

What arrives: A stream of quantized integers, heavily skewed toward zero.
What leaves: The finished bitstream. Nothing is discarded here.
What the next stage assumes: Nothing downstream — this is the last coding stage. What it assumes is upstream: that the symbol distribution has already been made lopsided for it.
What goes wrong here: No entropy coder can beat the Shannon entropy of what it is handed, so its ceiling is set entirely by the earlier stages. Run it on unquantized coefficients and there is little redundancy to find, which is the reason the lossy step comes first rather than last.

Previous stage: Quantization Next stage: Rate control

Problem solved in full

The room left for a cleverer algorithm than Huffman on 16 symbols 6 steps
16 symbols, Laplacian distribution, entropy 3.010 bits. Huffman achieves 3.012. Work out how much room is left for a cleverer algorithm.
1. Entropy is the average surprise, in bits, of one symbol drawn from this distribution. It is a property of the probabilities alone and knows nothing about any code.
  
  $H (X) = - i = 1 \sum N p_{i} lo g_{2} p_{i} = 3.010 bits/symbol (N = 16, Laplacian, λ = 1.5)$
2. The naive alternative gives every symbol the same number of bits, and 16 symbols need 4. This is the baseline the saving is measured against.
  
  $L_{fixed} = ⌈ lo g_{2} N ⌉ = ⌈ lo g_{2} 16 ⌉ = 4.0 bits/symbol$
3. Huffman gives short codes to common symbols and long ones to rare ones, and the average is the probability-weighted length.
  
  $\overset{ˉ}{L} = \sum p_{i} L_{i} = 3.012 bits/symbol$
4. The saving compares the two code lengths, not the code with the entropy — which is why it is a claim about this alternative rather than about the limit.
  
  $savings = \frac{4.0 - 3.012}{4.0} = 24.7%$
5. Now compare against the limit. Shannon's source coding theorem says no prefix code can go below H, and Huffman is guaranteed to land under H + 1.
  
  $H \leq \overset{ˉ}{L} < H + 1 (Shannon); \overset{ˉ}{L} - H = 3.012 - 3.010 = 0.002 bits$
6. Express the remaining gap as a fraction and the optimisation question answers itself.
  
  $\frac{0.002}{3.010} = 0.07% above the floor$
Answer

0.002 bits per symbol, or 0.07%. Shannon's theorem brackets any prefix code between H and H + 1, and Huffman is proven optimal among them, so no prefix code will ever beat 3.012 on this text. The 24.7% saving over fixed-length coding is real, and the remaining 0.07% is the whole of what better engineering could ever add. Compression gains after this point by changing the model rather than the code: if neighbouring symbols correlate, the entropy of the conditional distribution is lower than 3.010, and that is a different number entirely.

$\overset{ˉ}{L} - H = 0.002 bits : Huffman is 0.07% off optimal here$

References (1)

Insight block 2 — entropy as average surprise, and the limit Huffman cannot beat: C. E. Shannon, "A Mathematical Theory of Communication." Bell System Technical Journal 27(3), 379–423, 1948.

By the 42Math team · Updated 2026-07-29

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

Uniform 8 - Uniform 8-symbol source: H=3 bits, zero coding gain — entropy equals fixed-length code
DCT-like Laplacian - DCT-like Laplacian: H≈2.1 bits, 23% savings — most video AC coefficients cluster near zero
Motion Vector-like - Motion vector-like exponential: H≈2.3 bits, 43% savings over 4-bit fixed code
Bimodal - Bimodal: two dominant symbols yield H≈2.5 bits, significant Huffman compression gain