Source and Channel Coding

Two limits run communication: entropy floors compression, capacity ceilings transmission. Shannon says both are reachable, separately.

Four symbols compress to 1.75 average bits against the entropy floor while parity fights a 0.1-flip channel under capacity 0.53

Why Does This Exist?

Files waste space and noisy links corrupt bits; ML ships both (datasets, weights, streaming predictions). Ad-hoc codes either bloat 2x or collapse at the first flipped bit. Shannon's two theorems replace folklore with floors and ceilings plus codes that reach them.

Source coding: $n$ symbols need $\\geq nH$ bits on average, Huffman achieves $< H + 1$ . Channel coding: reliable rate sits $\\leq C = \\max_{p(x)} I(X;Y)$ , achievable with long codes. Separation: do them in sequence. They quantify entropy and mutual information as operating limits.

The one idea you need first

Entropy $H$ is the incompressible core:500 fair coins need 500 bits, period. Capacity $C$ is the pipe width after noise: a binary symmetric channel flipping 10% carries $C = 1 - H(0.1) \\approx 0.531$ bits per use. Codes approach, never cross.

Think of It Like This

Packing versus armored trucks

Source coding packs luggage: Huffman folds common shirts small, rare coats big, averaging near the suitcase's true volume. Channel coding hires armored trucks: parity guards and repetition survive hijacked (flipped) boxes at the cost of fewer boxes per trip.

Packing never protects; armor never shrinks. Where it stops: luggage packing is exact and offline, while ML streams codes online with latency budgets Shannon ignores.

How It Actually Works

Kraft inequality $\\sum 2^{-l_i} \\leq 1$ constrains prefix lengths; Huffman greedily merges rarest symbols, optimal among prefix codes. Arithmetic codes reach $H + 2/n$ bits total. Channel: random coding plus joint-typicality decoding proves achievability below $C$ ; Fano's inequality proves the converse above it. Modern LDPC, turbo, and polar codes operate tenths of a dB from $C$ ; quantization plus entropy coding (weights, JPEG) lives the source side daily.

Worked example

Symbols $[A,B,C,D]$ with $p = [0.5, 0.25, 0.125, 0.125]$ . Entropy $H = 0.5(1) + 0.25(2) + 2(0.125)(3) = 0.5 + 0.5 + 0.75 = 1.75$ bits. Huffman lengths $[1,2,3,3]$ average $0.5(1)+0.25(2)+0.125(3)+0.125(3) = 1.75$ : meets the floor exactly. Fixed 2-bit codes waste $0.25$ bits per symbol (14%). Channel BSC $p = 0.1$ : $H(0.1) = -(0.1\\log_2 0.1 + 0.9\\log_2 0.9) \\approx 0.469$ , $C \\approx 0.531$ . Triple repetition with majority vote pushes error $0.1 \\to 3(0.01)(0.9)+0.001 = 0.028$ at rate $1/3$ : below capacity, working, improvable.

Code

1import numpy as np2
3p = np.array([0.5, 0.25, 0.125, 0.125])4H = float(-(p * np.log2(p)).sum())5lengths = np.array([1, 2, 3, 3])6print(round(H, 2), round(float((p * lengths).sum()), 2))  # -> (1.75, 1.75)

Entropy and Huffman average coincide at 1.75. The floor is met, not just approached.

Watch Out For

Coding to the wrong distribution

Huffman on yesterday's frequencies bloats today's drifted stream past fixed-length: the $H+1$ guarantee assumes matched $p$ . Model drift silently taxes every byte.

Track frequencies online (adaptive Huffman, arithmetic with updates) or re-fit per block. If average length creeps above $H + 1$ , the code is stale.

Transmitting above capacity and retrying harder

No code, retried forever, beats $C$ : Fano's converse is a wall, not a challenge. Pipelines that push 0.8 bits through a 0.53 pipe "with better engineering" burn latency for guaranteed residual error.

Compress first (lower $H$ ), widen the pipe, or accept distortion (rate-distortion). If error floors persist across codes, physics decided.

The Quick Version

Source floor $H$ with Huffman under $H+1$ ; example hits 1.75 exactly.
Channel ceiling $C = \\max I(X;Y)$ ; BSC at 10% gives 0.531 bits per use.
Separation: compress to $H$ , then protect below $C$ .
Repetition 3x cuts 0.1 error to 0.028 at rate one-third.
Match codes to live frequencies; stale codes bloat past fixed-length.
Above capacity no retry scheme converges; change the pipe or the fidelity.