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\).
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)\).
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 |