Question 3 of 5: Error-control coding

Question 3: Error-control coding (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A binary linear block code specified by the $4\times 7$ generator matrix printed in the question, so $k=4$ message bits map to $n=7$ code bits and the code has $2^{4}=16$ codewords. Part (d) instead supplies only a minimum distance, $d_{\min}=9$.

Find. (a) the parity-check matrix, (b) the minimum Hamming distance, (c) a worked demonstration of single-error correction, and (d) the correcting and detecting capability implied by $d_{\min}=9$.

Approach. Recognise the generator matrix as systematic, which turns part (a) into a transposition; obtain the minimum distance from the codeword weights and cross-check it against the columns of $\mathbf{H}$; then encode one message, inject one error, and let the syndrome locate it. Part (d) applies the standard distance bounds.

1. Part (a) — split the generator matrix into its systematic blocks. The first four columns are the identity, so $\mathbf{G} = [\,\mathbf{I}_{4}\ |\ \mathbf{P}\,]$ with $$\mathbf{P} = \begin{bmatrix}1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1\end{bmatrix}.$$ The code is therefore systematic: the first four bits of every codeword are the message itself and the last three are parity checks.
2. Write down the parity-check matrix. For a systematic generator the matching parity-check matrix is $\mathbf{H} = [\,\mathbf{P}^{T}\ |\ \mathbf{I}_{3}\,]$, giving $$\boxed{\mathbf{H} = \begin{bmatrix}1 & 1 & 1 & 0 & 1 & 0 & 0\\1 & 1 & 0 & 1 & 0 & 1 & 0\\1 & 0 & 1 & 1 & 0 & 0 & 1\end{bmatrix}}$$which satisfies $\mathbf{G}\mathbf{H}^{T}=\mathbf{0}$ over GF(2) — the check that every codeword passes every parity equation. Verifying that product is the cheapest possible guard against a transposition slip, and it is worth doing in the exam.
3. Part (b) — the minimum distance is the minimum nonzero codeword weight. For a linear code the difference of two codewords is itself a codeword, so $$d_{\min} = \min_{\mathbf{c}\neq\mathbf{0}} w(\mathbf{c}),$$ and only 15 weights need checking rather than all 120 pairs. Enumerating the sixteen codewords gives seven of weight 3, seven of weight 4 and one of weight 7, hence $$\boxed{d_{\min} = 3}.$$
4. Cross-check on the columns of $\mathbf{H}$. An equivalent statement is that $d_{\min}$ is the smallest number of columns of $\mathbf{H}$ that sum to zero. Here all seven columns are distinct and none is zero, so no single column and no pair can sum to zero, ruling out $d_{\min}=1$ or 2; and triples do exist, for example columns 1, 2 and 3. Since the columns are exactly the seven nonzero binary triples, this is the (7,4) Hamming code, whose minimum distance is 3 by construction — a reassuring agreement with the weight enumeration.
5. Part (c) — encode a message. Take $\mathbf{m} = 1011$. Then $\mathbf{c} = \mathbf{m}\mathbf{G}$ is the sum over GF(2) of rows 1, 3 and 4 of $\mathbf{G}$: $$\mathbf{c} = 1000111 \oplus 0010101 \oplus 0001011 = 1011001,$$ and $\mathbf{H}\mathbf{c}^{T}=\mathbf{0}$ confirms it is a legitimate codeword. The first four bits are the message, as systematic form requires.
6. Inject a single error and form the syndrome. Suppose bit 5 is inverted in transit, so the received vector is $\mathbf{r} = \mathbf{c}\oplus\mathbf{e} = 1011101$ with $\mathbf{e}=0000100$. The decoder computes $$\mathbf{s} = \mathbf{H}\mathbf{r}^{T} = \mathbf{H}(\mathbf{c}\oplus\mathbf{e})^{T} = \mathbf{H}\mathbf{e}^{T},$$ because the codeword part contributes nothing. Evaluating row by row gives $$\boxed{\mathbf{s} = (1,\,0,\,0)^{T}}.$$
7. Locate and correct the error. The syndrome equals column 5 of $\mathbf{H}$, and since $\mathbf{H}\mathbf{e}^{T}$ is just the sum of the columns indexed by the error positions, a syndrome matching one column means one error in that position. Inverting bit 5 of $\mathbf{r}$ restores $1011001$ and the recovered message is the first four bits, $\mathbf{\hat{m}} = 1011$ — the message that was sent. The same works for every position: the seven columns are distinct, so the seven single-error syndromes are distinct, and with the all-zero syndrome for “no error” the decoder's lookup table has exactly $2^{3}=8$ entries. That $8 = 1+7$ is why the Hamming code is called perfect: the syndrome space is used up exactly, with nothing left over for double errors.
8. Part (d) — apply the distance bounds. A code corrects up to $$t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor = \left\lfloor \frac{9-1}{2} \right\rfloor = \boxed{4\ \text{errors}},$$ because spheres of radius 4 about distinct codewords 9 apart cannot overlap. Used purely for detection it catches $$s = d_{\min}-1 = \boxed{8\ \text{errors}},$$ since no error pattern of weight 8 or less can turn one codeword into another. These are alternative operating modes, not simultaneous guarantees: to correct $t$ while detecting $s\gt t$ the requirement is $t+s+1\le d_{\min}$, so this code could, for instance, correct 2 errors while still detecting 6.