# Q4(c) · Hamming generation and correction

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2024-ai-final/q4c

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2024-ai-final--q4c/

Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.

### Q4(c). Generate even-parity Hamming code for data 10101111. If the 7th bit is corrupted, give the received pattern and show how to detect and correct the error. [10 marks]

### Answer

**Source note:** The paper does not state bit-position direction. The solution numbers positions from the right, matching current faculty slides; position 7 means the seventh from the right throughout.

### Given

Data 10101111; even parity; one error at position 7 from the right.

### To find

Codeword, received word, syndrome, corrected data.

### Formula and why



$$
2^r\ge m+r+1,\qquad m=8
$$



Use the smallest r satisfying the inequality. Four checks label positions up to 12; parity positions are powers of two.

### Solution

### Step 1. Choose parity positions

r=3 gives 8 < 8+3+1=12, so it is insufficient. r=4 gives16 ≥8+4+1=13. Total length =12; reserve positions1,2,4,8.

### Step 2. Insert data in the remaining positions

| Position (right-to-left index) | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Role | data | data | data | data | p8 | data | data | data | p4 | data | p2 | p1 |
| Data/parity | 1 | 0 | 1 | 0 | ? | 1 | 1 | 1 | ? | 1 | ? | ? |

### Step 3. Set each parity bit for an even total

| Parity | Other covered positions | Other bits | Parity bit |
| --- | --- | --- | --- |
| 1 | 3, 5, 7, 9, 11 | 1 + 1 + 1 + 0 + 0 | 1 |
| 2 | 3, 6, 7, 10, 11 | 1 + 1 + 1 + 1 + 0 | 0 |
| 4 | 5, 6, 7, 12 | 1 + 1 + 1 + 1 | 0 |
| 8 | 9, 10, 11, 12 | 0 + 1 + 0 + 1 | 0 |

**Transmitted codeword = 101001110101**.

### Step 4. Flip position 7

Position7 changes 1→0. Received word = **101000110101**.

### Step 5. Compute the received syndrome

| Parity check | Positions | XOR |
| --- | --- | --- |
| 1 | 1,3,5,7,9,11 | 1 |
| 2 | 2,3,6,7,10,11 | 1 |
| 4 | 4,5,6,7,12 | 1 |
| 8 | 8,9,10,11,12 | 0 |

s8s4s2s1 = 0111 = 7. Flip position7 back; all four checks become0. Remove positions1,2,4,8 to recover **10101111**.