Error Detection and Correction

Why stored and transmitted bits need protection

Every representation covered in this path has assumed the bits arrive intact. Real memory cells and real communication links do not make that guarantee – a cosmic ray can flip a stored bit, and electrical noise can flip a transmitted one. This lesson covers the standard techniques for noticing when a bit has flipped, and in one important case, for figuring out which bit it was and flipping it back without ever needing to ask for the data again.

The parity bit

The simplest protection scheme adds one extra bit to a word, chosen so that the total number of 1s in the word plus the parity bit is always even (even parity) or always odd (odd parity), by convention fixed in advance. For even parity, the parity bit is just the XOR of all the data bits, since XOR of a set of bits is 0 exactly when the set contains an even number of 1s. The receiver recomputes the same XOR over the received word; if it does not come out to the expected parity, at least one bit has flipped.

A single parity bit has a sharp limitation: it can only tell the receiver that an error happened, never which bit is wrong, so there is nothing for the receiver to do but ask for the data again. It also has a blind spot – if exactly two bits flip, the total count of 1s is unchanged, parity still checks out, and the error passes completely unnoticed. This is why parity by itself is reserved for links or memories where errors are rare and retransmission is cheap, and why anything that needs to recover from an error on the spot, without retransmission, needs more than one check bit.

Hamming codes: detecting and correcting

A Hamming code adds several parity bits, each covering a different, overlapping subset of the data bits, chosen so that the specific pattern of which checks fail and which pass points directly at which single bit is wrong. The classic Hamming(7,4) code takes 4 data bits and adds 3 parity bits to form a 7-bit codeword. The 7 positions are numbered 1 through 7, and the positions that are powers of two – 1, 2 and 4 – are reserved for the parity bits p₁, p₂ and p₄; the remaining positions, 3, 5, 6 and 7, carry the four data bits in order.

Each parity bit covers exactly the positions whose binary representation has its own bit set: p₁ (position 1, binary 001) covers every position whose binary form has bit 0 set – positions 1, 3, 5, 7. p₂ (position 2, binary 010) covers positions with bit 1 set – 2, 3, 6, 7. p₄ (position 4, binary 100) covers positions with bit 2 set – 4, 5, 6, 7. Every data position is covered by a different combination of the three parity bits, which is exactly the property that lets the decoder pin down a single flipped bit uniquely.

Worked example: encoding 1, 0, 1, 1

Let us encode the 4 data bits 1, 0, 1, 1, placed into positions 3, 5, 6, 7 respectively (d₁=1 at position 3, d₂=0 at position 5, d₃=1 at position 6, d₄=1 at position 7). Each parity bit is the XOR of its covered positions:

• p₁ = position 3 ⊕ position 5 ⊕ position 7 = 1 ⊕ 0 ⊕ 1 = 0
• p₂ = position 3 ⊕ position 6 ⊕ position 7 = 1 ⊕ 1 ⊕ 1 = 1
• p₄ = position 5 ⊕ position 6 ⊕ position 7 = 0 ⊕ 1 ⊕ 1 = 0

Laying out positions 1 through 7 in order (p₁, p₂, d₁, p₄, d₂, d₃, d₄) gives the codeword 0 1 1 0 0 1 1.

Locating an error with the syndrome

Suppose position 5 flips in transmission, so the received word becomes 0 1 1 0 1 1 1 instead of 0 1 1 0 0 1 1. The decoder recomputes each parity check against the received bits and records whether it still passes (0) or now fails (1), building a 3-bit syndrome:

• s₁ = position 1 ⊕ position 3 ⊕ position 5 ⊕ position 7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1 (fails)
• s₂ = position 2 ⊕ position 3 ⊕ position 6 ⊕ position 7 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 (passes)
• s₄ = position 4 ⊕ position 5 ⊕ position 6 ⊕ position 7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1 (fails)

Reading the syndrome bits as s₄s₂s₁ gives 1 0 1, which is binary for 5 – and the error really is at position 5. This is not a coincidence: it is exactly why the parity bits were assigned to cover the positions they cover. Each data position is covered by a unique combination of parity checks, so the pattern of which checks fail is the binary address of the one bit that flipped. Once the decoder has that address, correcting the error is just flipping the bit back at that position – no retransmission needed, which is the entire advantage a Hamming code buys over a plain parity bit.

Where this fits in a real design

Hamming(7,4) protects against exactly one flipped bit per codeword; two simultaneous flips can produce a syndrome that points at the wrong position and silently makes things worse, which is why error-correcting memory in real systems is usually described by its guarantee directly – SECDED (Single Error Correction, Double Error Detection) adds one more overall parity bit on top of a Hamming code specifically to at least detect, even where it cannot correct, a second simultaneous flip. Wider error-correcting codes used in storage and networking (Reed-Solomon, CRC for whole-packet detection without correction) extend the same core idea – add redundant, carefully chosen check bits so that the pattern of failed checks identifies the fault – to larger blocks and to error patterns beyond a single flipped bit.