Hamming code (7,4): encoder and error corrector, live

A Hamming (7,4) code protects 4 data bits with 3 parity bits so that any single flipped bit can be found and fixed. The receiver recomputes the three parity checks, and the 3-bit result, the syndrome, is the position of the bad bit, or 000 when nothing is wrong.

The seven bits are numbered 1 to 7. Positions 1, 2 and 4 (the powers of two) hold parity bits and positions 3, 5, 6 and 7 hold the data D1 to D4. Each parity bit covers the positions whose number has its bit set: p1 covers 3, 5 and 7, p2 covers 3, 6 and 7, p4 covers 5, 6 and 7. Every position has a different set of checks, so when one bit flips, the checks that fail spell out its position in binary. This circuit is the whole round trip: an encoder, a channel where the switches E1 to E7 each flip one of the seven bits in transit, and a decoder that computes the syndrome S4 S2 S1 and flips the bad data bit back, giving the repaired data R1 to R4. Turn on any single E switch and R still equals D. Turn on two and the syndrome points at the wrong bit, which is why memory that must also catch double errors adds an overall parity bit (SECDED). The simpler single-error detector is the parity generator and checker.

Big circuit: pinch, scroll or tap + to zoom in, then drag to move around.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

6× XOR: encoder: p1 = D1 XOR D2 XOR D4, p2 = D1 XOR D3 XOR D4, p4 = D2 XOR D3 XOR D4
7× XOR: the channel: each bit XOR its error switch E1 to E7
9× XOR: syndrome: S1, S2 and S4 each XOR four received bits
3× NOT: inverted syndrome bits for the position decoder
8× AND: decode positions 3, 5, 6 and 7 (each a 3-input AND made of two gates)
4× XOR: flip the data bit the syndrome points at

Step by step

Place data inputs D1 to D4 and compute the parity bits: p1 = D1 XOR D2 XOR D4, p2 = D1 XOR D3 XOR D4, p4 = D2 XOR D3 XOR D4. The codeword is p1 p2 D1 p4 D2 D3 D4.
Model the channel: XOR each of the seven bits with an error switch E1 to E7. Off means the bit arrives intact; on flips it.
At the receiver, recompute each check over the received bits: S1 over positions 1, 3, 5, 7; S2 over 2, 3, 6, 7; S4 over 4, 5, 6, 7.
Read S4 S2 S1 as a number. Decode positions 3, 5, 6 and 7 with AND gates, and XOR each received data bit with its decoder output to get R1 to R4.
Set a data word, then turn on one error switch at a time: the syndrome names the position, and R stays equal to D. A flip in a parity position (1, 2 or 4) is reported but leaves the data alone.

What the syndrome means

S4 S2 S1	Position	Bad bit	Repair
000	none	none	nothing to do
001	1	p1	data already correct
010	2	p2	data already correct
011	3	D1	flip D1
100	4	p4	data already correct
101	5	D2	flip D2
110	6	D3	flip D3
111	7	D4	flip D4

Before the page is built the circuit is checked on all 2,048 combinations of the 16 data words and the 128 error patterns, against a model of a Hamming decoder: every single error is corrected, and for multiple errors the circuit does exactly what the code predicts (the syndrome is the XOR of the flipped positions). For example, data 1011 is sent as 0110011; flip position 5 and the syndrome reads 101.

You can also read the full theory in the lesson on error detection and correction. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load 1011 sequence detector binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter traffic light controller 4-bit barrel shifter CMOS AND gate CMOS OR gate CMOS XOR gate 1-bit magnitude comparator half subtractor from NAND gates full subtractor from NAND gates 8-to-3 encoder Gray to binary converter 4-to-16 decoder

Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.

Open the Hamming (7,4) code encoder and corrector in the lab →

Frequently asked

What is a Hamming code?

An error-correcting code that adds parity bits at the power-of-two positions of a word so that the pattern of failed parity checks, the syndrome, gives the position of a single flipped bit. Hamming (7,4) sends 4 data bits as 7 bits and corrects any one error.

How many parity bits does Hamming (7,4) use?

Three, at positions 1, 2 and 4. In general r parity bits can protect m data bits when 2^r is at least m + r + 1, so 3 parity bits cover 4 data bits (8 is at least 4 + 3 + 1).

How does the syndrome find the error?

Each position is covered by a different combination of parity checks: exactly the checks whose numbers add up to the position. When one bit flips, exactly those checks fail, so the failed checks read as a binary number are the position of the error.

Can a Hamming code correct two errors?

No. Two flipped bits give a syndrome that points at a third, wrong position. Adding one overall parity bit (SECDED: single error correction, double error detection) lets the receiver tell that two bits flipped, without being able to fix them.

How do you encode 1011 with Hamming (7,4)?

With D1 D2 D3 D4 = 1 0 1 1: p1 = 1 XOR 0 XOR 1 = 0, p2 = 1 XOR 1 XOR 1 = 1, p4 = 0 XOR 1 XOR 1 = 0, so the codeword p1 p2 D1 p4 D2 D3 D4 is 0110011.