Computer Networks · TEE · papers
Q2(a) · Hamming error correction
2023-11-22 · AI-only Sem V variant; incomplete recovered scan
Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.
Q2(a). A seven-bit Hamming codeword received is 1011011. Assuming even parity, determine whether it is correct; if not, locate and correct the erroneous bit. [10 marks]
Answer
Given
Received word 1011011; even parity. Number positions 7,6,5,4,3,2,1 from left to right, so position 1 is the rightmost bit.
To find
Syndrome, erroneous position, and corrected word.
Formula and why
LaTeX: s_p=\bigoplus_{i\,\&\,p\ne0}b_i,\quad \text{error position}=4s_4+2s_2+s_1Each parity check covers positions whose binary position number contains that parity bit. For even parity, XOR must be zero; a 1 identifies a failed group.
Solution
Step 1. Label every received bit
| Position | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|
| Received bit | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
Step 2. Evaluate the three parity groups
| Parity | Covered positions | Bits added | Sum | Sum mod 2 |
|---|---|---|---|---|
| 1 | 1, 3, 5, 7 | 1 + 0 + 1 + 1 | 3 | 1 |
| 2 | 2, 3, 6, 7 | 1 + 0 + 0 + 1 | 2 | 0 |
| 4 | 4, 5, 6, 7 | 1 + 1 + 0 + 1 | 3 | 1 |
Step 3. Read the syndrome as a binary position
Syndrome s4s2s1 = 101; decimal = 5. Under the single-bit-error assumption, flip position 5 from the right. Corrected word = 1001011.
Step 4. State the assumption
Ordinary Hamming(7,4) corrects one bit. A multi-bit corruption may produce a misleading nonzero syndrome, so do not claim guaranteed correction of arbitrary errors.