Information & Coding Theory

Advanced Topics » Information & Coding Theory

In 1948 Claude Shannon asked two questions that look unrelated and answered them with the same currency — the bit. How far can a source be compressed without losing information? And how fast can information be pushed through a noisy channel while keeping the error probability arbitrarily small? The astonishing answer is that both limits are sharp, both are computed from the same logarithmic quantity, and — crucially — the two problems separate: you can compress optimally first and protect against noise second, losing nothing by treating them independently.

• Entropy is the only sensible measure. Demanding continuity, monotonicity, and a grouping (chain) rule forces the measure of uncertainty to be Shannon entropy up to the choice of logarithm base.
• Compression has a floor. No uniquely decodable code beats the source entropy on average; Huffman and arithmetic coding get within one bit and one symbol of it respectively.
• Capacity is a phase transition. Below capacity, error probability can be driven to zero; above it, error is bounded away from zero. There is no graceful middle ground in the asymptotic limit.
• Random codes are optimal. Shannon proved capacity is achievable by averaging over random codebooks — but the constructive race to build explicit, efficiently decodable capacity-achieving codes took another fifty years (LDPC, turbo, polar).

The Logical Spine

The results below form a dependency chain, not a list. Entropy and its conditional/joint variants are defined axiomatically; mutual information is the unique quantity that drops out as “shared uncertainty”; the Asymptotic Equipartition Property (AEP) turns these averages into hard combinatorial facts about typical sequences; and the two coding theorems — source coding and channel coding — are both proved by counting typical sequences.

flowchart TD
    AX["Axioms: continuity, grouping"] --> H["Shannon entropy H(X)"]
    H --> JC["Joint / conditional entropy"]
    JC --> MI["Mutual information I(X;Y)"]
    H --> AEP["Asymptotic Equipartition Property"]
    AEP --> SCT["Source Coding Theorem<br/>(compression limit = H)"]
    MI --> CC["Channel capacity C = max I(X;Y)"]
    AEP --> NCT["Noisy-Channel Coding Theorem<br/>(reliable rate &lt; C)"]
    CC --> NCT
    SCT --> SEP["Source–channel separation"]
    NCT --> SEP

Table of Contents

• Entropy and Information Measures
• Mutual Information and Relative Entropy
• The Asymptotic Equipartition Property
• Source Coding (Compression)
• Channel Capacity and the Noisy-Channel Theorem
• Error-Correcting Codes
• Rate–Distortion Theory
• Quantum Information Measures

Entropy and Information Measures

Shannon Entropy

Intuition: The entropy of a random variable is the average number of bits needed to describe its outcome — equivalently, the average “surprise” of an observation, where the surprise of an event of probability $p$ is $\log(1/p)$. Rare events carry more information.

Entropy is not an arbitrary choice. Shannon’s axiomatic theorem shows that any measure $H(p_1,\dots,p_n)$ that is (i) continuous in the probabilities, (ii) monotonically increasing in $n$ for the uniform distribution, and (iii) satisfies the grouping/chain rule must equal $-K\sum_i p_i \log p_i$ for some positive constant $K$ — the base of the logarithm being the only freedom.

Joint, Conditional, and the Chain Rule

For a pair $(X,Y)\sim p(x,y)$ the joint entropy is $H(X,Y) = -\sum_{x,y} p(x,y)\log_2 p(x,y)$, and the conditional entropy — the residual uncertainty in $Y$ once $X$ is known — is

These obey the chain rule, the workhorse identity of the whole subject:

More generally, $H(X_1,\dots,X_n) = \sum_{i=1}^n H(X_i \mid X_1,\dots,X_{i-1})$. Conditioning never increases entropy, $H(Y\mid X) \le H(Y)$, with equality iff $X$ and $Y$ are independent — extra side information can only reduce (or preserve) uncertainty.

Mutual Information and Relative Entropy

Relative Entropy (KL Divergence)

The Kullback–Leibler divergence measures the inefficiency of assuming distribution $q$ when the truth is $p$ — the extra bits per symbol paid by coding for the wrong distribution:

By Gibbs’ inequality, $D(p\,|\,q) \ge 0$, with equality iff $p = q$. It is not a metric — asymmetric and violating the triangle inequality — but it is the canonical “statistical distance” and underlies hypothesis testing (Stein’s lemma) and large-deviations theory.

Mutual Information

Mutual information is the reduction in uncertainty about $X$ from observing $Y$ (and symmetrically). It is non-negative, symmetric, and zero iff $X \perp Y$. The relationships are captured by the familiar information diagram:

flowchart LR
    subgraph HX["H(X)"]
      A["H(X|Y)"]
    end
    subgraph HY["H(Y)"]
      C["H(Y|X)"]
    end
    A --- B["I(X;Y)"]
    B --- C

The data-processing inequality is the structural consequence that matters most in practice: if $X \to Y \to Z$ forms a Markov chain (post-processing $Y$ to get $Z$), then

No deterministic or stochastic processing of the data can manufacture information about $X$ that the data did not already contain. This single inequality bounds estimators, justifies sufficient statistics, and constrains the layers of any pipeline.

The Asymptotic Equipartition Property

The AEP is the information-theoretic analog of the law of large numbers, and it is the technical engine behind both coding theorems.

Source Coding (Compression)

The Source Coding Theorem and Kraft’s Inequality

A code assigns to each symbol a binary string (codeword). For a code to be uniquely decodable, codeword lengths $\ell(x)$ must satisfy the Kraft–McMillan inequality:

Conversely, any lengths satisfying Kraft admit a prefix (instantaneously decodable) code. Minimizing expected length $L = \sum_x p(x)\ell(x)$ subject to Kraft, via Lagrange multipliers, gives the ideal lengths $\ell^*(x) = -\log_2 p(x)$ and recovers the entropy.

Huffman Coding

Huffman’s algorithm builds the provably optimal symbol-by-symbol prefix code by a greedy bottom-up merge: repeatedly combine the two least-probable symbols into a subtree, summing their probabilities, until one tree remains. Its expected length satisfies $H(X) \le L_{\text{Huffman}} < H(X)+1$ and no other prefix code does better on the same symbol distribution.

import heapq
from collections import Counter

def huffman(symbol_probs):
    """Build a Huffman code; returns {symbol: bitstring}."""
    heap = [[p, [sym, ""]] for sym, p in symbol_probs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = "0" + pair[1]
        for pair in hi[1:]:
            pair[1] = "1" + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return {sym: code for sym, code in heap[0][1:]}

probs = {"a": 0.5, "b": 0.25, "c": 0.125, "d": 0.125}
code = huffman(probs)
L = sum(probs[s] * len(c) for s, c in code.items())  # 1.75 bits

Arithmetic Coding

Huffman’s one-bit-per-symbol overhead is wasteful when symbols are highly skewed (a symbol with $p=0.9$ “deserves” $0.15$ bits but Huffman must spend at least one). Arithmetic coding sidesteps this by encoding the entire message as a single real number in $[0,1)$. The current interval is recursively subdivided in proportion to the symbol probabilities; the final interval is identified by any binary fraction inside it.

Its expected length for a block of $n$ symbols satisfies $L_n < nH(X) + 2$, so the per-symbol redundancy is $O(1/n)$ — vanishing, regardless of how skewed the source is. It also pairs naturally with adaptive and context models (the basis of modern codecs like the range coder in PPM/CABAC and the entropy stage of many image and video standards).

Channel Capacity and the Noisy-Channel Theorem

Discrete Memoryless Channels

A discrete memoryless channel (DMC) is specified by an input alphabet $\mathcal{X}$, output alphabet $\mathcal{Y}$, and transition probabilities $p(y \mid x)$, applied independently to each transmitted symbol. The capacity is the maximum mutual information over input distributions:

The Noisy-Channel Coding Theorem

The proof of achievability is a non-constructive tour de force: pick a codebook of $2^{nR}$ codewords i.i.d. from the capacity-achieving input distribution, decode by joint typicality (declare the unique codeword jointly typical with the received sequence), and show the average error over random codebooks $\to 0$ when $R<C$. Since the average is small, some codebook is good. The converse follows from Fano’s inequality, which lower-bounds the error probability by the residual conditional entropy:

The theorem is a genuine threshold phenomenon: arbitrarily reliable communication is possible up to $C$ and impossible beyond it. For the bandlimited Gaussian channel with bandwidth $B$, signal power $P$, and noise power spectral density $N_0$, this specializes to the celebrated Shannon–Hartley formula

Error-Correcting Codes

Shannon proved capacity-achieving codes exist; coding theory builds them with structure so that encoding and decoding are efficient. The central objects are linear block codes over finite fields.

Linear Block Codes and the Hamming Bound

An $[n,k]$ linear code over $\mathbb{F}_q$ is a $k$-dimensional subspace of $\mathbb{F}_q^n$: $k$ information symbols map to $n$ transmitted symbols, giving rate $R = k/n$. It is described by a generator matrix $G$ (codewords are $\mathbf{c} = \mathbf{m}G$) and a parity-check matrix $H$ with $G H^\top = 0$, so that $\mathbf{c}H^\top = 0$ for every codeword. The minimum distance $d$ — the smallest Hamming weight of a nonzero codeword — governs error handling: a code can detect up to $d-1$ errors and correct up to $\lfloor (d-1)/2 \rfloor$. The Hamming (sphere-packing) bound limits how good a code can be:

Hamming Codes

The $[7,4]$ Hamming code is the canonical single-error-correcting code: $d=3$, so it corrects any single bit error. Decoding is elegant — compute the syndrome $\mathbf{s} = \mathbf{r}H^\top$ of the received word $\mathbf{r}$; if $\mathbf{s}=0$ the word is a codeword, otherwise $\mathbf{s}$ equals the column of $H$ indexed by the error position, which directly names the bit to flip. Hamming codes are perfect: they meet the sphere-packing bound with equality, tiling the space exactly.

import numpy as np

# Parity-check matrix for the [7,4] Hamming code (columns 1..7 in binary)
H = np.array([
    [0,0,0,1,1,1,1],
    [0,1,1,0,0,1,1],
    [1,0,1,0,1,0,1],
])

def correct(r):
    s = H.dot(r) % 2            # syndrome
    pos = int("".join(map(str, s)), 2)   # column index (1-based) or 0
    if pos:
        r = r.copy()
        r[pos - 1] ^= 1        # flip the indicated bit
    return r

Reed–Solomon Codes

Reed–Solomon (RS) codes are nonbinary $[n,k]$ codes over $\mathbb{F}_q$ (typically $q=256$, working on bytes) built by evaluating a degree-$<k$ message polynomial at $n$ distinct field points. They are maximum-distance-separable (MDS): they meet the Singleton bound

with equality, the best possible distance for given $n,k$. An $[n,k]$ RS code corrects up to $\lfloor (n-k)/2 \rfloor$ symbol errors (or twice as many erasures), and because errors are counted per symbol, a single corrupted byte costs only one of the budget no matter how many of its bits flipped — making RS ideal against burst errors. Practical decoders (Berlekamp–Massey, Euclidean) run in polynomial time. RS codes underpin QR codes, CDs/DVDs, deep-space telemetry (the Voyager probes), and RAID-6 storage.

LDPC Codes and Modern Capacity-Approaching Codes

Low-density parity-check (LDPC) codes, introduced by Gallager (1962) and rediscovered in the 1990s, are linear codes whose parity-check matrix $H$ is sparse. That sparsity is the whole point: it admits near-linear-time iterative decoding by belief propagation (the sum–product algorithm) on the code’s bipartite Tanner graph, passing log-likelihood messages between variable nodes and check nodes until they converge.

flowchart TB
    subgraph V["Variable nodes (bits)"]
      v1((v1)); v2((v2)); v3((v3)); v4((v4))
    end
    subgraph C["Check nodes (parity)"]
      c1["c1"]; c2["c2"]
    end
    v1 --- c1; v2 --- c1; v3 --- c1
    v2 --- c2; v3 --- c2; v4 --- c2

Well-designed LDPC ensembles provably approach the Shannon limit — the density-evolution analysis predicts a decoding threshold noise level below which the bit-error rate $\to 0$, and optimized irregular degree distributions push that threshold to within hundredths of a dB of capacity. LDPC codes are now standard in Wi-Fi (802.11n/ac/ax), 5G NR data channels, DVB-S2, and 10GBASE-T Ethernet. Alongside them sit two other capacity-approaching families: turbo codes (parallel concatenated convolutional codes with iterative decoding, used in 3G/4G and deep space) and polar codes (Arıkan, 2009 — the first provably capacity-achieving codes with explicit construction and $O(n\log n)$ decoding, adopted for 5G control channels).

Rate–Distortion Theory

Lossless compression bottoms out at $H(X)$. Rate–distortion theory answers the lossy question: if we tolerate average distortion $D$ under a measure $d(x,\hat{x})$, what is the minimum rate $R(D)$ needed to represent the source? It is the dual of channel coding — instead of maximizing mutual information subject to a power constraint, we minimize it subject to a fidelity constraint.

$R(D)$ is non-increasing and convex: more allowed distortion buys a lower rate, with diminishing returns. Two cornerstone results make it concrete:

• Gaussian source, squared-error distortion. For $X \sim \mathcal{N}(0,\sigma^2)$, \(R(D) = \begin{cases} \frac{1}{2}\log_2 \frac{\sigma^2}{D}, & 0 \le D \le \sigma^2 \\ 0, & D > \sigma^2. \end{cases}\) Each extra bit halves the distortion (the classic 6 dB/bit rule), and once $D \ge \sigma^2$ the source is described for free by its mean.

• Bernoulli source, Hamming distortion. For $X \sim \text{Bernoulli}(p)$ with $p \le \tfrac12$, \(R(D) = \begin{cases} H_b(p) - H_b(D), & 0 \le D \le p \\ 0, & D > p. \end{cases}\)

The rate–distortion theorem establishes that $R(D)$ is the true asymptotic limit (achievable and not beatable), proved again by a random-coding/typicality argument that mirrors the channel theorem. This is the theoretical backbone of every lossy codec — JPEG, MP3/AAC, and modern neural compressors all trade rate against a perceptual distortion measure.

Quantum Information Measures

Classical information theory has a non-commutative sibling. Replace probability distributions by density operators $\rho$ (positive semidefinite, unit trace) and the role of Shannon entropy is played by the von Neumann entropy:

where $\lambda_i$ are the eigenvalues of $\rho$. For a diagonal $\rho$ this reduces to Shannon entropy, but quantum mechanics adds genuinely new phenomena:

• Entanglement breaks subadditivity intuition. Classically $H(X,Y) \ge \max{H(X),H(Y)}$, but a pure entangled state can have $S(\rho_{AB}) = 0$ while each subsystem is maximally mixed, $S(\rho_A) = S(\rho_B) > 0$. The conditional entropy can go negative — a uniquely quantum signature with operational meaning in state merging.
• Holevo bound. The accessible classical information extractable from a quantum ensemble ${p_i, \rho_i}$ is capped by the Holevo quantity $\chi = S!\big(\sum_i p_i \rho_i\big) - \sum_i p_i S(\rho_i)$. This is why $n$ qubits store at most $n$ classical bits despite their continuous parameters.
• Quantum mutual information $I(A;B) = S(\rho_A) + S(\rho_B) - S(\rho_{AB})$ remains non-negative (strong subadditivity), and quantum channel capacities (classical, quantum, private) replace the single classical $C$.

These measures are developed in full — together with stabilizer error correction and the quantum threshold theorem — on the Quantum Algorithms Research page. The recurring lesson is that Shannon’s framework is robust enough that its scaffolding (entropy, mutual information, capacity, coding theorems) survives the jump to the quantum world, even as the inequalities acquire new and stranger behavior.

Key Takeaways

• Entropy is the unique measure. Continuity plus a grouping axiom forces Shannon’s $-\sum p\log p$; it is both the compression floor and the building block of every other measure.
• Mutual information is shared bits. $I(X;Y)$ quantifies how much $Y$ reveals about $X$, obeys the data-processing inequality, and defines channel capacity as $\max_{p(x)} I(X;Y)$.
• Capacity is a sharp threshold. Below $C$, error $\to 0$; above $C$, error is bounded away from zero — proved by typicality (achievability) and Fano’s inequality (converse).
• Compression reaches the entropy. Huffman is optimal among prefix codes; arithmetic coding drives per-symbol redundancy to $O(1/n)$ for any source.
• Structured codes approach the limit. Hamming and Reed–Solomon give exact algebraic guarantees; LDPC, turbo, and polar codes approach or achieve capacity with efficient decoders.
• Lossy has its own limit. The rate–distortion function $R(D)$ is the sharp rate for tolerated distortion $D$, the dual of channel coding and the basis of every lossy codec.

See Also