Parity-check matrix for the (7,4) code — Hamming code
edge casethe linear-algebra view
Answer
H is 3×7
Why this example is worth doing
The same code expressed as matrices: the syndrome is H times the received vector over GF(2), and the columns of H are simply the numbers one to seven written in binary. Seeing that makes the syndrome-equals-position property a triviality rather than a coincidence. The page includes this view because it is the one that generalises to every other linear code, and it is where a coding-theory course picks up.
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 (7,4) matrices over GF(2)
Position-ordered parity-check matrix H: column c is position (c + 1) written in binary, least significant bit in row 0.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 |
Systematic form puts the payload first: G = [I_k | P] and H = [Pᵀ | I_{n−k}], so G·Hᵀ = P + P = 0.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 |
Encoding is c = m·G and the syndrome is s = H·rᵀ, both over GF(2).
Source: R. W. Hamming, Bell System Technical Journal 29(2):147–160 (1950)