Error-Correcting Codes
Error-correcting codes add structured redundancy to data so that errors introduced during transmission or storage can be detected and corrected.
Definition
A code is a set of codewords, typically strings over a finite alphabet, chosen so that any two differ in enough positions that errors changing a few symbols can be detected or corrected by decoding to the nearest codeword.
Scope
This topic covers the basic parameters of block codes - length, dimension, and minimum distance - the Hamming metric, linear codes and their generator and parity-check matrices, and key families such as Hamming, Reed-Solomon, BCH, and Reed-Muller codes. It introduces fundamental bounds on code parameters, including the Singleton, Hamming, and Gilbert-Varshamov bounds.
Core questions
- How many errors can a code detect and correct given its minimum distance?
- How are good codes constructed over finite fields?
- What are the fundamental trade-offs among length, rate, and distance?
- How can codes be decoded efficiently?
Key concepts
- Hamming distance and weight
- Minimum distance
- Linear codes
- Generator and parity-check matrices
- Hamming and Reed-Solomon codes
- Singleton and Hamming bounds
Key theories
- Minimum distance and error correction
- A code with minimum Hamming distance d can detect up to d-1 errors and correct up to the floor of (d-1)/2 errors, the central principle relating geometric separation of codewords to error-handling capability.
- Singleton bound and MDS codes
- The minimum distance of a code of length n and dimension k cannot exceed n-k+1; codes meeting this bound with equality, such as Reed-Solomon codes, are maximum distance separable and optimally efficient.
Clinical relevance
Error-correcting codes are indispensable in digital communication and storage: they protect data on compact discs and hard drives, in QR codes, cellular and satellite links, and deep-space transmission, and they connect to combinatorial designs and finite geometry.
History
Shannon's 1948 channel-coding theorem proved reliable communication is possible below capacity, and Hamming's 1950 codes gave the first practical construction, launching coding theory as a discipline.
Key figures
- Claude Shannon
- Richard Hamming
- Irving Reed
Related topics
Seminal works
- macwilliams1977
- vanlintcoding1999
Frequently asked questions
- How does a code correct an error without knowing where it is?
- Because valid codewords are spread far apart, a received word with few errors is closest to exactly one codeword, and decoding to the nearest codeword recovers the original.
- What is the difference between detection and correction?
- Detection only flags that an error occurred and may request retransmission, while correction recovers the intended data directly; correction requires a larger minimum distance.