Encode an 8-bit byte: 1011 0101 — Hamming code
exam standardoverhead falls as the block grows
Answer
001101100101
Why this example is worth doing
Eight data bits need four parity bits, giving a (12,8) code — fifty per cent overhead against the (7,4) code's seventy-five. The page tabulates the overhead as the block length grows and makes the general point that longer blocks are more efficient but more fragile, because the single-error guarantee applies per block. Choosing a block length is a trade between overhead and the expected error rate.
Try your own input in the Hamming code. Encode, inject an error, and watch the syndrome point straight at the flipped bit.
How the answer is reached
Hamming (12,8) encode
Hamming (12,8): 4 parity bits, because 2^4 = 16 ≥ k + r + 1 = 13.
Data word10110101
| Position | Binary index | Holds | Bit |
|---|---|---|---|
| 1 | 0001 | p1 | 0 |
| 2 | 0010 | p2 | 0 |
| 3 | 0011 | d1 | 1 |
| 4 | 0100 | p4 | 1 |
| 5 | 0101 | d2 | 0 |
| 6 | 0110 | d3 | 1 |
| 7 | 0111 | d4 | 1 |
| 8 | 1000 | p8 | 0 |
| 9 | 1001 | d5 | 0 |
| 10 | 1010 | d6 | 1 |
| 11 | 1011 | d7 | 0 |
| 12 | 1100 | d8 | 1 |
Each parity bit is the XOR of the data bits it covers, so every check comes out even.
p11 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0— covers positions 3, 5, 7, 9, 11
p21 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 0— covers positions 3, 6, 7, 10, 11
p40 ⊕ 1 ⊕ 1 ⊕ 1 = 1— covers positions 5, 6, 7, 12
p80 ⊕ 1 ⊕ 0 ⊕ 1 = 0— covers positions 9, 10, 11, 12
Codeword001101100101Highlighted cells are parity bits.
Positions are 1-indexed: the first character of the codeword is position 1.
Source: R. W. Hamming, Bell System Technical Journal 29(2):147–160 (1950)