Error Detection and Correction: Parity and Hamming

Parity: cheap single-error detection

Wires, memories and links all flip bits occasionally from noise, radiation or marginal timing, so error coding adds redundant bits the receiver can use to notice, and sometimes repair, those flips. The key measure is Hamming distance: the number of bit positions in which two valid codewords differ. A parity bit is the XOR of all data bits. Even parity makes the total number of 1s even; odd parity makes it odd. The receiver recomputes parity and flags a mismatch. One extra bit gives a minimum Hamming distance of 2, which is enough to detect any single bit flip but not to locate it, and any even number of flips slips through undetected.

// 8-bit even parity generate and check
wire [7:0] data;
wire parity_bit = ^data;            // XOR reduction = even parity

// receiver: zero means no detected error
wire [8:0] received;                // {parity, data}
wire error = ^received;             // 1 if a single-bit flip occurred

Hamming code: correcting single errors

To fix an error you need to know which bit flipped, so you need more redundancy. A Hamming code places parity bits at power-of-two positions (1, 2, 4, 8, ...) and each parity bit covers a specific subset of positions. When the receiver recomputes the checks, the failing checks form a binary number called the syndrome that points directly at the flipped bit. A code with k parity bits protects up to 2 to the power k minus k minus 1 data bits.

In this (7,4) code, suppose the syndrome from the three checks reads P4 P2 P1 = 101, which is binary 5. Position 5 is the bit that flipped, so the receiver simply inverts it; a clean codeword gives syndrome 000. Basic Hamming has minimum distance 3, which corrects one error or detects two but not both at once. Adding one overall parity bit raises the distance to 4 and gives SECDED: single error correction, double error detection. This is exactly what ECC memory uses, typically 8 check bits guarding 64 data bits. Storage and high-speed links go further with CRC for detection and Reed-Solomon or LDPC codes for correcting bursts of errors.