Error-correcting code

An error-correcting code is a method of representing information with structured redundancy so that errors introduced during transmission or storage can be corrected. An encoder maps messages to permitted sequences called codewords; a decoder uses their structure to infer the original message from potentially corrupted data. Error-correcting codes are central to information theory and digital telecommunications. When correction occurs without requesting retransmission, the process is called forward error correction (FEC). (nokia.com)

Principles and parameters

Redundancy makes valid codewords distinguishable even after limited corruption. A simple repetition code represents one bit by three bits: 0 becomes 000, and 1 becomes 111. Majority decoding recovers the original bit if at most one position changes. Thus, receiving 101 yields the decoded value 1. This code is easy to implement but transmits three bits for every information bit. (math.mit.edu)

A block code encodes messages into fixed-length codewords. For a code mapping $k$ information symbols into $n$ symbols over the same alphabet, the code rate is

A higher rate means less redundancy, although reliability also depends on the code structure, channel, and decoder. A systematic encoder leaves the information symbols unchanged in designated positions and supplies additional check symbols; a nonsystematic encoder need not preserve this visible separation. (nokia.com)

Distance, detection, and correction

The Hamming distance between two equal-length sequences is the number of positions in which they differ. The minimum distance $d_{\min}$ of a code is the smallest distance between distinct codewords. It determines worst-case guarantees for symbol-substitution errors: a code can detect every pattern of up to $d_{\min}-1$ errors and uniquely correct every pattern of up to

errors. These are separate guarantees: a decoder configured to correct errors does not necessarily flag every larger, otherwise detectable pattern. (math.mit.edu)

Correction works because sets of received words within distance $t$ of different codewords do not overlap. Beyond this radius, decoding may still succeed, but success is not guaranteed; a corrupted word may be mistaken for another codeword. Error detection instead identifies a word as invalid without necessarily determining the original message. A system can use detection to request retransmission rather than correcting locally. (math.mit.edu)

Linear codes and syndrome decoding

A linear code is a linear subspace of $\mathbb{F}_q^n$, where $\mathbb{F}_q$ is a finite field. A $k$-dimensional linear code contains $q^k$ codewords. Its algebraic structure allows encoding and checking through matrices, rather than storing every codeword explicitly. Using row-vector notation, a generator matrix $G$ encodes a message $u$ as $c=uG$. A parity-check matrix $H$ satisfies $Hc^T=0$ for every codeword. (ocw.mit.edu)

If the received vector is $r=c+e$, its syndrome is

The syndrome depends on the error vector $e$, not on the transmitted codeword. A syndrome decoder associates syndromes with candidate error patterns and removes the inferred error. A zero syndrome means that the received vector is a valid codeword, not necessarily that transmission was error-free. For binary codes, addition uses exclusive OR, equivalent to addition modulo two in modular arithmetic. (ocw.mit.edu)

The binary [[hamming-code|Hamming $[7,4,3]$ code]] encodes four information bits into seven bits and corrects any single-bit error. Its three-bit syndrome distinguishes the seven possible single-error positions from the no-error case. (ocw.mit.edu)

Major code families and decoding methods

Reed–Solomon codes construct codewords using evaluations of polynomials over finite fields. Their symbols can represent groups of bits, and their symbol-level correction capability makes them useful when corruption affects consecutive bits. They have been used in compact discs and spacecraft communications. (learn.mit.edu)

Convolutional codes encode streams using a finite-state mechanism whose output depends on current input and stored state. Decoding commonly uses the Viterbi algorithm to find the most likely path through a state-transition trellis. Hard-decision decoding uses discrete symbol decisions; soft-decision decoding retains information about received-signal reliability, allowing more informed choices. (ocw.mit.edu)

Low-density parity-check (LDPC) codes use sparse parity-check matrices and are commonly decoded through iterative message passing. Turbo codes combine constituent codes with an interleaver and exchange reliability information between component decoders. Both families can approach channel-capacity limits under suitable conditions. Concatenated constructions combine codes, such as an outer Reed–Solomon code and an inner convolutional code. (ocw.mit.edu)

Historical foundations and practical limits

In 1948, Claude Shannon established the noisy-channel coding theorem. For a discrete memoryless channel, information rates below its channel capacity permit codes whose decoding-error probability becomes arbitrarily small as block length increases. The theorem establishes an achievable limit, not a promise that every finite-length code attains it. Richard Hamming’s 1950 paper developed practical error-detecting and error-correcting constructions. (mtlsites.mit.edu)

Practical code selection balances redundancy, delay, decoding work, and residual error probability. Longer blocks and sophisticated decoders can improve performance but require buffering and computation. Spacecraft links illustrate these choices: NASA documentation describes Reed–Solomon, convolutional, turbo, and LDPC coding, with performance depending on block size, coding scheme, and link margin. Unlike data compression, which reduces representation length, error correction deliberately introduces redundancy to protect information. (ocw.mit.edu)