Shannon Source Coding

Every time you zip a file, stream a video, or send a text, something invisible is happening: a code is turning symbols into bits. The question engineers have always asked is — how short can those bits get?

In 1948, Claude Shannon gave the definitive answer. He defined entropy — a single number that measures the average unpredictability of a source — and proved that no lossless code can, on average, squeeze a message below that number of bits per symbol. Try harder, be cleverer, use any trick you like: entropy is the floor.

The theorem does not tell you which code is best; it tells you when you have reached the absolute limit. And it turns out that simple, elegant codes like Huffman coding get arbitrarily close to that limit — within one bit per symbol at worst.

Adjust the probability sliders to shape a 4-symbol source. The demo computes the Shannon entropy $H$ and the Huffman code for your distribution, then shows the average code length $\bar{L}$ alongside $H$.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="controls"></div>
<div class="results" id="results">
  <div class="result-row">
    <span class="label">{{label_entropy}}</span>
    <span class="value" id="val-entropy">—</span>
    <span class="unit">{{unit_bps}}</span>
  </div>
  <div class="result-row">
    <span class="label">{{label_avg_len}}</span>
    <span class="value" id="val-avglen">—</span>
    <span class="unit">{{unit_bps}}</span>
  </div>
  <div class="result-row gap-row">
    <span class="label">{{label_gap}}</span>
    <span class="value" id="val-gap">—</span>
    <span class="unit">{{unit_bits}}</span>
  </div>
</div>
<div class="codebook" id="codebook"></div>
<div class="btns">
  <button id="btn-equal" type="button">{{btn_equal}}</button>
  <button id="btn-skewed" type="button">{{btn_skewed}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_style}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
#controls { display: flex; flex-direction: column; gap: .45rem; margin-bottom: .9rem; }
.sym-row { display: flex; align-items: center; gap: .55rem; }
.sym-label { font-weight: 700; font-size: .95rem; width: 22px; text-align: center; }
.sym-slider { flex: 1; accent-color: #1d3557; }
.sym-prob { width: 44px; text-align: right; font-variant-numeric: tabular-nums; color: #555; font-size: .88rem; }
.results { display: flex; flex-direction: column; gap: .2rem; background: #eef2f6; border-radius: 8px; padding: .65rem .9rem; margin-bottom: .8rem; }
.result-row { display: flex; align-items: baseline; gap: .4rem; }
.result-row.gap-row { margin-top: .25rem; border-top: 1px solid #cdd9e3; padding-top: .25rem; }
.label { color: #555; flex: 1; }
.value { font-weight: 700; font-variant-numeric: tabular-nums; font-size: 1.05rem; color: #1d3557; }
.unit { color: #888; font-size: .8rem; }
.codebook { display: flex; flex-wrap: wrap; gap: .4rem .8rem; margin-bottom: .8rem; }
.code-entry { display: flex; align-items: center; gap: .3rem; font-size: .88rem; }
.code-sym { font-weight: 700; color: #1d3557; }
.code-bits { font-family: ui-monospace, monospace; background: #dde4ec; border-radius: 4px; padding: 1px 5px; font-size: .82rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

No matter how you move the sliders, the Huffman average length stays between $H$ and $H + 1$ bits per symbol — never below $H$. Shannon's theorem guarantees the gap cannot be closed by any lossless scheme; Huffman coding closes it to within one bit.

Shannon's source coding theorem has two halves, and together they form one of the sharpest results in all of science.

The converse (lower bound): for any uniquely decodable lossless code over an alphabet of size $r$, the average codeword length $\bar{L}$ satisfies

$$\bar{L} \;\ge\; H_r(X) \;=\; -\sum_{i} p_i \log_r p_i.$$

No exceptions. The proof is a few lines of Jensen's inequality applied to the concavity of $\log$. Every compressor in the world, past or future, must obey this bound.

The direct part (achievability): for any $\varepsilon > 0$ and long enough block length $n$, there exists a code with $\bar{L} \le H(X) + \varepsilon$. In other words, entropy is not just a lower bound — it is an achievable limit. Shannon's 1948 paper proved this. The proof uses the asymptotic equipartition property: almost all long strings concentrate their probability into a "typical set" of roughly $2^{nH}$ sequences, each needing about $nH$ bits to name.

Huffman codes (1952, David Huffman) achieve $H \le \bar{L} < H + 1$ for a single symbol at a time — within one bit of the theoretical floor, no block coding needed. Arithmetic coding and asymmetric numeral systems (ANS, Jarek Duda, 2009) push the gap to near zero in practice.

The key insight: randomness cannot be compressed away. If a source has $H = 3$ bits per symbol, you cannot describe what it outputs in fewer than 3 bits per symbol on average — because those 3 bits are genuinely new information each time. Compare this with Kolmogorov complexity, which asks the same question about individual strings rather than distributions.

Shannon's theorem is not an abstraction. It is the foundation every compression engineer stands on:

• File compression (ZIP, gzip, zstd): deflate and its successors use Huffman or arithmetic coding on the output of an LZ77 dictionary stage. The entropy bound governs how tight the final bit stream can get.
• Image and video (JPEG, PNG, H.265): after prediction and transform, the residuals are entropy-coded. The quality-vs-size tradeoff lives entirely in how close the coder gets to $H$.
• Audio (MP3, AAC, FLAC): FLAC is lossless; every byte it saves comes from exploiting the source's low entropy. Lossy codecs like MP3 first remove perceptually irrelevant information, then entropy-code what remains.
• DNA sequencing: genomes have low entropy (bases are correlated) — specialized compressors such as CRAM exploit this to cut storage costs dramatically.
• Machine learning compression: modern large model weights are increasingly entropy-coded for deployment; the theoretical bound sets the ceiling for how small they can get.

Whenever a file format claims a new compression record, the fine print always compares to the entropy of the test corpus. Shannon drew that target in 1948, and every compressor since has been an attempt to hit it.

Shannon source coding is one of the cleanest theorems in science: a hard lower bound that is also exactly achievable. Entropy $H(X)$ measures the average surprise in a source, and no lossless scheme can compress below it — not by a fraction of a bit, not on average, not ever.

What makes the theorem powerful is its universality. It does not care whether you are compressing text, images, audio, DNA, or neural network weights. The bound is the bound. Every modern compressor — Huffman, arithmetic, ANS, LZMA — is an engineering attempt to close the gap to zero.

The next time a progress bar tells you a file shrank from 10 MB to 4 MB, you are witnessing Shannon's theorem in action: the compressor found and removed the redundancy, and stopped exactly where the entropy said it must. To learn how information limits relate to computation itself, see Kolmogorov complexity.