Hamming code calculator: encode, check and correct

A Hamming code puts parity bits at the power-of-two positions (1, 2, 4, 8, ...) of a codeword so that any single flipped bit can be found and fixed: the receiver recomputes each parity check, and the checks that fail, read as a binary number, give the position of the bad bit. Encode your data below, then flip a bit and watch it get corrected.

Worked example: 1011 in the (7,4) code

The data bits d1 to d4 = 1, 0, 1, 1 go to positions 3, 5, 6 and 7. Each parity bit makes its group even: p1 covers positions 3, 5, 7, so p1 = 1 XOR 0 XOR 1 = 0; p2 covers 3, 6, 7, so p2 = 1 XOR 1 XOR 1 = 1; p4 covers 5, 6, 7, so p4 = 0 XOR 1 XOR 1 = 0. The codeword is 0110011.

Now flip position 5 in transit: 0110111. The receiver's check over positions 1, 3, 5, 7 fails, the one over 2, 3, 6, 7 passes and the one over 4, 5, 6, 7 fails, so the syndrome is 4 + 1 = 5: flip bit 5 back and read the data 1011 again. That works for every position because no two positions are covered by the same set of checks. The calculator is tested on every data length from 1 to 64 bits, with every single-bit error corrected.

How many parity bits?

With r parity bits the syndrome can name 2^r - 1 positions, so r is the smallest number with 2^r at least k + r + 1 for k data bits. The cost falls quickly as words grow:

The last row is why ECC memory commonly uses 72-bit words: 64 data bits, 7 Hamming parity bits and one overall parity bit for SECDED.

SECDED: catching two errors

A plain Hamming code cannot tell one error from two: two flipped bits give a nonzero syndrome that points at a third, innocent bit, and correcting it makes things worse. SECDED adds one overall parity bit, P, over the whole word. One error makes the overall parity odd, and the syndrome says where; two errors leave it even while the syndrome is nonzero, so the word is reported as uncorrectable instead. Tick SECDED above and flip two bits to see it. Richard Hamming published these codes in 1950, after the relay computers he used at Bell Labs kept abandoning his jobs whenever they detected an error.

The same code as a circuit

Encoding and checking are nothing but XOR gates, so a Hamming code costs very little hardware. The Hamming (7,4) encoder and corrector builds the whole round trip from gates: an encoder, a channel where you can flip any bit, and a decoder that fixes it. For a single parity bit, see the parity generator and checker; for detecting errors in long messages, the CRC calculator. The error detection and correction lesson ties them together.

Frequently asked

How do you calculate a Hamming code?

Number the codeword positions from 1. Put parity bits at the powers of two (1, 2, 4, 8, ...) and the data bits, in order, everywhere else. Each parity bit p is the XOR of the bits at every position whose number has bit p set, which makes each check even. For the data 1011 that gives the codeword 0110011.

How many parity bits does a Hamming code need?

The smallest r with 2^r at least k + r + 1, for k data bits: 2 for 1 data bit, 3 for 2 to 4 (4 data bits make the (7,4) code), 4 for 5 to 11, 5 for 12 to 26, 6 for 27 to 57 and 7 for 58 to 120. SECDED adds one more.

How do you find which bit is wrong?

Recompute every parity check over the received word, including the parity bit itself. Each check that fails contributes its position number; added together they are the syndrome, which is the position of the flipped bit. A syndrome of 0 means no error was detected.

What is SECDED?

Single error correction, double error detection: a Hamming code plus one overall parity bit across the whole word. One flipped bit makes the overall parity odd and the syndrome points to it; two flipped bits leave the overall parity even but the syndrome nonzero, so the error is reported instead of being miscorrected. ECC memory commonly stores 64 data bits as a 72-bit SECDED word.

Can a Hamming code correct two errors?

No. A Hamming code has a minimum distance of 3, enough to correct one error; two errors produce a syndrome that points at a third, wrong position. With the extra SECDED bit the distance is 4, so two errors are detected but still not corrected.

What is the (7,4) Hamming code?

The smallest useful Hamming code: 7 bits in total, 4 of them data. Parity p1 covers positions 3, 5 and 7, p2 covers 3, 6 and 7, and p4 covers 5, 6 and 7. It is built as a live gate circuit in the Hamming code encoder and corrector.