Introduction

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.

Try It

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

<!-- Shannon Source Coding demo: shows entropy H and Huffman average code length L -->
<p class="hint">Drag the sliders to set symbol probabilities. The demo computes the Shannon entropy <b>H</b> and builds a Huffman code, showing its average length <b>L</b>. Notice that L is always ≥ H, and L &lt; H+1.</p>
<div id="controls"></div>
<div class="results" id="results">
  <div class="result-row">
    <span class="label">Shannon entropy H</span>
    <span class="value" id="val-entropy">—</span>
    <span class="unit">bits/symbol</span>
  </div>
  <div class="result-row">
    <span class="label">Huffman avg. length L</span>
    <span class="value" id="val-avglen">—</span>
    <span class="unit">bits/symbol</span>
  </div>
  <div class="result-row gap-row">
    <span class="label">Gap L − H</span>
    <span class="value" id="val-gap">—</span>
    <span class="unit">bits</span>
  </div>
</div>
<div class="codebook" id="codebook"></div>
<div class="btns">
  <button id="btn-equal" type="button">Equal probs</button>
  <button id="btn-skewed" type="button">Skewed probs</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* layout and color styles for the entropy/Huffman demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Huffman coding: builds the optimal prefix-free code for a given probability
// distribution. The average length L satisfies H <= L < H+1 (Shannon's theorem).

const SYMBOLS = ['A', 'B', 'C', 'D'];
// default probabilities: must sum to 1 (A=0.5, B=0.25, C=0.15, D=0.10)
let probs = [0.5, 0.25, 0.15, 0.1];

// entropy in bits: H(p) = -sum p_i * log2(p_i)
function entropy(ps) {
  return ps.reduce((h, p) => p > 0 ? h - p * Math.log2(p) : h, 0);
}

// build a Huffman tree and assign binary codewords
function buildHuffman(ps) {
  // start with leaf nodes, one per symbol
  const nodes = ps.map((p, i) => ({ p, sym: SYMBOLS[i], code: '' }));
  const heap = [...nodes];
  // merge the two lowest-probability nodes until one root remains
  while (heap.length > 1) {
    heap.sort((a, b) => a.p - b.p);
    const lo = heap.shift(), hi = heap.shift();
    for (const n of lo.sym ? [lo] : lo.leaves) n.code = '0' + n.code;
    for (const n of hi.sym ? [hi] : hi.leaves) n.code = '1' + n.code;
    heap.push({ p: lo.p + hi.p, leaves: [...(lo.sym ? [lo] : lo.leaves), ...(hi.sym ? [hi] : hi.leaves)] });
  }
  return nodes;
}

// average codeword length L = sum p_i * |code_i|
function avgLen(nodes) {
  return nodes.reduce((s, n) => s + n.p * n.code.length, 0);
}

function update() {
  // normalize so probabilities always sum to 1
  const total = probs.reduce((a, b) => a + b, 0);
  const ps = probs.map(p => p / total);

  const H = entropy(ps);
  const nodes = buildHuffman(ps);
  const L = avgLen(nodes);
  const gap = L - H;

  document.getElementById('val-entropy').textContent = H.toFixed(3);
  document.getElementById('val-avglen').textContent = L.toFixed(3);
  document.getElementById('val-gap').textContent = gap.toFixed(3);

  // show codeword for each symbol
  const cb = document.getElementById('codebook');
  cb.innerHTML = '';
  nodes.forEach((n, i) => {
    const el = document.createElement('div');
    el.className = 'code-entry';
    el.innerHTML = `<span class="code-sym">${SYMBOLS[i]}</span><span style="color:#888;font-size:.8rem">${(ps[i]*100).toFixed(1)}%</span><span class="code-bits">${n.code}</span>`;
    cb.appendChild(el);
  });

  // update displayed probabilities next to each slider
  document.querySelectorAll('.sym-prob').forEach((el, i) => {
    el.textContent = (ps[i] * 100).toFixed(1) + '%';
  });
}

function buildControls() {
  // create one slider row per symbol
  const div = document.getElementById('controls');
  div.innerHTML = '';
  SYMBOLS.forEach((sym, i) => {
    const row = document.createElement('div');
    row.className = 'sym-row';
    row.innerHTML = `<span class="sym-label">${sym}</span><input class="sym-slider" type="range" min="1" max="100" value="${Math.round(probs[i]*100)}"><span class="sym-prob"></span>`;
    div.appendChild(row);
    row.querySelector('input').addEventListener('input', e => {
      probs[i] = +e.target.value / 100;
      update();
    });
  });
  update();
}

document.getElementById('btn-equal').addEventListener('click', () => {
  // uniform distribution: H is maximized (= log2(4) = 2 bits)
  probs = [0.25, 0.25, 0.25, 0.25];
  document.querySelectorAll('.sym-slider').forEach((el, i) => el.value = 25);
  update();
});
document.getElementById('btn-skewed').addEventListener('click', () => {
  // skewed distribution: H drops, Huffman assigns short code to A
  probs = [0.7, 0.15, 0.1, 0.05];
  document.querySelectorAll('.sym-slider').forEach((el, i) => el.value = Math.round(probs[i]*100));
  update();
});
document.getElementById('btn-reset').addEventListener('click', () => {
  // restore default probabilities
  probs = [0.5, 0.25, 0.15, 0.1];
  document.querySelectorAll('.sym-slider').forEach((el, i) => el.value = Math.round(probs[i]*100));
  update();
});

buildControls();
Result
Console

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

The Real Complexity

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 rr, the average codeword length Lˉ\bar{L} satisfies

Lˉ  ≥  Hr(X)  =  −∑ipilog⁡rpi.\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⁡\log. Every compressor in the world, past or future, must obey this bound.

The direct part (achievability): for any ε>0\varepsilon > 0 and long enough block length nn, there exists a code with Lˉ≤H(X)+ε\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 2nH2^{nH} sequences, each needing about nHnH bits to name.

Huffman codes (1952, David Huffman) achieve H≤Lˉ<H+1H \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=3H = 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.

Where It Matters

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

Conclusion

Shannon source coding is one of the cleanest theorems in science: a hard lower bound that is also exactly achievable. Entropy H(X)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/shannon-source-coding/Content licensed under CC BY-NC 4.0.