Error-correcting codes

Basic Principles

Redundancy and Parity

Error‑correcting codes work by adding carefully designed redundancy to the original data. The sender appends extra bits—called parity bits or check bits—to the information bits. The resulting longer sequence (a codeword) is transmitted over a noisy channel. At the receiver, the redundant bits allow the detection and, in many cases, the correction of errors that occur during transmission. The simplest example is a single parity bit that makes the total number of 1s in a block either even or odd; this can detect an odd number of bit flips but cannot correct them. More sophisticated codes add multiple parity bits to enable actual error correction.

Hamming Distance and Minimum Distance

The Hamming distance between two codewords is the number of positions in which they differ. For a code, the minimum distance \(d_{\min}\) is the smallest Hamming distance between any two distinct codewords. This parameter directly determines the code’s error‑correcting capability: a code with minimum distance \(d_{\min}\) can guarantee correction of up to \(\lfloor (d_{\min}-1)/2 \rfloor\) errors per codeword. For example, a code with \(d_{\min}=3\) can correct any single‑bit error. The concept of Hamming distance is fundamental to coding theory; it provides a geometric view of codewords as points in a binary space, with error correction corresponding to moving a received point to the nearest codeword.

Historical Development

Early Work: Hamming Codes (1940s–1950s)

The modern theory of error‑correcting codes began with Richard Hamming at Bell Labs in the late 1940s. Dissatisfied with the error‑prone relay computers of the day, Hamming devised codes that could automatically detect and correct single‑bit errors. His Hamming codes are a family of linear block codes that add \(r\) parity bits to \(k\) information bits, producing codewords of length \(n = 2^r - 1\) with minimum distance 3. A Hamming code can correct any single error and detect any double error. These codes are among the simplest and most elegant examples of error correction and remain widely used, particularly in computer memory (ECC RAM).

Reed–Solomon and Convolutional Codes (1960s)

In 1960, Irving Reed and Gustave Solomon introduced a class of non‑binary block codes now known as Reed–Solomon (RS) codes. These codes work on groups of bits (symbols) rather than individual bits, making them highly effective against burst errors. They achieve large minimum distances and are optimal in the sense that they meet the Singleton bound. RS codes found early use in deep‑space probes and later in optical storage (compact discs) and digital broadcasting. Around the same time, convolutional codes were proposed by Peter Elias. Unlike block codes, which process fixed‑length messages, convolutional codes generate a continuous stream of encoded bits using a sliding‑window linear function (typically implemented with shift registers). They are well suited for real‑time communication and lay the groundwork for later advances such as turbo codes.

Applications in Modern Systems

Error‑correcting codes are embedded in nearly every digital communication and storage system. In computer memory, error‑correcting code (ECC) RAM uses Hamming or more advanced codes to correct single‑bit errors and detect multi‑bit errors, increasing reliability in servers and critical computing. Optical discs (CDs, DVDs, Blu‑ray) rely on cross‑interleaved Reed–Solomon codes to handle scratches and dust. Satellite and deep‑space communications use concatenated schemes (e.g., Reed–Solomon plus convolutional codes) to reliably send data across vast distances with exceedingly low signal‑to‑noise ratios. Modern wireless standards, including 5G New Radio (NR), employ low‑density parity‑check (LDPC) codes for data channels and polar codes for control channels. The development of these codes has enabled the high‑speed, low‑error communication that underpins the internet, mobile telephony, and digital broadcasting.

Block Codes

Linear Block Codes

A block code divides the information sequence into fixed‑length blocks of \(k\) bits and encodes each block into a longer block of \(n\) bits (an \((n,k)\) code). A linear block code is one in which the sum (XOR) of any two codewords is also a codeword. This property makes encoding and decoding highly efficient, often using matrix multiplication. The code’s structure is described by a generator matrix \(G\) (for encoding) and a parity‑check matrix \(H\) (for syndrome decoding).

Hamming Codes

Hamming codes are a family of linear block codes with parameters \((2^r - 1, 2^r - r - 1, 3)\) for \(r \ge 2\). They achieve minimum distance 3 and can correct all single‑bit errors. Their parity‑check matrix consists of all non‑zero binary vectors of length \(r\) as columns. Because of their simplicity and perfect packing (they meet the Hamming bound), they are optimal single‑error‑correcting codes for their block lengths. The binary \((7,4)\) Hamming code is the most famous example.

Reed–Solomon Codes

Reed–Solomon codes are non‑binary linear block codes defined over finite fields (typically \(GF(2^m)\)). An \((n,k)\) RS code has length \(n = 2^m - 1\) and can correct up to \(\lfloor (n-k)/2 \rfloor\) symbol errors. The minimum distance is \(n - k + 1\), attaining the Singleton bound, making them maximum distance separable (MDS) codes. They are especially powerful against burst errors because a single symbol error affects several consecutive bits. RS codes are widely used in storage (CD, DVD, RAID 6) and communications (DSL, space probes).

Non‑linear Block Codes

Non‑linear block codes do not satisfy the linearity condition (sum of codewords may not be a codeword). While they can sometimes achieve better code parameters for a given length and rate than linear codes, they are harder to analyze and implement. Examples include some constant‑weight codes and codes used in specific applications like optical communications. In practice, linear codes dominate because of their algebraic structure and simpler decoding.

Cyclic Codes

A cyclic code is a linear block code with the additional property that any cyclic shift of a codeword is also a codeword. This cyclicity allows efficient encoding and syndrome computation using shift registers and polynomial algebra. Cyclic codes form the foundation for many important families, including BCH, Reed–Solomon (which are cyclic in a broader sense), and CRC codes.

BCH Codes

Bose–Chaudhuri–Hocquenghem (BCH) codes are a class of cyclic codes that generalize Hamming codes to multiple error correction. For any integers \(m\) and \(t\), a BCH code over \(GF(2^m)\) has length \(n = 2^m - 1\) and can correct up to \(t\) errors, with minimum distance at least \(2t+1\). Their algebraic decoding algorithm (the Berlekamp–Massey algorithm) is efficient and well‑studied. BCH codes are used in pagers, satellite communications, and as components of concatenated codes.

Convolutional Codes

Encoding with Shift Registers

Convolutional codes encode a continuous stream of information bits by passing them through a finite‑state machine built from shift registers and modulo‑2 adders. The code is characterized by parameters \((n, k, m)\), where \(k\) bits enter the encoder at each time step and \(n\) output bits are produced, and \(m\) is the memory (number of shift‑register stages). The outputs depend on the current input and the previous \(m\) bits, creating a convolutional relationship. Typical examples include rate‑1/2 codes with constraint length 7 (used in early deep‑space missions). Encoding is simple, but decoding requires more sophisticated algorithms.

Trellis Representation

A convolutional code can be visualized with a trellis diagram, which shows all possible state transitions over time. Each path through the trellis corresponds to a possible encoded sequence. The trellis structure is the basis for the Viterbi algorithm, which finds the most likely transmitted sequence given the received noisy signal. The number of states is \(2^{km}\), providing a trade‑off between error‑correction power and decoding complexity.

Modern Codes

Turbo Codes

Introduced in 1993 by Berrou, Glavieux, and Thitimajshima, turbo codes revolutionized coding theory by approaching the Shannon limit with practical decoders. A turbo encoder consists of two or more parallel recursive systematic convolutional (RSC) encoders separated by an interleaver. The decoder uses iterative soft‑decision exchange between the component decoders (using the maximum a posteriori (MAP) algorithm) to refine estimates. Turbo codes achieve excellent performance at low signal‑to‑noise ratios and are used in 3G/4G mobile communications, satellite links, and deep‑space missions.

Low‑Density Parity‑Check (LDPC) Codes

LDPC codes, invented by Robert Gallager in 1960 but only widely recognized in the 1990s, are linear block codes defined by a very sparse parity‑check matrix. They can be decoded efficiently using belief propagation (a message‑passing algorithm) on a bipartite (Tanner) graph. LDPC codes approach the Shannon limit closely, especially for long block lengths. They are now adopted in many standards, including Wi‑Fi (802.11n/ac/ax), 10GBase‑T Ethernet, DVB‑S2, and 5G NR.

Polar Codes

Polar codes, introduced by Erdal Arıkan in 2009, are the first class of codes proven to achieve the symmetric capacity of binary‑input memoryless channels under low‑complexity successive cancellation decoding. They are constructed by “polarizing” the channel into noiseless and purely noisy virtual channels through a recursive transformation. The encoder and decoder have O(N log N) complexity. Polar codes were selected for the control channel of 5G NR and are considered promising for future communication systems.

Hard‑Decision Decoding

Hard‑decision decoding treats the received signal as a sequence of bits (0 or 1) after a threshold decision. It is simple and fast but discards soft information available from the channel.

Syndrome Decoding

For linear block codes, the receiver computes the syndrome by multiplying the received vector by the transpose of the parity‑check matrix \(H\). If the syndrome is zero, no error is detected; otherwise, it indicates the error pattern. The syndrome uniquely determines the error location for single‑error‑correcting codes (e.g., Hamming codes). For multiple‑error‑correcting codes, syndrome decoding can involve lookup tables or algebraic algorithms (e.g., Berlekamp–Massey for BCH).

Majority‑Logic Decoding

Majority‑logic decoding is a simple method applicable to certain codes (e.g., Reed–Muller codes or some cyclic codes). Each parity check provides an estimate of a data bit; a majority vote among these estimates determines the most likely value. It is easy to implement in hardware but limited in power.

Soft‑Decision Decoding

Soft‑decision decoding uses reliability information (e.g., log‑likelihood ratios) from the channel, which improves error‑correction performance by about 2 dB compared to hard‑decision decoding. It is more complex but often essential for achieving near‑capacity performance.

Viterbi Algorithm (for Convolutional Codes)

The Viterbi algorithm is a dynamic programming method that finds the most likely path through the trellis of a convolutional code given a sequence of soft (or hard) input symbols. It uses branch metrics based on the received signal and accumulates path metrics (e.g., Hamming distance for hard decisions, squared Euclidean distance for soft). The algorithm outputs the decoded bit sequence corresponding to the path with the smallest accumulated metric. It has complexity linear in the sequence length but exponential in the constraint length, limiting its use to codes with moderate memory.

Belief Propagation (for LDPC Codes)

Belief propagation is a message‑passing algorithm that works on the Tanner graph of an LDPC code. Variable nodes and check nodes exchange probability messages (or log‑likelihood ratios) iteratively. After enough iterations, the algorithm produces soft estimates of each bit, which are then hardened. The algorithm converges quickly for well‑designed LDPC codes and is highly parallelizable. It is the standard decoder for LDPC codes.

Iterative Decoding (Turbo Decoding)

Turbo decoding involves two or more soft‑input soft‑output (SISO) decoders that work iteratively, exchanging extrinsic information. Each component decoder uses the MAP (or simplified Max‑Log‑MAP) algorithm to produce a refined estimate. The interleaver between decoders spreads errors and improves performance. Typically 6–12 iterations suffice; each iteration increases reliability. Turbo decoding is computationally intensive but provides performance within a fraction of a decibel of the Shannon limit.

Bounds on Decoding Complexity

The decoding complexity of a code depends on its structure and the algorithm used. For block codes, syndrome lookup tables have complexity \(O(2^{nk})\) for brute force, which is infeasible for large codes; algebraic decoding reduces this to polynomial time (e.g., \(O(n^2)\) for BCH). Convolutional codes with the Viterbi algorithm have complexity \(O(2^{km} L)\) for sequence length \(L\). LDPC decoders using belief propagation have complexity roughly \(O(n \log n)\) per iteration, while polar decoders (successive cancellation) have \(O(n \log n)\) complexity. The field of coding theory continues to seek algorithms that offer good error correction with manageable complexity for practical systems.

Error‑Detection and Error‑Correction Capability

For a code with minimum distance \(d_{\min}\):

• It can detect up to \(d_{\min}-1\) errors.
• It can correct up to \(\lfloor (d_{\min}-1)/2 \rfloor\) errors.
• It can simultaneously detect \(e\) errors and correct \(t\) errors if \(e + t < d_{\min}\) (for \(t \le e\)).

These capabilities are deterministic for bounded‑distance decoding. With list decoding or soft‑decision decoding, the actual performance can surpass these bounds under typical channel noise.

Sphere‑Packing Bound

The sphere‑packing bound (or Hamming bound) states that for an \((n,k)\) binary code with error‑correcting capability \(t\), the number of codewords must satisfy \[ 2^k \sum_{i=0}^t \binom{n}{i} \le 2^n. \] If equality holds, the code is perfect. Hamming codes are perfect for \(t=1\). The bound gives a limit on the maximum rate for a given error‑correction capability.

Gilbert–Varshamov Bound

The Gilbert–Varshamov bound provides a lower bound on the size of a code: there exists a code with length \(n\), minimum distance \(d\), and at least \[ 2^n \left/ \sum_{i=0}^{d-1} \binom{n}{i} \right. \] codewords. It guarantees the existence of codes with certain parameters, though not necessarily linear or easily decodable. It is often used to show that good codes exist asymptotically.

Coding Gain

Coding gain is the reduction in required signal‑to‑noise ratio (SNR) (or energy per bit) to achieve a given bit error rate (BER) when using an error‑correcting code compared to uncoded transmission. It is usually expressed in decibels (dB). For example, a (7,4) Hamming code provides about 0.5 dB coding gain at a BER of \(10^{-5}\), while a high‑rate LDPC code can yield several dB of gain. Coding gain is a key metric in system design, as it directly translates to improved link margin or reduced transmit power.

Bit Error Rate (BER) vs. Signal‑to‑Noise Ratio (SNR)

The performance of an error‑correcting code is typically characterized by a plot of BER (or packet error rate) versus SNR (often \(E_b/N_0\), energy per bit over noise power spectral density). Coded systems exhibit a steeper drop in BER as SNR increases compared to uncoded systems, demonstrating the code’s effectiveness. The waterfall region (where BER drops sharply) and the error floor (where performance flattens due to small minimum distance) are important features. For many modern codes, the waterfall region approaches the Shannon limit within 1 dB or less.

Channel Capacity and the Noisy‑Channel Coding Theorem

Claude Shannon’s noisy‑channel coding theorem (1948) states that for any discrete memoryless channel with capacity \(C\) (in bits per channel use), there exist codes of rate \(R &lt; C\) that can achieve arbitrarily small error probability with bounded decoding complexity (as block length increases). Conversely, for \(R &gt; C\), reliable communication is impossible. This theorem provides the fundamental theoretical limit for error‑correcting codes. The Shannon limit for a binary‑input AWGN channel (with BPSK modulation) is a key benchmark; modern codes like turbo and LDPC codes operate within 0.5–1 dB of this limit.

Trade‑Offs: Rate vs. Reliability

The code rate \(R = k/n\) is a measure of efficiency: lower rates add more redundancy, improving error correction but reducing throughput. Designers must balance the need for reliability against bandwidth or storage overhead. For example, a rate‑1/2 code doubles the transmission time but can provide high coding gain, while a rate‑7/8 code adds only ~14% overhead but offers limited correction. The choice depends on the channel quality, latency constraints, and system requirements.

Burst Errors and Interleaving

Many real‑world channels (e.g., fading radio, scratched discs) produce burst errors—clusters of consecutive bit errors. Block codes like Reed–Solomon are well suited to bursts because they operate on symbols. Convolutional codes also handle bursts moderately, but long bursts overwhelm them. Interleaving is a common technique to spread burst errors across multiple codewords, effectively randomizing them. The transmitter rearranges the order of bits (or symbols) before transmission; the receiver de‑interleaves to restore original order. This converts a burst of length \(L\) into single errors in \(L\) different codewords, which can then be corrected by the code. Interleaving is used in CD audio (CIRC), satellite TV, and digital video broadcasting.

Implementation in Hardware and Software

Error‑correcting codes must be implemented efficiently. Hardware implementations use dedicated logic (ASICs, FPGAs) for high‑speed operations like syndrome computation, Viterbi decoding, and belief propagation. These are found in network controllers, memory controllers, and baseband processors. Software implementations are used in applications where speed is less critical or where flexibility is needed (e.g., research, data storage systems). Modern libraries (e.g., Intel’s ISA‑L) provide optimized routines for Reed–Solomon, LDPC, and CRC codes. Decoding complexity is a major driver: for example, the Viterbi algorithm in hardware can achieve gigabits per second, while iterative turbo decoding may require multiple clock cycles per bit.

Standards and Real‑World Systems

Compact Disc (Cross‑Interleaved Reed–Solomon Code)

The compact disc (CD) uses the Cross‑Interleaved Reed–Solomon Code (CIRC), a two‑layer concatenated code. First, a (32,28) RS code corrects symbol errors, then a second (28,24) RS code, combined with two layers of interleaving, corrects bursts up to about 4000 bits (~2.5 mm of disc length). CIRC can correct up to 4000 bit errors and conceal up to 12,000 errors through interpolation, making CDs robust against scratches and dirt.

5G NR (LDPC and Polar Codes)

The 5G New Radio standard specifies LDPC codes for the data channel (physical downlink and uplink shared channels) and polar codes for the control channel (physical broadcast channel, downlink control information). LDPC codes offer flexible code rates and block lengths with excellent performance and parallel decoding. Polar codes provide capacity‑achieving performance for short block lengths with low‑complexity successive cancellation list decoding. This combination enables the high throughput and low latency required by 5G applications.

Deep‑Space Communications (Reed–Solomon + Convolutional)

Deep‑space probes (e.g., Voyager, Cassini, Mars rovers) have traditionally used a concatenated code: an outer Reed–Solomon (255,223) code (8‑bit symbols) and an inner convolutional code of rate 1/2 or 1/6, with interleaving. The outer code corrects burst errors that escape the inner Viterbi decoder. This combination, along with later turbo codes (used on the Mars Reconnaissance Orbiter), allows reliable communication over billions of kilometers with extremely low received signal power.