Entropy Coding Playground

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) = -\sum p_i \log_2 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 \approx 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.

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 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.