Error detection and correction

When data is transmitted over a communication channel or stored on a medium, noise and interference can flip individual bits, turning a transmitted 1 into a received 0 or the reverse. Error detection and correction are the techniques that let a receiver notice such corruption and, in some schemes, repair it without asking for the data again. They work by adding controlled redundancy: extra bits computed from the original data are sent alongside it, and the receiver recomputes them to check for consistency.

The simplest scheme is a single parity bit, which records whether the number of 1 bits is even or odd and can flag any single-bit error. Checksums and more elaborate codes extend the idea to catch more errors. A Hamming code is a block code that interleaves several parity bits at power-of-two positions so that, when an error occurs, the failed parity checks point directly to the corrupted bit; a basic Hamming code can correct any single-bit error and detect some double-bit errors. Such forward error correction is valuable when retransmission is costly or impossible.

For detection over noisy links, the cyclic redundancy check (CRC) is widely used. It treats the message as a large binary number and divides it, using modulo-2 arithmetic, by a fixed generator polynomial; the remainder becomes the CRC checksum appended to the frame. The receiver repeats the division and expects a zero remainder. CRCs are efficient in hardware and catch all single-bit errors, all odd numbers of bit errors for suitable polynomials, and long bursts of consecutive errors, which is why they appear in Ethernet, storage formats, and many file integrity checks.

Frequently asked questions

What is the difference between error detection and error correction?

Detection only reveals that data was corrupted, usually prompting a retransmission, while correction adds enough redundancy for the receiver to reconstruct the original data on its own.

What can a Hamming code do?

A basic Hamming code can correct any single-bit error in a block and detect some two-bit errors, using parity bits placed at power-of-two positions to locate the faulty bit.

Does a CRC correct errors?

No. A CRC is a detection method: it reliably flags corrupted frames, including burst errors, but does not repair them, so the frame is normally discarded and resent.