Error detection and correction

Error detection and correction techniques are classified by their ability to detect or correct errors. Detection-only methods, such as parity bits and checksums, append a small amount of redundancy that allows the receiver to recognize that an error has occurred, but not to locate or fix it. Error-correcting codes (ECC), also called forward error correction (FEC), add more redundancy so that the receiver can identify and correct errors without a retransmission request. A key metric is the Hamming distance between valid codewords; a code with minimum distance d can detect up to d−1 errors and correct up to ⌊(d−1)/2⌋ errors.¹

Simple detection codes include single parity bits, which can detect odd numbers of bit flips, and cyclic redundancy checks (CRCs), which are polynomial-based and widely used in Ethernet and storage. For correction, block codes like Hamming codes and Reed–Solomon codes are used in CDs, QR codes, and deep-space communications. Convolutional codes and modern turbo codes and low-density parity-check (LDPC) codes approach the Shannon limit and are used in 5G, Wi-Fi, and satellite links.² The choice of code balances overhead, latency, and error-correction capability.

Error correction is critical in computer memory: ECC RAM uses Hamming codes to correct single-bit errors and detect double-bit errors, protecting servers and critical systems. In storage, RAID arrays and file systems like ZFS use checksums and parity to detect and repair data corruption. In telecommunications, FEC is mandatory in optical transport and deep-space missions; for example, NASA's Voyager probes use Reed–Solomon codes to transmit images from beyond the solar system.³ Wireless standards like 5G NR employ LDPC codes for data channels to achieve high throughput in noisy environments.

Beyond the mainstream, error correction appears in unexpected places. The ISBN-10 and ISBN-13 book identifiers use a check digit to detect transcription errors, and credit card numbers use the Luhn algorithm. The Voyager Golden Record includes a special cover with instructions for playing it, but the audio itself uses a simple error-correction scheme. In quantum computing, quantum error correction (QEC) uses entangled states to protect against decoherence, a fundamentally different approach from classical codes. Also, the 1950 Hamming code was developed by Richard Hamming at Bell Labs to fix errors in early relay computers, and his work laid the foundation for the field.⁴

Hamming distance

The number of positions in which two codewords differ.

Forward error correction (FEC)

A technique where redundant data is sent to allow error correction at the receiver.

Cyclic redundancy check (CRC)

A polynomial-based checksum used to detect accidental changes to raw data.

Low-density parity-check (LDPC) code

A linear error-correcting code that approaches the Shannon limit.