Coding Theory¶
Coding theory answers a very practical question: when you send a message and some bits get flipped by noise, how can the receiver notice — and even fix — the errors? The trick is to not use all possible words. If only certain "code words" are legal, then a corrupted word usually isn't legal, which is the flag that something went wrong.
The course studies binary linear codes, and their charm is a double identity: a linear code is at once a group-theory object (a subgroup) and a linear-algebra object (a subspace). Every exam problem leans on that double identity, so keep both hats handy.
Linear codes¶
A binary code of length \(n\) is just a chosen set of words in \((\mathbb{Z}_2)^n\) — strings of \(n\) bits. It is linear when it's a subgroup of \((\mathbb{Z}_2)^n\); equivalently (same thing, linear-algebra hat) a linear subspace. Concretely that means: it contains the all-zeros word, and the sum of any two code words is again a code word.
Size of a linear code
A linear code of dimension \(k\) has
In particular, the size of a linear code is always a power of 2.
Why a power of 2 — and why closure under addition is the only thing to check. In \(\mathbb{Z}_2\), addition is XOR, and every word is its own inverse (\(x + x = \mathbf{0}\)), so "closed under inverses" comes free. That leaves closure under addition, and a set of bit-strings closed under XOR is spanned by some \(k\) independent words — giving exactly \(2^k\) combinations.
Exam (May 2024, Problem 5a): why is this code not linear?
Count: \(\lvert C \rvert = 6\). But a linear code must have \(2^k\) elements, and \(6\) is not a power of \(2\). So \(C\) cannot be linear. One line, no arithmetic.
(You could instead hunt for two code words whose XOR escapes \(C\) — but the size check is faster and always available. Reach for it first.)
Making a code linear¶
To grow a non-linear \(C\) into a linear \(C'\), you add the "missing" sums until it's closed. The systematic route, using the subspace hat: find a spanning set inside \(C\), take the whole subspace it generates, and confirm the result contains \(C\).
Exam (May 2024, Problem 5b): completing \(C\) to a linear code
Label the words \(v_0 = 0000000000\), \(v_1 = 0101010101\), \(v_2 = 1010101010\), \(v_3 = 1111111111\), \(v_4 = 0000011111\), \(v_5 = 1111100000\).
The sums that leak out of \(C\) are \(v_1 + v_4\) and \(v_2 + v_4\), so add them back:
Showing \(C'\) is linear — this is where the marks live, and the argument is slick. Let \(W\) be the subspace generated by \(v_1, v_2, v_5\). We show \(C' = W\), which makes \(C'\) a subspace (hence linear) automatically. The proof is a size sandwich:
- \(C' \subseteq W\): check each word of \(C'\) is a combination of \(v_1, v_2, v_5\). Indeed \(v_0 = 0\cdot v_1\), \(v_3 = v_1 + v_2\), \(v_4 = v_3 + v_5 = v_1 + v_2 + v_5\), and \(w, w'\) are sums of these. So all \(8\) words of \(C'\) live in \(W\).
- \(\lvert W \rvert = 8\): \(v_1, v_2, v_5\) are linearly independent (check directly), so \(\dim W = 3\) and \(\lvert W \rvert = 2^3 = 8\).
- Conclude: \(C' \subseteq W\), both have \(8\) elements, so \(C' = W\). A subspace — done. \(\square\)
The reusable move: rather than grind through all \(8 \times 8\) sums to verify closure, trap \(C'\) inside a subspace of the same size and conclude equality by counting. Sandwiching by cardinality beats brute force.
Hamming distance¶
The Hamming distance \(\delta(x, y)\) between two words is the number of positions where they differ — literally, how many bit-flips turn one into the other. A code's minimum distance is the smallest distance between any two distinct code words:
This one number controls everything about error handling: the further apart the code words are, the more corruption you can survive without confusing one word for another.
The shortcut that makes linear codes easy
For a linear code, the minimum distance equals the minimum weight — the fewest \(1\)s in any nonzero code word:
Why: the distance \(\delta(x, y)\) counts the differing positions, which is exactly the number of \(1\)s in \(x + y\) — that is, \(\operatorname{wt}(x+y)\). And for a linear code \(x + y\) is another code word. So every pairwise distance is the weight of some code word, and minimising distance = minimising weight. This turns \(\binom{\lvert C\rvert}{2}\) pairwise comparisons into just \(\lvert C \rvert - 1\) weight counts. Only valid if the code is linear — check that first.
Detection and correction¶
Now the payoff: how many errors can a code catch, and how many can it repair?
The two thresholds
A code with minimum distance \(\delta\) can:
- detect up to \(\delta - 1\) errors, and
- correct up to \(t\) errors, where \(\delta \geq 2t + 1\) — i.e. \(t = \left\lfloor \frac{\delta - 1}{2} \right\rfloor\).
The geometry behind both numbers. Picture the code words as points, each pair at least \(\delta\) apart. Errors nudge a received word away from the true code word:
- Detection. With fewer than \(\delta\) flips you can't land exactly on a different code word (they're \(\delta\) apart), so a corrupted word is recognisably illegal — you detect up to \(\delta - 1\) errors.
- Correction. To repair, snap the received word to the nearest code word. That's only unambiguous if the radius-\(t\) "balls" around code words don't overlap — which needs \(\delta \geq 2t + 1\) (two balls of radius \(t\) need a gap of more than \(2t\) between centres).
Exam (May 2024, Problem 5c–d): distance and decoding
(c) Minimum distance and error capacity. For the linear \(C'\), the lightest nonzero word has weight \(5\), so \(\delta(C') = 5\). For the original (non-linear) \(C\), use a two-sided squeeze:
- \(C \subset C'\), so every distance in \(C\) also occurs in \(C'\); hence \(\delta(C) \geq \delta(C') = 5\).
- And \(\delta(v_0, v_1) = 5\) is achieved by an actual pair in \(C\); hence \(\delta(C) \leq 5\).
Together \(\delta(C) = 5\). So both codes detect up to \(\delta - 1 = 4\) errors and correct up to \(t = \lfloor 4/2 \rfloor = 2\).
(The squeeze — lower bound from the linear superset, upper bound from one explicit pair — lets you borrow the linear code's easy minimum-weight computation to pin down the non-linear code's distance. A tidy trick worth remembering.)
(d) Decode a received word. You receive \(x = 0101011111\) (sent using \(C\)). Compute \(\delta(x, v)\) to each code word; the nearest is \(v_4 = 0000011111\) at distance \(2\). Since \(C\) corrects up to \(2\) errors, this is within range: the word contains at least \(2\) errors and you correct it to \(v_4 = 0000011111\).
The sphere-packing bound¶
Correction works by putting a radius-\(t\) ball around each code word and snapping a received word to whichever ball it lands in. For that to be unambiguous the balls must be disjoint — and disjoint balls can't overcrowd the space. Counting how many words a ball contains turns this into a hard limit on how many code words can coexist.
Sphere-packing (Hamming) bound
A binary code of length \(n\) correcting \(t\) errors — so its balls of radius \(t\) are disjoint — has at most
The denominator is the number of words within distance \(t\) of a fixed word: \(\binom{n}{i}\) ways to flip exactly \(i\) of the \(n\) bits, summed over \(i = 0, \dots, t\).
Why. There are \(2^n\) words in total. Each of the \(\lvert C\rvert\) disjoint balls uses up \(\sum_{i=0}^{t}\binom{n}{i}\) of them, and disjoint sets can't total more than the whole space — so \(\lvert C\rvert \cdot \sum_{i=0}^{t}\binom{n}{i} \leq 2^n\). A code meeting the bound with equality wastes nothing: every word is in exactly one ball. Such a code is called perfect — the balls tile the whole space with no gaps.
Worked: the Hamming \([7,4]\) code is perfect
The Hamming code has \(n = 7\), \(\lvert C\rvert = 2^4 = 16\), and corrects \(t = 1\) error. Check the bound: a radius-\(1\) ball holds \(\binom{7}{0} + \binom{7}{1} = 1 + 7 = 8\) words, so
Equality — the \(16\) balls tile all \(128\) words of \((\mathbb{Z}_2)^7\) exactly. Every received word is within distance \(1\) of precisely one code word, so single-error correction never hits an ambiguous case. That is what "perfect" means, made concrete.
Check matrices¶
A check matrix for \(C\) is a matrix \(A\) such that the code is exactly the set of words \(A\) kills:
This is a compact way to specify a code, and it comes with a free bonus: since the kernel of a linear map is always a subspace, presenting \(C\) as \(\ker A\) is itself a proof that \(C\) is linear. Two practical consequences: testing whether a word is a code word is one matrix–vector product (\(Ax \stackrel{?}{=} 0\)), and the dimension drops out of rank–nullity, \(k = n - \operatorname{rank}(A)\).
Generator matrices and encoding¶
A check matrix tests membership; a generator matrix produces code words. It's a \(k \times n\) matrix \(G\) whose rows are a basis of \(C\), so every code word is a combination of them — encoding a \(k\)-bit message \(\mathbf{m}\) is one matrix product:
As \(\mathbf{m}\) ranges over all \(2^k\) messages, \(\mathbf{c}\) ranges over all \(2^k\) code words. The two matrices are two views of the same code and are linked by
— every generated code word passes the check, which is exactly the statement that the rows of \(G\) lie in \(\ker A\). A systematic generator \(G = [\,I_k \mid P\,]\) is the convenient form: the first \(k\) bits of each code word are the message itself (copied by \(I_k\)) and the last \(n-k\) are parity checks (computed by \(P\)). Decoding then just reads the message off the front.
Syndrome decoding¶
For a code given by a check matrix, there's a decoding method far smarter than comparing the received word against all \(2^k\) code words. Given a received word \(\mathbf{r}\), compute its syndrome:
- If \(\mathbf{s} = \mathbf{0}\), then \(\mathbf{r}\) is a valid code word — accept it.
- If \(\mathbf{s} \neq \mathbf{0}\), an error occurred. Crucially, the syndrome depends only on the error pattern, not on which code word was sent: if \(\mathbf{r} = \mathbf{c} + \mathbf{e}\) then \(A\mathbf{r}^{\top} = A\mathbf{c}^{\top} + A\mathbf{e}^{\top} = A\mathbf{e}^{\top}\), since code words have zero syndrome. So the syndrome fingerprints the error, and you correct by finding the lightest \(\mathbf{e}\) with that syndrome.
Why this is the elegant case of Hamming codes
Arrange the check matrix so its columns are the binary numbers \(1\) through \(n\) in order. Then the syndrome of a single-bit error in position \(p\) is exactly column \(p\) — i.e. the binary numeral for \(p\). The syndrome literally spells out the position of the error. No search: read the syndrome as a number, flip that bit.
Worked: single-error correction with the Hamming \([7,4]\) code
Take the check matrix whose columns are \(1,2,\dots,7\) in binary (top row = the \(4\)s bit):
Suppose you receive \(\mathbf{r} = 1001101\) (bits \(r_1 \dots r_7\)). Compute the syndrome — each row of \(A\) picks out the positions with a \(1\) and sums them mod \(2\):
So \(\mathbf{s} = (s_1,s_2,s_3) = (1,1,1)\), which read as a binary numeral (top row the \(4\)s bit) is \(111 = 7\). The error is in position \(7\). Flip \(r_7\) from \(1\) to \(0\):
Check the correction: the new syndrome is \((0,0,0)\), so \(\mathbf{c}\) is a genuine code word. One matrix product located and fixed the error — no comparison against the \(16\) code words needed. That "the syndrome names the broken bit" is the whole appeal of the construction.
Quick reference¶
| Question | Fastest route |
|---|---|
| Is \(C\) linear? | Is \(\lvert C \rvert\) a power of \(2\)? If not, done. If yes, check closure under \(+\) (XOR). |
| What is \(\delta(C)\)? | Linear: minimum weight of a nonzero word. Non-linear: all pairwise distances. |
| How many errors detected? | \(\delta - 1\) |
| How many corrected? | \(\lfloor (\delta - 1)/2 \rfloor\) |
| Decode a received word \(x\) | Snap to the nearest code word in Hamming distance |
| Show \(C\) is linear, given \(A\) | \(C = \ker A\) is a subspace, so linear |