Construct a (7,4) Hamming code

A (7,4) Hamming code encodes 4 data bits into 7 bits by adding 3 parity bits. It has d_min = 3, so it corrects any single-bit error.

Generator matrix (4 × 4 identity + 4 × 3 parity part)

G = [I₄ | P]:

      | 1 0 0 0 : 1 1 0 |
 G =  | 0 1 0 0 : 0 1 1 |
      | 0 0 1 0 : 1 1 1 |
      | 0 0 0 1 : 1 0 1 |

Codeword c = d·G (mod 2) = [d1 d2 d3 d4 | p1 p2 p3], where

• p1 = d1 ⊕ d3 ⊕ d4
• p2 = d1 ⊕ d2 ⊕ d3
• p3 = d2 ⊕ d3 ⊕ d4

Encoding an arbitrary message d = 1011

c = row 1 ⊕ row 3 ⊕ row 4 = 1000110 ⊕ 0010111 ⊕ 0001101 = 1011100

(Check by equations: p1 = 1⊕1⊕1 = 1, p2 = 1⊕0⊕1 = 0, p3 = 0⊕1⊕1 = 0.)

Parity-check matrix H = [Pᵀ | I₃]

      | 1 0 1 1 : 1 0 0 |
 H =  | 1 1 1 0 : 0 1 0 |
      | 0 1 1 1 : 0 0 1 |

For every codeword, syndrome s = c·Hᵀ = 000.

Error detection and correction

Suppose bit 3 is received wrongly: r = 1001100.

• s1 = r1⊕r3⊕r4⊕r5 = 1⊕0⊕1⊕1 = 1
• s2 = r1⊕r2⊕r3⊕r6 = 1⊕0⊕0⊕0 = 1
• s3 = r2⊕r3⊕r4⊕r7 = 0⊕0⊕1⊕0 = 1

s = 111, which equals column 3 of H, so bit 3 is in error. Flip it to get 1011100 and read the message 1011.

The sixteen codewords

0000000, 0001101, 0010111, 0011010, 0100011, 0101110, 0110100, 0111001, 1000110, 1001011, 1010001, 1011100, 1100101, 1101000, 1110010, 1111111. The minimum non-zero weight is 3, so d_min = 3.