Error_correction_code

# Error correction code An **error correction code** is a scheme for adding structured redundancy to a message before it crosses a noisy [[Communication_channel]], so that the receiver can find and fix a limited number of errors using the redundancy alone, without a return channel to request a retransmission. The technique is also called forward error correction, since the correcting power is built in ahead of time rather than negotiated after the fact, and it is the only option on a one-way broadcast link, a satellite far enough away that a retransmission request would cost minutes of round trip, or a link cheap enough in bandwidth that spending some of it on redundancy beats spending time on retries. The primary microsim on this page encodes short messages with the simplest widely used error correction code, sends them through a channel with an adjustable per-bit error rate, and shows, codeword by codeword, which ones survive unmarked, which are silently repaired, and which are too damaged to fix. Every scheme in the family trades bandwidth for reliability in the same basic way: more redundancy corrects more errors but leaves less of the channel for the message itself, and the central engineering question in [[Telecommunications]] is almost always where on that trade-off a given link should sit. Where [[Data_compression]] strips redundancy out of a message to shrink it, error correction puts controlled redundancy back in to protect it, and the two are routinely applied to the same data one after the other, compression first and coding last. ## Method ### Simplified formalism A code maps each possible k-bit message to one of a set of longer, n-bit codewords, chosen so that any two codewords differ in at least d positions, the code's minimum distance. Comparing a received, possibly corrupted word against every valid codeword and picking the nearest one — nearest meaning fewest differing bits, in the same best-match spirit as a [[Matched_filter]] picking out the strongest correlation — recovers the original message correctly provided no more than roughly half the minimum distance's worth of bits were flipped in transit: a code with minimum distance d detects up to d − 1 errors and corrects up to t = ⌊(d − 1)/2⌋ of them.[^ellrate] The redundant bits carry no information of their own; their entire purpose is to make the set of valid codewords sit far enough apart in this sense that a plausible pattern of channel errors cannot turn one valid codeword into another. ### Averaging noise to reduce errors The crudest possible code simply repeats each bit several times and lets the receiver take a majority vote, and in an analogue or soft-decision setting the same repetition can instead be averaged rather than voted on. Averaging N independent noisy copies of the same quantity is exactly the operation that gives [[Estimation_theory|a repeated measurement's sample mean]] a variance that falls as 1/N, so a repetition code is really parameter estimation in disguise: it buys reliability at a rate of only 1/N in bandwidth for a benefit that grows much more slowly, which is why practical codes replace blunt repetition with structured redundancy that spends the same extra bits far more efficiently. ## Types ### Block codes A block code processes a fixed-length k-bit message into a fixed-length n-bit codeword with no memory of earlier blocks. The clearest example, and the one the primary microsim implements, is the Hamming(7,4) code: four data bits are joined by three parity bits computed from overlapping subsets of them, giving a 7-bit codeword with minimum distance 3, invented by the American mathematician Richard Hamming and published in 1950.[^hamming50] A minimum distance of 3 guarantees correcting any single-bit error; a two-bit error also produces a nonzero syndrome, but a decoder that always trusts that syndrome will confidently flip some other bit and drift one bit further from the truth rather than safely flagging the failure, which is why a real design only relies on a distance-3 code up to its guaranteed one-error radius. A Hamming(7,4) codeword carries information at a code rate of 4/7 ≈ 0.571 — the fraction of every transmitted bit that actually carries message content. Reed–Solomon codes generalise the idea to symbols of several bits at once over a finite field rather than to single bits, which lets them correct a whole burst of adjacent bit errors as one damaged symbol; a Reed–Solomon code built from 5-bit symbols has at most n = 2⁵ − 1 = 31 symbols in a codeword, and choosing k = 15 message symbols leaves 2t = n − k = 16 parity symbols, correcting up to t = 8 damaged symbols anywhere in the block at a rate of 15/31 ≈ 0.48. ### Soft codes #### Low-density parity-check (LDPC) An LDPC code is defined by a parity-check matrix in which almost every entry is zero, a sparsity that makes an iterative, probabilistic decoding procedure practical even for very long codewords; the decoder passes soft, probability-weighted beliefs about each bit back and forth across the sparse structure rather than committing to hard 0/1 guesses along the way. Long LDPC codes, tens of thousands of bits per block, can come within about 1 dB of the Shannon limit for the channel they are designed against, closer than most classical block codes manage.[^ellrate] #### Turbo code A turbo code encodes the same data twice, through two simple convolutional encoders separated by an interleaver that scrambles the bit order between them, and decodes by passing soft estimates repeatedly between two matching decoders until they agree. First published in 1993, turbo codes were the first practical construction shown to approach the Shannon limit closely on a real channel, which is why the name stuck to the whole family of designs built around iterative soft-decision exchange.[^berrou93] ## Describing the performance of an ECC ### Code-rate and the tradeoff between reliability and data rate The reason any of this works at all traces to the American mathematician [[Claude_Shannon]], whose 1948 theorem showed that a noisy channel has a definite capacity below which codes exist that make the error rate as small as desired, and above which no code can help.[^shannon48] A code's rate, r = k/n, is not free to raise without cost: coding gain, the reduction in the [[Signal-to-noise_ratio|signal-to-noise ratio]] needed for a target error rate, generally grows as the rate falls and the redundancy grows. A BCH(63,45) code, for instance, has a rate of 0.714 and lowers the signal-to-noise ratio needed for a bit-error rate of one in a million from about 11 dB to about 8 dB uncoded, a coding gain of roughly 3 dB — but the same code can make matters worse rather than better once the channel is already noisier than about 6 dB, because at low enough signal-to-noise ratio a decoder trying to correct more errors than the code can actually handle introduces new ones faster than it removes old ones.[^ellrate] Choosing a code is therefore choosing a point on this curve to suit the channel actually expected, not simply choosing the strongest code available. ## Local decoding and testing of codes A locally decodable code allows the receiver to recover any single symbol of the original message by reading only a small, sub-linear number of positions in a possibly corrupted codeword, rather than decoding the whole thing, which matters when the codeword is enormous, as in distributed storage, and only a small piece of the message is wanted at any one time. A related idea, local testability, allows a checker to decide with high confidence whether a received string is close to some valid codeword, in the spirit of [[Detection_theory]], by reading only a handful of positions, without ever running a full decoder; both properties trade some of the ordinary tools' fixed decoding cost against a codeword's structure, and both are active research areas in theoretical computer science and [[Information_theory]] rather than settled engineering practice. ## Improving performance ### Concatenation (combination) Two codes can be layered so that an outer code, often a Reed–Solomon code well suited to correcting whole damaged symbols, wraps an inner code, often a [[Convolution|convolutional]] code decoded with a Viterbi-style algorithm well suited to correcting scattered single-bit errors; each stage cleans up the kind of error the other stage tends to leave behind, at a decoding complexity far below what a single code of equivalent strength would need.[^forney66] ### Interleaving #### Interleaving example Interleaving does not add redundancy; it rearranges it. A 7-by-5 block interleaver, for instance, writes 35 coded bits into the block by rows and reads them out by columns, so that a burst of channel noise, which typically damages a run of consecutive transmitted bits, ends up scattered across many different, separately correctable codewords once the receiver reverses the shuffle; at a 10 kb/s data rate a 10-millisecond frame carries on the order of 100 bits, so only a few such blocks are needed to cover one frame.[^ellinterleave] A code like Hamming(7,4), built to correct one isolated bit error per codeword, can then handle a whole burst that interleaving has spread thin enough to look like several separate single-bit errors. #### Disadvantages of interleaving The rearrangement is not free. A receiver cannot begin decoding until it has buffered a full interleaver block, so interleaving adds a delay roughly proportional to the block's span, which can be the deciding constraint against it on a real-time voice or control link. It also does nothing for a channel whose errors are already spread uniformly at random rather than clustered into bursts, since there is no burst structure left for the shuffle to break up. ## Software for error-correcting codes Encoding and decoding algorithms exist as libraries in most general-purpose programming languages, useful for research, simulation and low-rate applications, but a link running continuously at a high data rate more often implements its error correction in dedicated [[Digital_signal_processing]] hardware — logic built into a modem chipset, a memory controller, or a storage drive's controller — because encoding and decoding must keep up with every bit that crosses the link and a general-purpose processor running ordinary software is usually the slower, more power-hungry way to do that at scale. More recently, decoders built from [[Neural_network|neural networks]] have been explored for codes whose exact optimal decoding is otherwise computationally expensive, blurring the historical line between classical algebraic decoding and learned, approximate decoding. ## List of error-correcting codes The families in practical use differ mainly in what kind of error they are built to catch and how they trade decoding complexity for coding gain. | Family | Redundancy structure | Best suited to | |---|---|---| | Repetition code | Whole message repeated N times | Extremely simple, very noisy or very short links | | Hamming code | Parity bits over overlapping bit subsets | Single-bit errors in short blocks | | BCH code | Algebraic, over a finite field | A chosen number of bit errors per block | | Reed–Solomon code | Algebraic, symbol- rather than bit-based | Burst errors, damaged storage media | | Convolutional code | Continuous, decoded with Viterbi-style search | Streaming data, deep-space and satellite links | | LDPC code | Sparse parity-check matrix, iterative decoding | Very long blocks operating near the Shannon limit | | Turbo code | Two interleaved convolutional codes | Mobile and satellite links needing near-capacity performance | ## Microsims The primary sketch encodes a stream of 4-bit messages with the Hamming(7,4) code shown above, sends each 7-bit codeword through a channel that flips every bit independently with a probability the reader sets, and computes the syndrome the receiver would use to locate and flip back a single damaged bit. Each codeword animates across the canvas labelled with the outcome the syndrome finds: no error, a one-bit error corrected, naming the position fixed, or, when two or more bits were flipped in the same codeword, an uncorrectable error the code can only report. Controls set the per-bit error probability from 0 to 30 percent, default 8 percent, and the animation speed. The sketch labels any codeword the channel damages in two or more bits "uncorrectable" using the actual number of flips the channel applied, rather than running the decoder's own blind correction through to its confidently wrong answer in that case. ILLUSTRATIVE. *Try:* Leave the error rate at its default of 8 percent and watch most codewords arrive clean or be silently repaired; then push the slider toward its maximum of 30 percent and watch two-bit errors start turning up as the sketch's own "uncorrectable" flag, exactly where the code's minimum distance of 3 predicts a single correction can no longer be trusted. A three.js companion built on the [[Error_detection_and_correction]] sketch renders the same Hamming(7,4) geometry directly, the minimum distance of 3 that guarantees one corrected error and no more. ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Error_correction_code) : [Wikitube](https://en.wikitube.io/wiki/Error_correction_code) Skeleton mirrored at revision 1362628481. Prose, emphasis and the microsims are Wikitube's own. ## See also - [[Communication_channel]] - [[Error_detection_and_correction]] - [[Claude_Shannon]] - [[Detection_theory]] - [[Estimation_theory]] - [[Matched_filter]] - [[Digital_signal_processing]] - [[Information_theory]] - [[Radar]] - [[Signal-to-noise_ratio]] ## References [^shannon48]: Shannon, C. E. "A Mathematical Theory of Communication." *Bell System Technical Journal*, vol. 27, 1948, pp. 379–423, 623–656. [^ellrate]: Ellingson, S. *Radio Systems Engineering - Revised First Edition*. 2023, pp. 162–163 (PDF pages). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/radio-systems-engineering . CC BY-NC. [^hamming50]: Hamming, R. W. "Error Detecting and Error Correcting Codes." *Bell System Technical Journal*, vol. 29, no. 2, 1950, pp. 147–160. [^berrou93]: Berrou, C.; Glavieux, A.; Thitimajshima, P. "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes." *Proceedings of the IEEE International Conference on Communications (ICC)*, 1993, pp. 1064–1070. [^forney66]: Forney, G. D. *Concatenated Codes*. MIT Press, 1966. [^ellinterleave]: Ellingson, S. *Radio Systems Engineering - Revised First Edition*. 2023, pp. 165–166 (PDF pages). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/radio-systems-engineering . CC BY-NC. ## Further reading - Ellingson, S. *Radio Systems Engineering - Revised First Edition* (2023). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/radio-systems-engineering - Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory* (2026). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory - Stiber, M.; Stiber, B.; Larson, E. *Signal Computing: Digital Signals in the Software Domain* (2020). Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/signal-computing-digital-signals-in-the-software-domain ## External links - [Live sketch: Forward error correction](https://editor.p5js.org/sciencenibber/full/AC_WC5JTt) - [Editor (fork)](https://editor.p5js.org/sciencenibber/sketches/AC_WC5JTt)