Question 5 of 5: Error-Control Coding

Question 5: 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.

(a) Block codes versus convolutional codes (5 marks)

Both families add controlled redundancy so that a receiver can detect or correct channel errors, but they differ fundamentally in whether the encoder has memory. A block code partitions the information stream into independent blocks of $k$ bits and maps each block, on its own, to an $n$-bit codeword through a fixed linear transformation $\mathbf{c} = \mathbf{m}G$. The encoder is memoryless: the codeword depends only on the current block, blocks may be encoded and decoded in any order, and the code is fully described by its generator and parity-check matrices. Decoding exploits algebraic structure — syndrome lookup for a Hamming code, or the finite-field algebra of Berlekamp–Massey for a Reed–Solomon or BCH code — and typically works on hard decisions. Familiar examples are the Hamming, cyclic redundancy check, BCH, Reed–Solomon and low-density parity-check codes.

A convolutional code, by contrast, processes the information as a continuous stream through a shift register of some constraint length $K$, so that each output bit is a modulo-2 combination of the current input bit and the previous $K-1$ inputs. The encoder is a finite-state machine with memory, the codeword is unbounded in length rather than blocked, and there is no fixed generator matrix in the block-code sense — only a set of generator polynomials and a rate $k/n$ (commonly 1/2 or 1/3). Decoding is not algebraic but a maximum-likelihood search over the encoder’s trellis, performed by the Viterbi algorithm, whose complexity grows as $2^{K-1}$ rather than with the length of the message. Two consequences matter in practice. First, convolutional decoders accept soft channel information naturally, and typically buy 2 to 3 dB over hard-decision decoding, which is why they dominated satellite and mobile links. Second, because errors propagate through the register span they occur in bursts at the decoder output, which is why convolutional codes are usually concatenated with an interleaver and an outer block code — the classic Reed–Solomon plus convolutional arrangement of deep-space and digital-broadcast standards. Block codes, being independent block to block, contain the damage of a burst to the block that suffered it but need the burst to be spread by interleaving in the first place.

(b) Minimum Hamming distance and error-correcting capability (5 marks)

The Hamming distance $d(\mathbf{x}, \mathbf{y})$ between two equal-length binary words is the number of bit positions in which they differ — equivalently the Hamming weight of their modulo-2 sum. The minimum Hamming distance $d_{\min}$ of a code is the smallest such distance taken over all distinct pairs of codewords:

For a linear code the definition simplifies usefully: since the sum of two codewords is itself a codeword, $d_{\min}$ equals the smallest Hamming weight among the non-zero codewords, so it can be found by examining $2^k - 1$ words rather than all pairs. It can also be read off the parity-check matrix directly, as the smallest number of columns of $H$ that sum to zero.

The connection to error correction is geometric. Think of the $2^n$ possible received words as points in a cube, with the codewords a sparse subset separated by at least $d_{\min}$ steps. A pattern of $t$ bit errors moves the received word $t$ steps away from the transmitted codeword. Nearest-codeword decoding will still return the right answer provided the corrupted word remains strictly closer to the transmitted codeword than to any other, and non-overlapping spheres of radius $t$ around every codeword require $d_{\min} \ge 2t + 1$. Hence a code can correct

or, if both capabilities are wanted simultaneously, correct $t$ and detect $d$ errors whenever $d_{\min} \ge t + d + 1$. For the (7,4) Hamming code used below, $d_{\min} = 3$, giving $t = \lfloor 2/2 \rfloor = 1$ correctable error and up to 2 detectable errors — which is exactly why it is described as a single-error-correcting, double-error-detecting code when an overall parity bit is appended to make $d_{\min} = 4$.

(c) The generator matrix (5 marks)

Given (stated assumption). The standard systematic parity-check matrix of the binary (7,4) Hamming code, with the three parity columns collected on the right:

Find. The $4 \times 7$ generator matrix $G$ whose rows span the null space of $H$, i.e. the matrix satisfying $GH^{T} = \mathbf{0}$ over GF(2).

Approach. Read the parity submatrix off $H$, transpose it, and place it alongside a $4 \times 4$ identity so that the code is systematic and every codeword automatically satisfies the parity checks.

1. Part (c) — state the systematic relationship between $H$ and $G$. A codeword must satisfy $H\mathbf{c}^{T} = \mathbf{0}$, and codewords are generated as $\mathbf{c} = \mathbf{m}G$; combining the two requires $$G H^{T} = \mathbf{0} \pmod 2 .$$ When $H$ is written in the systematic form $[\,A \mid I_{n-k}\,]$ with $A$ of size $3 \times 4$, the matrix $$G = [\,I_k \mid A^{T}\,]$$ satisfies this identically, because $GH^{T} = I_k A^{T} + A^{T} I_{n-k} = A^{T} + A^{T} = \mathbf{0}$ in modulo-2 arithmetic, where addition is its own inverse.
2. Part (c) — transpose the parity submatrix. Taking the first four columns of $H$ as $A$ and transposing, $$A^{T} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}.$$ Each row of $A^{T}$ tells which of the three parity bits a given message bit contributes to.
3. Part (c) — assemble the generator matrix. Placing $I_4$ to the left of $A^{T}$, $$\boxed{G = \left[\,I_4 \mid A^{T}\,\right] = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}}$$ Because of the leading identity block the code is systematic: the first four bits of every codeword are the message itself and the last three are parity, so no inverse mapping is needed at the receiver once errors have been corrected. Multiplying out confirms $GH^{T} = \mathbf{0}$, and the seven columns of $H$ are all distinct and non-zero — the defining property of a Hamming code, and the reason every single-bit error produces a unique syndrome. Exhaustively weighing the sixteen codewords generated by $G$ gives $d_{\min} = 3$, consistent with part (b) and with single-error correction.

(d) Worked single-error correction (10 marks)

Approach. Encode a chosen message, deliberately flip one bit, compute the syndrome of the received word, match the syndrome against the columns of $H$ to locate the flipped position, invert that bit and recover the message.

1. Part (d) — encode a message. Take the four-bit message $\mathbf{m} = (1\;0\;1\;1)$. Then $\mathbf{c} = \mathbf{m}G$, computed modulo 2. The first four bits are the message; the three parity bits are the modulo-2 sums of the rows of $A^{T}$ selected by the ones in $\mathbf{m}$, namely rows 1, 3 and 4: $$(1\,1\,0) \oplus (0\,1\,1) \oplus (1\,1\,1) = (0\,1\,0),$$ so the transmitted codeword is $$\boxed{\mathbf{c} = (1\;0\;1\;1\;\;0\;1\;0)}$$ Checking, $H\mathbf{c}^{T} = (0\;0\;0)^{T}$, so $\mathbf{c}$ is a valid codeword.
2. Part (d) — introduce a single-bit channel error. Suppose the channel flips bit position 2, so the received word is $$\mathbf{r} = \mathbf{c} \oplus \mathbf{e}_2 = (1\;1\;1\;1\;\;0\;1\;0), \qquad \mathbf{e}_2 = (0\;1\;0\;0\;0\;0\;0).$$ The receiver knows neither $\mathbf{c}$ nor $\mathbf{e}$ — only $\mathbf{r}$.
3. Part (d) — compute the syndrome. The syndrome is the result of applying the parity checks to what was actually received: $$\mathbf{s} = H\mathbf{r}^{T} = H(\mathbf{c} \oplus \mathbf{e})^{T} = \underbrace{H\mathbf{c}^{T}}_{=\,\mathbf{0}} \oplus\, H\mathbf{e}^{T} = H\mathbf{e}^{T},$$ so the syndrome depends only on the error pattern, never on the message. Evaluating the three parity checks row by row on $\mathbf{r} = (1,1,1,1,0,1,0)$:

   Check	Row of $H$	Modulo-2 sum with $\mathbf{r}$	Syndrome bit
   1	(1 1 0 1 1 0 0)	$1 \oplus 1 \oplus 1 \oplus 0 = 1$	1
   2	(1 0 1 1 0 1 0)	$1 \oplus 1 \oplus 1 \oplus 1 = 0$	0
   3	(0 1 1 1 0 0 1)	$1 \oplus 1 \oplus 1 \oplus 0 = 1$	1

   $$\boxed{\mathbf{s} = (1\;0\;1)^{T} \neq \mathbf{0}}$$ A non-zero syndrome announces that an error has occurred.
4. Part (d) — locate the error by matching the syndrome to a column of $H$. For a single error in position $i$, $\mathbf{e}$ has a lone 1 in position $i$, so $H\mathbf{e}^{T}$ is simply the $i$-th column of $H$. Scanning the seven columns $$(1,1,0),\ (1,0,1),\ (0,1,1),\ (1,1,1),\ (1,0,0),\ (0,1,0),\ (0,0,1),$$ the syndrome $(1,0,1)$ matches column 2 and no other — the columns are distinct by construction, so the match is unique. The error is therefore in bit position 2.
5. Part (d) — correct and decode. Flipping bit 2 of $\mathbf{r}$ restores $$\hat{\mathbf{c}} = \mathbf{r} \oplus \mathbf{e}_2 = (1\;0\;1\;1\;\;0\;1\;0) = \mathbf{c},$$ and because the code is systematic the message is read straight off the first four bits: $$\boxed{\hat{\mathbf{m}} = (1\;0\;1\;1) = \mathbf{m}}$$ The error has been corrected without retransmission. Repeating the exercise for a flip in each of the other six positions gives, in turn, the other six columns of $H$ as the syndrome, so every single-bit error in the seven-bit block is located and corrected. Two simultaneous errors, by contrast, produce a syndrome equal to the sum of two columns, which is itself one of the seven columns — the decoder would then “correct” the wrong bit and deliver three errors. That is the price of $d_{\min} = 3$, and the reason part (b)’s bound is a hard limit rather than a guideline.