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 $3\times 7$ parity-check matrix

All arithmetic is over GF(2): addition is exclusive-OR and $1+1 = 0$.

Find. The generator matrix, the codeword carrying the message 1101, a worked single-error correction, and the minimum distance with its detection and correction consequences.

Approach. Recognise that H is already in systematic form $[\mathbf{P}^{T}\,|\,\mathbf{I}_3]$, from which $\mathbf{G} = [\mathbf{I}_4\,|\,\mathbf{P}]$ follows immediately; then encode, decode a deliberately corrupted word by syndrome lookup, and determine $d_{\min}$ from the column structure.

1. Part (a) — identify the systematic structure of H. The right-hand $3\times 3$ block of H is the identity, so H has the standard systematic form $$\mathbf{H} = [\,\mathbf{P}^{T} \mid \mathbf{I}_{3}\,], \qquad \mathbf{P}^{T} = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix}.$$ The code therefore has block length $n = 7$ and $n - k = 3$ parity checks, so $k = 4$ information bits: it is a (7,4) code.
2. Write down the generator matrix. For a systematic code the generator and parity-check matrices are related by $\mathbf{G} = [\,\mathbf{I}_{k} \mid \mathbf{P}\,]$, where P is the transpose of the left block of H. Transposing, $$\mathbf{P} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}, \qquad \boxed{\ \mathbf{G} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix}\ }$$ The check that this is right is $\mathbf{G}\mathbf{H}^{T} = \mathbf{0}$ over GF(2), which holds because $\mathbf{P}\cdot\mathbf{I} + \mathbf{I}\cdot\mathbf{P} = 2\mathbf{P} = \mathbf{0}$ in binary arithmetic; each of the four rows of G is itself a codeword, and each satisfies all three parity checks.
3. Part (b) — encode the message 1101. With $\mathbf{m} = [1\ 1\ 0\ 1]$ the codeword is $\mathbf{c} = \mathbf{m}\mathbf{G}$, which because G is systematic means the first four bits are the message itself and the last three are parity. Adding rows 1, 2 and 4 of G modulo 2, $$\mathbf{c} = [1\,0\,0\,0\,1\,1\,1] \oplus [0\,1\,0\,0\,1\,1\,0] \oplus [0\,0\,0\,1\,0\,1\,1],$$ whose parity section is $111 \oplus 110 \oplus 011 = 010$. Hence $$\boxed{\mathbf{c} = 1\ 1\ 0\ 1\ 0\ 1\ 0}$$ Verifying, $\mathbf{H}\mathbf{c}^{T} = [0\ 0\ 0]^{T}$: the first check sums bits 1, 2, 3, 5 $= 1+1+0+0 = 0$; the second sums bits 1, 2, 4, 6 $= 1+1+1+1 = 0$; the third sums bits 1, 3, 4, 7 $= 1+0+1+0 = 0$.
4. Part (c) — corrupt one bit and recover it by syndrome decoding. Suppose the codeword above is transmitted and the channel inverts bit 3, so the receiver observes $$\mathbf{r} = 1\ 1\ \mathbf{1}\ 1\ 0\ 1\ 0 \qquad (\text{error pattern } \mathbf{e} = 0010000).$$ The decoder computes the syndrome $\mathbf{s} = \mathbf{H}\mathbf{r}^{T}$. Because $\mathbf{r} = \mathbf{c} \oplus \mathbf{e}$ and $\mathbf{H}\mathbf{c}^{T} = \mathbf{0}$, the syndrome depends only on the error: $\mathbf{s} = \mathbf{H}\mathbf{e}^{T}$. Evaluating the three checks on r, $$s_1 = r_1 + r_2 + r_3 + r_5 = 1+1+1+0 = 1,$$ $$s_2 = r_1 + r_2 + r_4 + r_6 = 1+1+1+1 = 0,$$ $$s_3 = r_1 + r_3 + r_4 + r_7 = 1+1+1+0 = 1,$$ so $\mathbf{s} = [1\ 0\ 1]^{T}$.
5. Match the syndrome to a column of H and correct. A single error in position $j$ makes $\mathbf{H}\mathbf{e}^{T}$ equal to the $j$-th column of H. Column 3 of H is $[1\ 0\ 1]^{T}$, which is exactly the syndrome obtained, and no other column matches because all seven columns are distinct. The decoder therefore inverts bit 3: $$\boxed{\hat{\mathbf{c}} = \mathbf{r} \oplus 0010000 = 1\ 1\ 0\ 1\ 0\ 1\ 0}$$ which is the transmitted codeword, and stripping the parity section returns the original message 1101. The same procedure works for an error in any of the seven positions: the seven columns of H are precisely the seven distinct non-zero binary triples, so every single-error syndrome is unique and non-zero, while a zero syndrome means no detectable error occurred.
6. Part (d) — determine the minimum Hamming distance. For a linear code the minimum distance equals the smallest non-zero codeword weight, and equivalently it is the smallest number of columns of H that sum to zero. No single column is zero, and no two columns are equal, so no set of one or two columns sums to zero; but three do, for example columns 1, 2 and 7, since $[1\,1\,1]^{T} \oplus [1\,1\,0]^{T} = [0\,0\,1]^{T}$. Hence $$\boxed{d_{\min} = 3}$$ Enumerating all sixteen codewords confirms it: the lightest non-zero codewords have weight 3 (for instance the message 0001 encodes to 0001011).
7. State what $d_{\min} = 3$ buys. The standard guarantees follow directly: $$\text{detect up to } d_{\min}-1 = 2 \text{ errors}, \qquad \text{correct up to } \left\lfloor \frac{d_{\min}-1}{2}\right\rfloor = 1 \text{ error}.$$ A decoder must choose between these — used purely for detection the code catches every single and double error, while used for correction it corrects every single error but will mis-correct a double error to the wrong codeword. This is the (7,4) Hamming code, and it is a perfect code: the $2^{3} = 8$ possible syndromes are exactly accounted for by the all-zero pattern plus the $n = 7$ single-error patterns, so the Hamming bound $2^{n-k} \ge 1 + n$ is met with equality and no syndrome is wasted.

Final Results