Skip to content
LumenaryAcademy
Waves 85 min

Information theory and error-correcting codes

How many bits a source really produces, how many a channel can carry, and the codes (from parity bits to the LDPC and polar codes of 5G) that get close to Shannon's limit.

Code tested · 6AI-draftedAwaiting review by an electrical engineer

Your guides: Chloe · The Physicist, Margaret · The Bench Engineer, Gideon · The Design Reviewer

MotivationH

Bits that arrive right

Scratch a QR code or cover part of it with a sticker, and a phone still reads it. A phone at the edge of a cell receives a signal barely above the noise, yet the web page that arrives has no wrong letters. Spacecraft billions of kilometres away send pictures with transmitters of a few tens of watts. None of this would work if the bits had to arrive intact on their own; every one of these links makes errors constantly and corrects them.

In 1948 Claude Shannon, at Bell Laboratories, published A Mathematical Theory of Communication, which answered two questions that engineers had not known how to ask precisely. How much information does a source really produce? And how much information can a noisy channel carry? His answers, entropy and capacity, are this lesson's first half. His most surprising claim, that a channel can deliver information with as few errors as you like at any rate below its capacity, took engineers fifty years to approach in practice. The codes that did it, and the simpler codes that came before, are the second half.

IntuitionH

Surprise, redundancy and the repetition code

Information is surprise. Being told that the Sun rose this morning tells you almost nothing; being told the result of a fair coin toss tells you exactly one bit; being told which of 64 equally likely squares a chess piece stands on tells you six bits, because it takes six yes-or-no questions to find out. A source whose symbols are predictable produces less information than one whose symbols are not, and can be compressed. That is the job of source coding (ZIP files, JPEG, the audio codec in a phone call).

Channel coding does the opposite: it adds redundancy, carefully, so that errors can be detected or corrected. The obvious way is to repeat each bit three times and take a majority vote at the receiver. If the channel flips each bit independently with probability pp, the vote is wrong only when two or three of the copies flip, with probability 3p2(1−p)+p3≈3p23p^2(1 - p) + p^3 \approx 3p^2. At p=0.01p = 0.01 that is about 3×10−43\times10^{-4}, thirty times better. But the price is steep: the information rate falls to a third, and to push the error rate lower still you must repeat more, so the rate goes to zero as the error rate does.

Before Shannon, everyone assumed that trade was unavoidable. Shannon proved it was not.

DefinitionsH

Entropy and capacity

Definition— entropy

A source emits symbols xx independently with probabilities p(x)p(x). Its entropy is

H=−∑xp(x)log⁡2p(x) bits per symbol,H = -\sum_x p(x)\log_2 p(x)\ \text{bits per symbol},

the average surprise −log⁡2p(x)-\log_2 p(x) of a symbol. It ranges from 0 (one symbol is certain) to log⁡2M\log_2 M (all MM symbols equally likely).

Theorem— Shannon's source coding theorem (informal)

A source of entropy HH can be encoded into an average of H+εH + \varepsilon bits per symbol, for any ε>0\varepsilon \gt 0, and can be decoded without loss; no lossless code can use fewer than HH bits per symbol on average.

Definition— channel capacity

The capacity CC of a channel is the largest rate at which information can be sent through it with an error probability that can be made arbitrarily small. For a binary symmetric channel that flips each bit with probability pp, C=1−H(p)C = 1 - H(p) bits per use, where H(p)=−plog⁡2p−(1−p)log⁡2(1−p)H(p) = -p\log_2 p - (1 - p)\log_2(1 - p). For a channel of bandwidth BB with additive white Gaussian noise and signal-to-noise ratio SNR, the Shannon–Hartley formula gives

C=Blog⁡2(1+SNR) bit/s.C = B\log_2(1 + \text{SNR})\ \text{bit/s}.

Theorem— Shannon's channel coding theorem (informal)

For any rate R<CR \lt C and any ε>0\varepsilon \gt 0, there exist codes of rate RR (with long enough blocks) whose probability of decoding error is below ε\varepsilon. For any rate R>CR \gt C, the error probability is bounded away from zero, whatever the code.

Shannon's proof was not constructive. He showed that a code chosen at random is good on average, so good codes must exist, but a random code of useful length is far too large to decode by searching. The history of coding since 1948 is the search for codes with structure enough to decode quickly and randomness enough to approach capacity. For more on the mathematics, see information theory in Lumenary Math.

ComputationC

Entropy and capacity, computed

The program computes a few entropies, the capacity of some links met in this level (the Wi-Fi and satellite budgets from antennas and radio links among them), the least energy per bit that any code needs, and the capacity of a binary symmetric channel.

python
import math

def entropy(probs):
    """Shannon entropy in bits: H = -sum p log2 p (terms with p = 0 contribute nothing)."""
    return -sum(p * math.log2(p) for p in probs if p > 0)

print("entropy of some sources (bits per symbol)")
for name, probs in [("fair coin", [0.5, 0.5]), ("coin with P(heads) = 0.1", [0.1, 0.9]),
                    ("fair die", [1 / 6] * 6), ("four symbols 1/2, 1/4, 1/8, 1/8", [0.5, 0.25, 0.125, 0.125])]:
    print(f"  {name:32} H = {entropy(probs):.3f}")

def capacity(bandwidth_hz, snr_db):
    return bandwidth_hz * math.log2(1 + 10 ** (snr_db / 10))

def si(x, unit):
    """Format a number with a k or M prefix, e.g. si(3100, 'Hz') -> '3.1 kHz'."""
    for factor, prefix in [(1e6, "M"), (1e3, "k"), (1, "")]:
        if x >= factor:
            return f"{x / factor:.4g} {prefix}{unit}"

print("\nShannon capacity C = B log2(1 + SNR)")
for name, b, snr in [("telephone line", 3.1e3, 35), ("Wi-Fi link of the last lesson", 80e6, 25.1),
                     ("5G carrier at the cell edge", 100e6, 5), ("5G carrier near the mast", 100e6, 25),
                     ("satellite TV transponder", 27e6, 15.0)]:
    c = capacity(b, snr)
    print(f"  {name:31} B = {si(b, 'Hz'):>9}, SNR = {snr:4.1f} dB: C = {si(c, 'bit/s'):>14} "
          f"({c / b:5.2f} bit/s/Hz)")

print("\nminimum Eb/N0 for reliable communication at spectral efficiency eta = C/B")
for eta in [8, 4, 2, 1, 0.5, 0.1, 0.001]:
    ebn0 = (2 ** eta - 1) / eta                  # from C/B = log2(1 + (Eb/N0) * C/B)
    print(f"  eta = {eta:6.3f} bit/s/Hz: Eb/N0 >= {10 * math.log10(ebn0):6.2f} dB")
print(f"  limit as eta -> 0: ln 2 = {10 * math.log10(math.log(2)):.2f} dB")

print("\nbinary symmetric channel: C = 1 - H(p) bits per use")
for p in [0.0, 0.01, 0.1, 0.5]:
    print(f"  crossover p = {p:4.2f}: C = {1 - entropy([p, 1 - p]):.3f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The four-symbol source with probabilities 12,14,18,18\tfrac12, \tfrac14, \tfrac18, \tfrac18 has an entropy of exactly 1.75 bits, and the code 0, 10, 110, 111 achieves it. The capacity table explains some history: telephone modems stalled at 33.6 kbit/s in the mid-1990s because the analog telephone channel, about 3.1 kHz wide with an SNR around 35 dB, has a capacity of about 36 kbit/s. The Wi-Fi link computed in the previous lesson could in principle carry 667 Mbit/s per spatial stream; real Wi-Fi at that SNR achieves a good fraction of it, with the gap set by its constellations, coding and overheads.

ExplanationH

Detecting errors: parity and CRCs

The simplest code adds one parity bit to a block, chosen so that the number of 1 bits is even. Any single bit error makes it odd, and the receiver notices. Two errors cancel out and go unnoticed. Parity is still used where errors are rare and independent, for example on each byte of some serial links and memory buses.

A cyclic redundancy check (CRC) is much stronger and almost as cheap. Treat the message bits as the coefficients of a polynomial M(x)M(x) over the two-element field, where addition is XOR (as in Boolean algebra). Choose a generator polynomial G(x)G(x) of degree rr. The sender appends rr check bits, the remainder of xrM(x)x^rM(x) divided by G(x)G(x), so the transmitted polynomial is exactly divisible by G(x)G(x). The receiver divides what arrives by G(x)G(x); a non-zero remainder means an error.

Example— A three-bit CRC by hand

Take the message 1101 and G(x)=x3+x+1G(x) = x^3 + x + 1, written 1011. Append three zeros and divide, subtracting (XORing) 1011 under each leading 1:

StepBits
start1101000
XOR 1011 at bit 10110000
XOR 1011 at bit 20011100
XOR 1011 at bit 30001010
XOR 1011 at bit 40000001

The remainder is 001, so the sender transmits 1101001, which is divisible by 1011. In hardware this is a shift register with a few XOR gates, one clock per bit.

Theorem— CRCs catch short bursts

Let G(x)G(x) have degree rr and a non-zero constant term. Then the CRC detects every burst of errors confined to rr or fewer consecutive bits.

Proof

An error pattern is a polynomial E(x)E(x) added to the transmission; it goes undetected exactly when G(x)G(x) divides E(x)E(x). A burst of length at most rr starting at bit ii is E(x)=xiB(x)E(x) = x^iB(x) with B(0)=1B(0) = 1 and deg⁡B<r\deg B \lt r. Since GG has a non-zero constant term it shares no factor with xix^i, so G∣xiBG \mid x^iB would require G∣BG \mid B, which is impossible for a non-zero BB of smaller degree than GG.

∎

Good generators do more: the standard CRC-32 also detects every pattern of up to three bit errors in a frame of Ethernet size, and a random corruption slips through with probability only about 2−322^{-32}. The program implements CRC-32 bit by bit, checks it against Python's zlib, and tests both codes against four kinds of damage to a 512-bit frame.

python
import random
import zlib

def parity(data: bytes) -> int:
    """Even parity: 1 if the number of 1 bits is odd, so that appending it makes the count even."""
    return sum(bin(b).count("1") for b in data) % 2

def crc32(data: bytes) -> int:
    """CRC-32 as used by Ethernet, ZIP and PNG, computed one bit at a time.
    The polynomial 0x04C11DB7 is processed bit-reversed (0xEDB88320), starting from all ones."""
    crc = 0xFFFFFFFF
    for byte in data:
        crc ^= byte
        for _ in range(8):
            crc = (crc >> 1) ^ 0xEDB88320 if crc & 1 else crc >> 1
    return crc ^ 0xFFFFFFFF

message = "Habari kutoka Nairobi".encode()
print(f"our CRC-32: {crc32(message):08x}   zlib's: {zlib.crc32(message):08x}")
print(f"check value for '123456789': {crc32(b'123456789'):08x}")

def flip(data: bytes, positions):
    b = bytearray(data)
    for p in positions:
        b[p // 8] ^= 1 << (p % 8)
    return bytes(b)

rng = random.Random(1948)
frame = bytes(rng.randrange(256) for _ in range(64))       # a 512-bit frame
n_bits = 8 * len(frame)

def burst():
    """A burst of length L <= 32: first and last bits flipped, those between at random."""
    start, length = rng.randrange(n_bits - 32), rng.randrange(2, 33)
    inner = [p for p in range(start + 1, start + length - 1) if rng.random() < 0.5]
    return [start, start + length - 1] + inner

good_parity, good_crc = parity(frame), crc32(frame)
trials = 4000
for name, make_errors in [("2 random bit errors", lambda: rng.sample(range(n_bits), 2)),
                          ("3 random bit errors", lambda: rng.sample(range(n_bits), 3)),
                          ("a burst of up to 32 bits", burst),
                          ("every bit flipped with prob. 1/2", lambda: [p for p in range(n_bits) if rng.random() < 0.5])]:
    caught_parity = caught_crc = 0
    for _ in range(trials):
        bad = flip(frame, make_errors())
        caught_parity += parity(bad) != good_parity
        caught_crc += crc32(bad) != good_crc
    print(f"{name:33} parity detects {100 * caught_parity / trials:5.1f} %,  CRC-32 detects {100 * caught_crc / trials:6.2f} %")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Parity catches exactly the odd-sized errors and so misses half of all bursts and random corruptions; CRC-32 catches everything thrown at it. A CRC only detects: the usual response is to discard the frame and ask for it again, which is how Ethernet and Wi-Fi frames, ZIP archives and PNG images protect themselves (see networking in Lumenary CS for retransmission protocols).

ExplanationH

Correcting errors: Hamming(7,4)

To correct an error, the receiver must work out which bit is wrong. Richard Hamming, frustrated in 1947 by a relay computer at Bell Labs that stopped at every detected error, found the first family of codes that could.

Definition— Hamming distance and minimum distance

The Hamming distance between two words of equal length is the number of positions in which they differ. The minimum distance dd of a code is the smallest distance between two different codewords. A code with d=2t+1d = 2t + 1 can correct any tt errors: the received word is still closer to the transmitted codeword than to any other. It can alternatively detect up to d−1d - 1 errors.

The Hamming(7,4) code adds three parity bits to four data bits. Each parity bit checks a different group of three data bits, as the diagram shows: put the data bits in the overlapping regions of three circles and choose each parity bit so that its circle holds an even number of 1s. A single wrong bit upsets a unique combination of circles, and that combination points to it.

p1 = 0p2 = 1p3 = 0d1 = 1d2 = 0d3 = 1d4 = 1circle Acircle Bcircle Ceach circle holdsan even numberof 1s
Hamming(7,4) as three overlapping circles, for the data 1011. Data bits d1 to d4 sit in the overlaps, parity bits p1 to p3 in the parts belonging to one circle only, and each parity bit makes its circle's count of 1s even. If one bit is flipped, the circles whose parity fails identify it: only circle A fails means p1; A and B means d1; all three means d4.

In matrix form, with the codeword written [d1 d2 d3 d4 p1 p2 p3][d_1\,d_2\,d_3\,d_4\,p_1\,p_2\,p_3] and arithmetic modulo 2, encoding multiplies the data by a generator matrix GG and checking multiplies the received word rr by a parity-check matrix HH:

G=(1000110010010100100110001111),H=(110110010110100111001).G = \begin{pmatrix} 1&0&0&0&1&1&0\\ 0&1&0&0&1&0&1\\ 0&0&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{pmatrix}, \qquad H = \begin{pmatrix} 1&1&0&1&1&0&0\\ 1&0&1&1&0&1&0\\ 0&1&1&1&0&0&1 \end{pmatrix}.

Every codeword satisfies Hc=0Hc = 0. If one bit is flipped, r=c+eir = c + e_i and the syndrome s=Hr=Heis = Hr = He_i is the ii-th column of HH. The seven columns are distinct and non-zero, so the syndrome names the bad position. The program checks all of this exhaustively and then runs the code over a noisy channel.

python
import itertools
import numpy as np

# Hamming(7,4) in systematic form: codeword = [d1 d2 d3 d4 p1 p2 p3], all arithmetic modulo 2
P = np.array([[1, 1, 0],          # p1 = d1 + d2 + d4, p2 = d1 + d3 + d4, p3 = d2 + d3 + d4
              [1, 0, 1],
              [0, 1, 1],
              [1, 1, 1]])
G = np.hstack([np.eye(4, dtype=int), P])          # generator matrix: codeword = data @ G
H = np.hstack([P.T, np.eye(3, dtype=int)])        # parity-check matrix: H @ codeword = 0

def encode(data):
    return data @ G % 2

def decode(r):
    """Syndrome decoding: the syndrome equals the column of H at the error position."""
    s = H @ r % 2
    r = r.copy()
    if s.any():
        position = np.flatnonzero((H.T == s).all(axis=1))[0]
        r[position] ^= 1
    return r[:4]

messages = np.array(list(itertools.product([0, 1], repeat=4)))
codewords = encode(messages)
weights = codewords.sum(axis=1)
print("all 16 codewords satisfy H c = 0:", bool((H @ codewords.T % 2 == 0).all()))
print("minimum distance = smallest non-zero weight =", weights[weights > 0].min())

fixed = sum((decode(c ^ e) == m).all() for m, c in zip(messages, codewords) for e in np.eye(7, dtype=int))
print(f"single errors corrected: {fixed} of {16 * 7}")
double = [np.array([int(i in pair) for i in range(7)]) for pair in itertools.combinations(range(7), 2)]
fixed2 = sum((decode(c ^ e) == m).all() for m, c in zip(messages, codewords) for e in double)
print(f"double errors corrected: {fixed2} of {16 * len(double)}")

# Over a binary symmetric channel that flips each bit with probability p
rng = np.random.default_rng(7)
n_blocks = 100_000
for p in [0.1, 0.01, 0.001]:
    data = rng.integers(0, 2, (n_blocks, 4))
    flips = (rng.random((n_blocks, 7)) < p).astype(int)
    received = encode(data) ^ flips
    syndromes = received @ H.T % 2
    # look up the error position from the syndrome (a table of 8 entries, as hardware does)
    table = {tuple(H[:, j]): j for j in range(7)}
    for i in np.flatnonzero(syndromes.any(axis=1)):
        received[i, table[tuple(syndromes[i])]] ^= 1
    coded_fail = np.mean((received[:, :4] != data).any(axis=1))
    uncoded_fail = 1 - (1 - p) ** 4
    print(f"p = {p:5.3f}: 4-bit block wrong, uncoded {uncoded_fail:.2e}, Hamming(7,4) {coded_fail:.2e}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

All 112 single errors are corrected and, as the minimum distance of 3 predicts, none of the 336 double errors is: two flipped bits make the received word closer to a different codeword, and the decoder confidently "corrects" it to the wrong one. Over a channel that flips 1 % of bits, a 4-bit block is wrong 3.9 % of the time without coding and 0.2 % with Hamming(7,4); at 0.1 % the improvement is two hundredfold.

ExplanationH

Convolutional codes and the Viterbi algorithm

Block codes chop the data into blocks. A convolutional code encodes a continuous stream: each input bit, together with the few bits before it, produces a few output bits. The classic example has rate 1/2 and constraint length 3: for input bit uu and the two previous bits s1,s2s_1, s_2, it sends u⊕s1⊕s2u \oplus s_1 \oplus s_2 and u⊕s2u \oplus s_2 (the "7, 5" code, from the generator patterns 111 and 101 in octal). The encoder is a two-bit shift register, so it has four states, and its behaviour is a table:

State s1s2s_1s_2Input 0: output, next stateInput 1: output, next state
0000, go to 0011, go to 10
0111, go to 0000, go to 10
1010, go to 0101, go to 11
1101, go to 0110, go to 11

Unrolled in time, the table becomes a trellis, and every possible message is a path through it.

00011011statesolid branch: input bit 0; dashed branch: input bit 1
The trellis of the rate-1/2, constraint-length-3 convolutional code: four states (s1 s2) at each time step, with a branch for each input bit. The highlighted path is the input 1, 0, 1, 1, which leaves state 00 and produces the output pairs 11, 10, 00, 01. The Viterbi decoder finds the path whose outputs are closest to what was received.

Decoding means finding the path whose output sequence is closest to the received sequence. There are 2n2^n paths for nn bits, but Andrew Viterbi's algorithm (1967) needs only to keep, for each state at each time, the best path that arrives there, because any longer best path through that state must begin with it (the same principle as in shortest-path algorithms and dynamic programming). The cost is proportional to nn times the number of states. The program encodes 20 bits, damages three of the 44 transmitted bits, and decodes; then it measures the error rate over a noisy channel.

python
import numpy as np

# Rate-1/2 convolutional code with constraint length 3 and generators 7 and 5 (octal):
# for each input bit u, output u+s1+s2 and u+s2 (mod 2), where s1, s2 are the two previous bits.
def conv_encode(bits):
    s1 = s2 = 0
    out = []
    for u in list(bits) + [0, 0]:                 # two zeros flush the encoder back to state 00
        out += [u ^ s1 ^ s2, u ^ s2]
        s1, s2 = u, s1
    return np.array(out)

def viterbi_decode(received):
    """Hard-decision Viterbi decoding over the 4-state trellis (state = (s1, s2))."""
    n = len(received) // 2
    INF = 10**9
    metric = {(0, 0): 0, (0, 1): INF, (1, 0): INF, (1, 1): INF}
    history = []
    for t in range(n):
        r = received[2 * t: 2 * t + 2]
        new_metric, choice = {}, {}
        for (s1, s2), m in metric.items():
            for u in (0, 1):
                expected = (u ^ s1 ^ s2, u ^ s2)
                cost = m + (expected[0] != r[0]) + (expected[1] != r[1])   # Hamming distance
                nxt = (u, s1)
                if cost < new_metric.get(nxt, INF + 1):
                    new_metric[nxt], choice[nxt] = cost, ((s1, s2), u)
        metric = new_metric
        history.append(choice)
    state, bits = (0, 0), []                        # the flushed encoder ends in state 00
    for choice in reversed(history):                # trace the surviving path backwards
        state, u = choice[state]
        bits.append(u)
    return np.array(bits[::-1][:-2])

rng = np.random.default_rng(1967)
msg = rng.integers(0, 2, 20)
code = conv_encode(msg)
noisy = code.copy()
noisy[[3, 17, 30]] ^= 1                              # three scattered channel errors
print("message :", "".join(map(str, msg)))
print("decoded :", "".join(map(str, viterbi_decode(noisy))), "(3 channel errors corrected)")

for p in [0.05, 0.02, 0.01]:
    msg = rng.integers(0, 2, 20000)
    code = conv_encode(msg)
    rx = code ^ (rng.random(len(code)) < p)
    ber = np.mean(viterbi_decode(rx) != msg)
    print(f"channel flips {p:.0%} of bits: decoded BER {ber:.1e}  (uncoded: {p:.0e})")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The three scattered errors are corrected, and with 1 % of channel bits flipped, the decoded error rate is 5×10−55\times10^{-5}, two hundred times lower.

Convolutional codes with Viterbi decoding were the workhorses of the late twentieth century: in deep-space probes, in GSM phones, in digital television, and in Wi-Fi from 802.11a, whose code has constraint length 7 (64 states). Feeding the decoder the received voltages instead of hard bits gains about 2 dB on its own, a point that matters for every code in the next section.

ExplanationH

Near the Shannon limit: turbo, LDPC and polar codes

By the 1980s the best practical schemes (a convolutional code inside a Reed–Solomon code) were still 2 to 3 dB from capacity. Then three ideas closed the gap.

  • Turbo codes (Claude Berrou, Alain Glavieux and Punya Thitimajshima, 1993) put two simple convolutional encoders in parallel, the second fed with an interleaved copy of the data, and decode iteratively: two decoders exchange soft estimates of each bit, each improving the other's, for several rounds. The first results, within about 0.5 dB of the limit at an error rate of 10−510^{-5}, were met with disbelief, then reproduced. Turbo codes carried the data of 3G and 4G mobile networks.
  • Low-density parity-check (LDPC) codes were invented by Robert Gallager in his 1960 doctoral thesis and largely forgotten, because the computers of the day could not decode them, until David MacKay and Radford Neal (among others) rediscovered them in the mid-1990s. An LDPC code is defined, like Hamming's, by a parity-check matrix HH, but a huge and sparse one: thousands of columns with only a few 1s in each. Decoding passes probabilistic messages back and forth between bits and the parity checks they take part in (belief propagation), and parallelises beautifully in hardware. With very long, carefully designed codes, LDPC decoding has been shown to come within 0.0045 dB of the Shannon limit (Chung, Forney, Richardson and Urbanke, 2001); practical codes of a few thousand bits are within about 1 dB. LDPC codes protect satellite TV (DVB-S2), Wi-Fi's faster modes, 10-gigabit Ethernet over copper, the flash memory in solid-state drives, and the data channels of 5G.
  • Polar codes (Erdal Arıkan, 2009) were the first codes proved to achieve capacity with an efficient encoder and decoder. A recursive transform "polarises" NN uses of a channel into some that are almost perfect and some that are almost useless; information goes on the good ones and the bad ones are frozen to known values. With a list decoder and a CRC to choose among the candidates, polar codes perform very well at short block lengths.

When 3GPP designed 5G NR in 2016–2017, it chose LDPC codes for the data channels, where blocks are long and throughput is high, and polar codes for the control channels, where messages are short and must be decoded reliably; both are specified in TS 38.212 (3GPP). 4G had used turbo codes for data and convolutional codes for control.

How close is close? For long blocks, within a fraction of a decibel. For short blocks the limit itself moves: Shannon's theorem is about infinitely long blocks, and a code of a few hundred bits must pay an unavoidable penalty, which information theorists have quantified precisely since about 2010. Much research in 2026 is about short codes for low-latency control signals and machine-type communication, and about decoders that use less energy per bit, since in a modern modem the channel decoder is one of the biggest consumers of power.

ExplanationH

The professional view

  • Standards specify codes exactly. Engineers implementing 5G, Wi-Fi or DVB-S2 do not design codes; they implement the ones in the specification, bit for bit, and compete on decoder speed, power and silicon area. Space agencies agree theirs through the CCSDS.
  • Codes are everywhere, not just in radio. Reed–Solomon codes protect QR codes, CDs and DVDs and the storage clusters of data centres (see storage at scale in Lumenary CS); SSDs use LDPC; DRAM in servers uses error-correcting codes on every word; PCIe 6.0 and recent Ethernet standards add forward error correction to their links.
  • Hybrid ARQ. Mobile and Wi-Fi links combine a CRC (to detect a failed block) with retransmission that sends more redundancy rather than the same bits again, and the receiver combines everything it has received. The CRC decides when to stop.
  • Simulation is the design tool. Codes and decoders are evaluated by simulating billions of blocks on computers and FPGAs, exactly as in this lesson's programs but faster, to measure error rates down to 10−1010^{-10} and to find "error floors" where a code stops improving.
History & global context

A short history

Shannon's 1948 paper defined the field in one stroke. Hamming's codes followed in 1950, Irving Reed and Gustave Solomon's codes in 1960, Gallager's LDPC codes in 1960–62 and Viterbi's algorithm in 1967. Concatenated Reed–Solomon and convolutional codes flew on deep-space missions from the late 1970s. Turbo codes (1993) and the rediscovery of LDPC codes (1995–96) brought practical codes to within a decibel of capacity, and Arıkan's polar codes (2009) supplied the first provably capacity-achieving construction with efficient decoding. Within a decade of their invention, polar codes were in the 5G standard and in billions of phones.

Common misconceptionsH

Common misconceptions

Misconception

"A clever enough code or modulation could beat the Shannon limit." Capacity is a theorem, not an engineering record: no scheme can communicate reliably above CC, or at an Eb/N0E_b/N_0 below −1.59-1.59 dB, on a Gaussian channel. Claims to the contrary have always turned out to be mistakes, or to assume a different channel (for example, more antennas, which change CC, as the next lesson shows).

Misconception

"A CRC fixes errors." A CRC only detects them. Correction needs a code designed for it, or a retransmission; in practice links use both, with the CRC deciding whether the correction worked.

Misconception

"More redundancy always means fewer errors." At a fixed energy per information bit, redundancy spreads the energy thinner. In that comparison a triple repetition code on a Gaussian channel is no better than no coding at all, and worse if the receiver makes hard 0/1 decisions. Good codes win because their structure is clever, not because they are redundant.

Misconception

"Entropy measures how meaningful a message is." Entropy measures how unpredictable the symbols are, nothing more: a page of random letters has higher entropy than a page of poetry. Shannon was explicit that meaning is not part of the engineering problem.

Exercises

Exercises

1. Information theory and error-correcting codes

Warm-upHuman

A weather station reports one of four conditions each hour: sunny with probability 1/2, cloudy 1/4, rain 1/8 and storm 1/8. What is the entropy of a report, in bits? Give a decimal number.

2. Information theory and error-correcting codes

Warm-upHuman

A 20 MHz Wi-Fi channel has a signal-to-noise ratio of 30 dB. What is its Shannon capacity, in Mbit/s, to the nearest whole number?

3. Information theory and error-correcting codes

Warm-upHuman

A byte is sent with one even-parity bit (9 bits in all). If exactly kk of the 9 bits are flipped, for which values of kk from 1 to 6 is the error always detected? Enter every such kk.

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

4. Information theory and error-correcting codes

CoreHuman

A block code has minimum distance d=7d = 7. What is the largest number of bit errors per block that it is guaranteed to correct?

5. Information theory and error-correcting codes

CoreHuman

Which pairing describes the channel codes chosen for 5G NR?

Choose one

6. Information theory and error-correcting codes

StretchHuman

A start-up claims its new code delivers a bit error rate of 10−610^{-6} over an ordinary single-antenna link with additive white Gaussian noise at Eb/N0=−2E_b/N_0 = -2 dB, using as much bandwidth as it likes. What should an engineer conclude?

Choose one

7. Information theory and error-correcting codes

CoreComputational

Implement crc8(data), the 8-bit CRC with generator x8+x2+x+1x^8 + x^2 + x + 1 (written 0x07, the x8x^8 term implied), initial value 0, processing each byte most significant bit first with no bit reversal. This is the CRC used by the SMBus protocol on many circuit boards.

The tests include the standard check value: crc8(b"123456789") must be 0xF4. They also check that a message followed by its own CRC byte leaves a remainder of zero.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Information theory and error-correcting codes

CoreComputational

Write hamming_decode(r) for the lesson's Hamming(7,4) code, whose codewords are [d1, d2, d3, d4, p1, p2, p3] with the matrices G and H given in the starter. Compute the syndrome s=Hrs = Hr (mod 2); if it is not zero, find the column of H equal to ss and flip that bit. Return the four data bits as a NumPy array.

The tests try every one of the 16 codewords with no error and with each of the 7 possible single errors. Do not modify the array passed in.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources

  • A Mathematical Theory of Communication · Claude E. Shannon · 1948Bell System Technical Journal, vol. 27. The paper that founded information theory, defining entropy and capacity and proving the coding theorems.
  • Error Detecting and Error Correcting Codes · Richard W. Hamming · 1950Bell System Technical Journal, vol. 29. The Hamming codes, and the idea of distance between codewords.
  • Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm · Andrew J. Viterbi · 1967IEEE Transactions on Information Theory, vol. 13. The Viterbi algorithm.
  • Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes · Claude Berrou, Alain Glavieux and Punya Thitimajshima · 1993Proceedings of the IEEE International Conference on Communications (ICC). The paper that showed practical codes could approach capacity.
  • Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels · Erdal Arıkan · 2009The invention of polar codes, published in IEEE Transactions on Information Theory in 2009.
  • On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit · Sae-Young Chung, G. David Forney, Thomas J. Richardson and Rüdiger Urbanke · 2001IEEE Communications Letters, vol. 5. How close LDPC codes can get with very long blocks.
  • 3GPPSpecification TS 38.212 defines the LDPC and polar codes of 5G NR.