Chapter 16: Classical Error Correction Refresher

16.1 Redundancy and Repetition Codes

The simplest idea in error correction is also the most ancient: say it more than once. If you shout "yes, yes, yes!" across a noisy field, your listener can take the majority vote of what they hear and correctly decode your message even if one repetition is garbled. This is the essence of a repetition code.

The 3-Bit Repetition Code

Suppose we want to send a single bit - either 0 or 1 - through a noisy channel where each bit has some probability $p$ of being flipped. Instead of sending the bare bit, we encode it by tripling:

These two strings, $000$ and $111$, are our codewords. The receiver gets three bits, some of which may have been flipped, and decodes by taking the majority vote: whichever value appears at least twice is declared the original bit.

If the channel flips each bit independently with probability $p$, the probability of a decoding failure (two or more flips) is:

This beats the uncoded error rate $p$ whenever $p < 1/2$. For $p = 0.01$, the failure probability drops from $0.01$ to roughly $0.0003$ - an improvement by a factor of 33.

Hamming Distance

Why does the repetition code work? The two codewords $000$ and $111$ differ in every position. The number of positions in which two binary strings differ is called their Hamming distance, named after Richard Hamming, who introduced it in 1950.

The minimum distance of a code is the smallest Hamming distance between any pair of distinct codewords. For the 3-bit repetition code, there are only two codewords and their distance is 3, so $d_{\min} = 3$. The general rule is:

For the 3-bit repetition code with $d = 3$: it can detect up to 2 errors and correct up to 1 error. This matches our majority-vote analysis perfectly.

The Cost of Repetition

The 3-bit repetition code uses 3 physical bits for 1 logical bit - a rate of $R = k/n = 1/3$. A 5-bit repetition code corrects up to 2 errors but has rate $1/5$. In general, the rate is $1/n$, going to zero as we demand more protection. Can we protect multiple data bits simultaneously at a reasonable rate? Yes - and this leads us to linear codes.

Repetition Code in a Quantum Sandbox

Although this chapter is classical, we can illustrate the repetition code concept using CNOT gates on qubits. The circuit below encodes the state of q[0] into three qubits by "copying" it to q[1] and q[2] via CNOT. An X gate on q[1] simulates a single-bit-flip error. Then we decode by majority vote using two CNOT gates and a Toffoli, extracting the corrected bit into q[0]. Run the circuit and verify that the error is corrected.

The corrected logical bit is in q[0], which should read 1 with 100% probability. The other two qubits contain syndrome information (not the original encoded values), so the full output will be 100 for no error, 110 for error on q[1], etc. The key point is that q[0] always recovers the correct logical value. Try moving the error to q[0] or q[2] - any single-bit flip is corrected in q[0].

16.2 Linear Codes: Parity Checks and Hamming Codes

Linear codes are far more sophisticated than repetition. They protect $k$ data bits using $n$ total bits ($n > k$), adding only $r = n - k$ parity check bits. A single parity bit can protect multiple data bits simultaneously.

The Parity Check Idea

A parity check is a single bit that records whether a certain subset of bits has an even or odd number of 1s. For example, given three data bits $d_1, d_2, d_3$, we might define a parity bit:

where $\oplus$ denotes addition modulo 2 (XOR). If $d_1 = 1, d_2 = 0, d_3 = 1$, then $p = 1 \oplus 0 \oplus 1 = 0$. The four-bit string $d_1 d_2 d_3 p = 1010$ satisfies the constraint $d_1 \oplus d_2 \oplus d_3 \oplus p = 0$. If any single bit is flipped, this parity sum becomes 1, alerting us that an error occurred. One parity bit can detect a single error but cannot locate it - it only tells us that something went wrong, not where.

Arithmetic in GF(2)

Classical coding theory takes place over $\text{GF}(2)$ (also written $\mathbb{F}_2$) - the field with two elements, 0 and 1. Addition is XOR and multiplication is AND. The crucial rule is $1 + 1 = 0$ (no carrying). Subtraction equals addition since $-1 = 1$. All the matrix algebra from earlier chapters carries over - we just work mod 2.

The Generator Matrix

A linear code is a code whose set of codewords forms a vector subspace of $\text{GF}(2)^n$. In practice, this means we can describe the entire code using a generator matrix $G$ of size $k \times n$. To encode a message $\mathbf{m} = (m_1, \ldots, m_k)$, we compute:

where all arithmetic is in $\text{GF}(2)$. The result $\mathbf{c}$ is an $n$-bit codeword. Because the encoding is a linear map, the sum of any two codewords is also a codeword - this is the defining property of a linear code.

A generator matrix in systematic form looks like $G = [I_k \mid P]$, where $I_k$ is the $k \times k$ identity matrix and $P$ is a $k \times r$ matrix that determines the parity bits. In systematic form, the first $k$ bits of the codeword are the original data bits, and the last $r$ bits are the parity checks.

The Parity Check Matrix

Dual to $G$ is the parity check matrix $H$ of size $r \times n$ ($r = n - k$). A vector $\mathbf{c}$ is a valid codeword if and only if:

When the generator matrix is in systematic form $G = [I_k \mid P]$, the parity check matrix is:

The key identity $G H^T = \mathbf{0}$ guarantees every codeword satisfies all parity checks. Each row of $H$ is a parity equation that every valid codeword must satisfy.

Syndrome Decoding

Suppose we send a codeword $\mathbf{c}$ and receive $\mathbf{r} = \mathbf{c} + \mathbf{e}$, where $\mathbf{e}$ is the error vector (a string with 1s in the corrupted positions). The syndrome of the received word is:

The syndrome depends only on the error, not on which codeword was sent. This is the magic of linear codes. If $\mathbf{s} = \mathbf{0}$, no error is detected. If $\mathbf{s} \neq \mathbf{0}$, the syndrome tells us exactly which error pattern occurred (for correctable errors).

The Hamming(7,4) Code

Richard Hamming's insight (1950) was to design $H$ so that its columns are all the nonzero binary strings of a given length. For the Hamming(7,4) code ($n=7$, $k=4$, $r=3$), the $2^3 - 1 = 7$ nonzero binary strings of length 3 become the columns of $H$:

Reading off the systematic form, the last three columns form $I_3$, and the first four columns form $P^T$. The corresponding generator matrix in systematic form is:

The first four columns of $G$ are the identity (systematic form), so encoding preserves the four data bits and appends three parity bits.

Parameters of Hamming Codes

The general Hamming code is parametrized by an integer $r \geq 2$:

• Block length: $n = 2^r - 1$
• Data bits: $k = 2^r - 1 - r$
• Parity bits: $r$
• Minimum distance: $d = 3$ (corrects 1 error, detects 2)

As $r$ grows, the rate approaches 1 - the overhead of parity bits becomes negligible relative to the data. This is a dramatic improvement over the repetition code. The Hamming(7,4) code protects 4 data bits with only 3 parity bits, achieving a rate of $4/7 \approx 0.571$ while still correcting any single-bit error.

The Hamming Bound

How efficient can a single-error-correcting code be? The Hamming bound (also called the sphere-packing bound) gives a limit. A code with $n$-bit codewords that corrects $t$ errors must satisfy:

For $t = 1$: $2^k \cdot (1 + n) \leq 2^n$, which gives $k \leq n - \log_2(1 + n)$. When $n = 2^r - 1$, we get $k \leq 2^r - 1 - r$, which is exactly the number of data bits in a Hamming code. In other words, Hamming codes are perfect codes - they achieve the Hamming bound with equality. Every possible received word is within Hamming distance 1 of exactly one codeword.

Interactive Parity Check Encoder/Decoder

Use the widget above to explore the Hamming(7,4) code. Enter four data bits to see the encoded 7-bit codeword. Then flip any single bit in the received word to watch syndrome decoding identify and correct the error.

Beyond Single-Error Correction

Hamming codes only correct single-bit errors. For applications requiring more protection, the coding theory toolbox includes:

• Extended Hamming codes: Add an overall parity bit to get distance 4, enabling single-error correction and double-error detection (SECDED). The extended Hamming(8,4) code is used in ECC memory.
• BCH codes: A generalization of Hamming codes that can correct multiple errors.
• Reed-Solomon codes: Work over larger fields; used in CDs, DVDs, QR codes, and deep-space communication.
• LDPC and Turbo codes: Modern codes approaching Shannon's theoretical limit, used in 5G cellular and Wi-Fi.

16.3 The Limits of Classical EC

Is there a fundamental limit to how well error correction can perform? The answer, given by Claude Shannon in 1948, is one of the most profound results in information theory.

The Binary Symmetric Channel

The simplest noise model is the binary symmetric channel (BSC): each bit is flipped independently with probability $p$ (the crossover probability):

When $p = 0$ the channel is perfect; when $p = 1/2$ the output is independent of the input. For $0 < p < 1/2$, some information survives the noise and error correction helps.

Channel Capacity

Shannon defined the capacity of a channel as the maximum rate at which information can be transmitted with arbitrarily low error probability. For the binary symmetric channel, the capacity is:

where $H(p)$ is the binary entropy function:

Let us unpack this. The theorem has two parts:

1. Achievability (positive part): If you want to send data at any rate below capacity, you can do it reliably. There exist codes (possibly with very long block lengths) that make the error probability as small as you wish.
2. Converse (negative part): If you try to send data at any rate above capacity, you cannot avoid errors. No code, no matter how clever, can achieve reliable communication above the capacity limit.

Numerical Examples

For a BSC with $p = 0.01$ (1% error rate): $H(0.01) \approx 0.081$, so $C \approx 0.919$. Even with a 1% error rate, we can reliably transmit at up to 91.9% of the raw channel rate. The Hamming(7,4) code at rate $4/7 \approx 0.571$ is reliable but far from optimal. Modern LDPC codes operate within a fraction of a percent of Shannon's limit.

At $p = 0.5$, every output bit is equally likely to be 0 or 1 regardless of the input, so the channel carries zero useful information.

Shannon's Theorem Is Existential

Shannon's theorem proves that good codes exist, but does not tell you how to find them. His proof used random coding: pick a code at random and, with high probability, it will be good. The quest for explicit, efficiently decodable codes near Shannon's limit drove decades of research - from Hamming (1950) through turbo codes (1993) and LDPC codes (1990s). Modern polar codes (Arikan, 2009) provably achieve capacity, and LDPC codes in 5G standards operate within 0.1 dB of the Shannon limit.

Why This Matters for Quantum EC

Shannon's framework carries over to the quantum setting, but with key complications:

• Richer error models. Classical bits only flip. Qubits suffer bit flips (X), phase flips (Z), or both (Y), plus continuous rotations.
• No-cloning forbids copying. The repetition code works by copying bits. Quantum mechanics forbids copying unknown states. Quantum EC must protect information without duplicating it - achievable through entanglement.
• Syndrome decoding survives. Stabilizer codes - the quantum generalization of linear codes - use parity measurements that extract syndrome information without collapsing the quantum state.

Classical-to-Quantum Dictionary

The classical vocabulary we built in this chapter maps directly to quantum error correction: