Topic: Information Theory and Coding
Consider a binary linear code with parity check matrix H given below.
$H=\begin{bmatrix}0&1&1&1&0&0\\ 1&0&1&0&1&0\\ 1&1&0&0&0&1\end{bmatrix}$
Which of the following is a valid codeword?
- A. [100101]
- B. [111101]
- C. [010010]
- D. [110110]
Answer: D. [110110]
Explanation: A valid codeword $c$ must satisfy the syndrome equation $H c^T = 0$ over GF(2). Multiplying $H$ by the transpose of option (d) $[1,1,0,1,1,0]^T$: Row 1: $(0\times1)+(1\times1)+(1\times0)+(1\times1)+(0\times1)+(0\times0) = 2 \equiv 0$. Row 2: $(1\times1)+(0\times1)+(1\times0)+(0\times1)+(1\times1)+(0\times0) = 2 \equiv 0$. Row 3: $(1\times1)+(1\times1)+(0\times0)+(0\times1)+(0\times1)+(1\times0) = 2 \equiv 0$. All rows yield 0, making it valid.