Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 3K (Coding and Cryptography)

For a binary block code, $n$ is the common length of its codewords, $m=|C|$ is the number of codewords, andis its minimum Hamming distance.

The parity extension isEvery extended word has even Hamming weight. The distance between two words increases by one exactly when their original distance is odd, so

Fix a coordinate, say the last one. The punctured code isDeleting one coordinate lowers each pairwise distance by at most one. Thus, when $d\ge 2$, no two words merge andIn guaranteed-distance notation this is recorded as an $[n-1,m,d-1]$ code. If $d=1$, puncturing a coordinate on which a distance-one pair differs can merge words, so its exact size must then be stated separately.

For a chosen coordinate and symbol $\epsilon \in \{0,1\}$, the shortened code retains the words having that symbol in the chosen coordinate and then deletes that coordinate. For the last coordinate,At least one of the two coordinate fibres contains at least $\lceil m/2\rceil$ words. Choose that fibre and, if necessary, discard surplus words. Because all retained words agree in the deleted coordinate, their mutual distances do not change. Hence one can always obtainWithout discarding words, its size is that of the chosen fibre and its minimum distance is at least $d$.

For the final calculation, the given code is the whole space ${\mathbb{F}}_2^3$, so its parity extension is the length-four even-weight binary code. In a binary symmetric channel, parity fails to notice a nonzero error exactly when an even number of bits flips. The possible error weights are therefore two and four. Their total probability isThis excludes the weight-zero event, since it is not an undetected error.