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 of length $n = 7$ defined by the $3\times 7$ parity-check matrix $H$ above, over $\mathrm{GF}(2)$ (addition is XOR). Since $H$ has $n - k = 3$ rows, the code carries $k = 4$ information bits, giving a $(7,4)$ code and 16 codewords. The information sequence to be encoded in part (b) is $\mathbf{u} = 0\,1\,0\,1$.

Find. (a) the generator matrix $G$; (b) the codeword for $\mathbf{u} = 0101$; (c) a worked single-error correction; (d) whether two errors can be corrected, and whether they can be detected.

Approach. Recognise that the last three columns of $H$ form an identity block, so $H$ is already in systematic form $H = [\,P^{T} \mid I_3\,]$; the matching generator is then $G = [\,I_4 \mid P\,]$, which is verified by checking $GH^{T} = 0$. Encode by $\mathbf{c} = \mathbf{u}G$, decode by computing the syndrome $\mathbf{s} = H\mathbf{r}^{T}$ and matching it to a column of $H$, and settle the capability question from the minimum distance.

1. Part (a) — Identify the systematic partition of $H$. The right-hand $3\times 3$ block of $H$ is the identity, so writing $H = [\,P^{T}\mid I_3\,]$ gives $$P^{T} = \begin{bmatrix} 1&1&1&0\\ 1&1&0&1\\ 1&0&1&1 \end{bmatrix} \quad\Longrightarrow\quad P = \begin{bmatrix} 1&1&1\\ 1&1&0\\ 1&0&1\\ 0&1&1 \end{bmatrix}.$$ The first four positions of a codeword are therefore the message bits and the last three are parity bits.
2. Assemble the generator matrix. For a systematic code the generator is $G = [\,I_k \mid P\,]$ with $k = 4$: $$\boxed{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}}$$ Row $i$ of $G$ is the codeword generated by the message with a single 1 in position $i$, which is why the encoder is just a selection-and-XOR of rows.
3. Verify the pair. The defining requirement is $GH^{T} = 0$ over $\mathrm{GF}(2)$, and with the systematic partition this reduces to $P + P = 0$, which holds identically because addition is modulo 2. Checking one row explicitly — row 1, $(1000111)$, against the three rows of $H$ — gives $1+1+1 = 0$, $1+1+0 = 0$ and $1+1+0+1 = 0$ as required, and the same holds for every row.
4. Part (b) — Encode the information sequence. The codeword is $\mathbf{c} = \mathbf{u}G$, i.e. the modulo-2 sum of the rows of $G$ selected by the 1s of $\mathbf{u} = 0101$, namely rows 2 and 4: $$\begin{aligned} \text{row 2:}&\quad 0\;1\;0\;0\;1\;1\;0\\ \text{row 4:}&\quad 0\;0\;0\;1\;0\;1\;1\\ \hline \text{XOR:}&\quad 0\;1\;0\;1\;1\;0\;1 \end{aligned}$$ $$\boxed{\mathbf{c} = 0\,1\,0\,1\,1\,0\,1}$$ The first four bits reproduce the message (systematic form) and the parity bits are $101$. As a check, $H\mathbf{c}^{T} = (0,0,0)^{T}$.
5. Part (c) — Establish why single errors are correctable at all. The seven columns of $H$ are $$(111)^{T},\,(110)^{T},\,(101)^{T},\,(011)^{T},\,(100)^{T},\,(010)^{T},\,(001)^{T},$$ which are the seven distinct non-zero 3-bit patterns — each appears exactly once. This makes the code the $(7,4)$ Hamming code: since a single error in position $i$ produces the syndrome $\mathbf{s} = H\mathbf{e}^{T} = $ column $i$ of $H$, and no two columns are equal or zero, the syndrome names the error position uniquely.
6. Work the example through. Transmit the codeword from part (b) and suppose the channel flips bit 3: $$\mathbf{c} = 0\,1\,0\,1\,1\,0\,1 \quad\longrightarrow\quad \mathbf{r} = 0\,1\,1\,1\,1\,0\,1.$$ Compute the syndrome row by row (each row of $H$ selects positions and XORs the received bits it selects):

   Row of $H$	Positions selected	Received bits	Syndrome bit
   $1\,1\,1\,0\,1\,0\,0$	1, 2, 3, 5	0, 1, 1, 1	$0\oplus1\oplus1\oplus1 = 1$
   $1\,1\,0\,1\,0\,1\,0$	1, 2, 4, 6	0, 1, 1, 0	$0\oplus1\oplus1\oplus0 = 0$
   $1\,0\,1\,1\,0\,0\,1$	1, 3, 4, 7	0, 1, 1, 1	$0\oplus1\oplus1\oplus1 = 1$

   so $\mathbf{s} = (1,0,1)^{T}$. This is non-zero, so an error is present; matching it against the columns of $H$ identifies it as column 3. Flipping bit 3 of $\mathbf{r}$ restores $0\,1\,0\,1\,1\,0\,1$ and the recovered message is the first four bits, $0101$ — exactly what was sent. Repeating the exercise for any of the other six positions gives that position's column as the syndrome, so all seven single-error patterns are corrected.
7. Part (d) — Establish the minimum distance. The code is linear, so the minimum distance equals the smallest weight of a non-zero codeword. Enumerating the 15 non-zero codewords gives a minimum weight of 3 (for example row 4 of $G$, $0001011$), which is also what the column structure predicts: no two columns of $H$ sum to zero, but there exist three columns that do, so $$\boxed{d_{\min} = 3}$$ The standard capability formulas then give $t = \lfloor (d_{\min}-1)/2 \rfloor = 1$ correctable error and up to $d_{\min}-1 = 2$ detectable errors.

Part (d), in words. No, the code cannot correct two errors: correcting $t$ errors requires $d_{\min}\ge 2t+1$, i.e. $d_{\min}\ge 5$ for $t = 2$, whereas this code has $d_{\min} = 3$. Concretely, flipping bits 1 and 2 of the codeword $0101101$ gives the syndrome $(0,0,1)^{T}$, which is column 7 — so a single-error decoder would confidently “correct” bit 7 and hand up a third error rather than a repair. It can, however, detect two errors, because $d_{\min} = 3 > 2$ means no double-error pattern can turn one codeword into another and the syndrome is therefore guaranteed non-zero; every one of the 21 double-error patterns produces a non-zero syndrome. The catch is that the two capabilities cannot be used simultaneously: a receiver operated in pure detection mode (flag and request a retransmission whenever $\mathbf{s}\neq 0$) catches all single and double errors, whereas a receiver operated in correction mode spends the distance on correcting singles and silently mis-corrects doubles.