A parity check code has the parity check matrix :
H = [1 0 1 1 0 0; 1 1 0 0 1 0; 0 1 1 0 0 1]
(rows: 1 0 1 1 0 0 / 1 1 0 0 1 0 / 0 1 1 0 0 1)
I. Determine the generator matrix G.
II. Find the code word that begins with 101... .
III. Suppose that the received word is 110110. Decode this received word.
10 marks · directive: Determine
The core of a good answer
Since H = [Pᵀ | I₃] with Pᵀ = [1 0 1; 1 1 0; 0 1 1], the generator matrix is G = [I₃ | P] = [1 0 0 1 1 0; 0 1 0 0 1 1; 0 0 1 1 0 1]; the codeword for 101 is 101011; the received word 110110 has syndrome 011, which matches column 2 of H, so the second bit is in error and the decoded codeword is 100110 (message 100).
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
This is a (6, 3) systematic linear block code. The method: identify the parity submatrix from H, write G = [I_k | P], encode by c = mG, and decode by the syndrome s = rHᵀ, matching it to a column of H for single error correction.
Answer outline
Introduction
H is 3 × 6 with the identity in its last three columns, so n = 6, k = 3, n − k = 3. The code is in systematic form with message bits first and parity bits last. All arithmetic is modulo 2.
Step 1: Identify P
- H = [Pᵀ | I₃], with Pᵀ = [1 0 1; 1 1 0; 0 1 1]
- P = (Pᵀ)ᵀ = [1 1 0; 0 1 1; 1 0 1]
Step 2: Generator matrix, part I
- G = [I₃ | P]
- G = [1 0 0 1 1 0; 0 1 0 0 1 1; 0 0 1 1 0 1]
- Check: GHᵀ = 0 (verified for all rows)
Step 3: Parity equations
- c₄ = m₁ ⊕ m₃
- c₅ = m₁ ⊕ m₂
- c₆ = m₂ ⊕ m₃
Step 4: Codeword beginning with 101, part II
- m = 101: c₄ = 1 ⊕ 1 = 0, c₅ = 1 ⊕ 0 = 1, c₆ = 0 ⊕ 1 = 1
- Codeword = 101011
- Check: H × (101011)ᵀ = 000
Step 5: Syndrome of the received word, part III
- r = 110110
- s₁ = r₁ ⊕ r₃ ⊕ r₄ = 1 ⊕ 0 ⊕ 1 = 0
- s₂ = r₁ ⊕ r₂ ⊕ r₅ = 1 ⊕ 1 ⊕ 1 = 1
- s₃ = r₂ ⊕ r₃ ⊕ r₆ = 1 ⊕ 0 ⊕ 0 = 1
- s = 011
Step 6: Error location and correction
- s = 011 equals the second column of H, so a single error is assumed in bit 2
- Error pattern e = 010000
- Corrected codeword c = r ⊕ e = 100110, decoded message = 100
- Check: 100 × G = 100110, a valid codeword
Conclusion
G = [1 0 0 1 1 0; 0 1 0 0 1 1; 0 0 1 1 0 1]; the codeword for 101 is 101011; 110110 decodes to 100110 (message 100). The code has minimum distance 3 (all six columns of H are distinct and non zero), so it corrects any single error.
Examples and data to cite
- The eight codewords are 000000, 001101, 010011, 011110, 100110, 101011, 110101 and 111000.
- The six columns of H are distinct and non zero, which is the condition for a code to correct any single bit error (the same principle as the Hamming codes).
Facts to remember
- For a systematic code, if H = [Pᵀ | I_{n−k}] then G = [I_k | P], and GHᵀ = 0.
- Encoding: c = mG (modulo 2).
- Syndrome s = rHᵀ; s = 0 for a valid codeword; for a single error in position j, s equals the j th column of H.
- A code corrects t errors if d_min ≥ 2t + 1; here d_min = 3, so t = 1.
- Results recomputed in Python with numpy (mod 2 arithmetic).