Error correction code: Difference between revisions

Revision as of 05:21, 2 July 2023

Latest revision as of 18:16, 25 August 2025

(38 intermediate revisions by 24 users not shown)

Line 4:

In [[computing]], [[telecommunication]], [[information theory]], and [[coding theory]], '''forward error correction''' ('''FEC''') or '''channel coding'''<ref>{{cite journal |author1=Charles Wang |author2=Dean Sklar |author3=Diana Johnson |title=Forward Error-Correction Coding |journal=Crosslink |publisher=The Aerospace Corporation |volume=3 |issue=1 |date=Winter 2001–2002 |url=http://www.aero.org/publications/crosslink/winter2002/04.html |access-date=5 March 2006 |archive-url=https://web.archive.org/web/20120314085127/http://www.aero.org/publications/crosslink/winter2002/04.html |archive-date=14 March 2012 |url-status=dead }}</ref><ref>{{cite journal |author1=Charles Wang |author2=Dean Sklar |author3=Diana Johnson |title=Forward Error-Correction Coding |journal=Crosslink |publisher=The Aerospace Corporation |volume=3 |issue=1 |date=Winter 2001–2002 |url=http://www.aero.org/publications/crosslink/winter2002/04_sidebar1.html | quote=How Forward Error-Correcting Codes Work] |access-date=5 March 2006 |archive-url=https://web.archive.org/web/20120314085127/http://www.aero.org/publications/crosslink/winter2002/04_sidebar1.html |archive-date=14 March 2012 |url-status=dead }}</ref><ref name=":0">{{Cite web|url=https://www.accelercomm.com/overview-channel-coding|title=Overview of Channel Coding|last=Maunder|first=Robert|date=2016}}</ref> is a technique used for [[error control|controlling errors]] in [[data transmission]] over unreliable or noisy [[communication channel]]s.

The central idea is that the sender encodes the message in a [[Redundancy (information theory)|redundant]] way, most often by using an '''error correction code''', or '''error correcting code''', ('''ECC''').<ref>{{cite book |author-last1=Glover |author-first1=Neal |author-last2=Dudley |author-first2=Trent |title=Practical Error Correction Design For Engineers |edition=Revision 1.1, 2nd |publisher=[[Cirrus Logic]] |___location=CO, USA |date=1990 |isbn=0-927239-00-0 }}</ref><ref name="Hamming">{{cite journal |author-last=Hamming |author-first=Richard Wesley |author-link=Richard Wesley Hamming |title=Error Detecting and Error Correcting Codes |journal=[[Bell System Technical Journal]] |volume=29 |issue=2 |pages=147–160 |publisher=[[AT&T]] |___location=USA |date=April 1950 |doi=10.1002/j.1538-7305.1950.tb00463.x|s2cid=61141773 |hdl=10945/46756 |hdl-access=free }}</ref> The redundancy allows the receiver not only to [[error detection|detect errors]] that may occur anywhere in the message, but often to correct a limited number of errors. Therefore a [[reverse channel]] to request re-transmission may not be needed. The cost is a fixed, higher forward channel bandwidth.

The American mathematician [[Richard Hamming]] pioneered this field in the 1940s and invented the first error-correcting code in 1950: the [[Hamming (7,4) code]].<ref name="Hamming"/>

FEC can be applied in situations where re-transmissions are costly or impossible, such as one-way communication links or when transmitting to multiple receivers in [[multicast]].

Long-latency connections also benefit; in the case of a satellitesatellites orbiting [[Uranus]]distant planets, retransmission due to errors canwould create a delay of fiveseveral hours. FEC is also widely used in [[modem]]s and in [[cellular network]]s, as well.

FEC processing in a receiver may be applied to a digital bit stream or in the demodulation of a digitally modulated carrier. For the latter, FEC is an integral part of the initial [[Analog-to-digital converter|analog-to-digital conversion]] in the receiver. The [[Viterbi decoder]] implements a [[Soft-decision decoder|soft-decision algorithm]] to demodulate digital data from an analog signal corrupted by noise. Many FEC decoders can also generate a [[bit-error rate]] (BER) signal which can be used as feedback to fine-tune the analog receiving electronics.

Line 15 ⟶ 16:

FEC information is added to [[mass storage]] (magnetic, optical and solid state/flash based) devices to enable recovery of corrupted data, and is used as [[ECC memory|ECC]] [[computer memory]] on systems that require special provisions for reliability.

The maximum proportion of errors or missing bits that can be corrected is determined by the design of the ECC, so different forward error correcting codes are suitable for different conditions. In general, a stronger code induces more redundancy that needs to be transmitted using the available bandwidth, which reduces the effective bit-rate while improving the received effective [[signal-to-noise ratio]]. The [[noisy-channel coding theorem]] of [[Claude Shannon]] can be used to compute the maximum achievable communication bandwidth for a given maximum acceptable error probability. This establishes bounds on the theoretical maximum information transfer rate of a channel with some given base noise level. However, the proof is not constructive, and hence gives no insight of how to build a capacity achieving code. After years of research, some advanced FEC systems like [[Polar code (coding theory)|polar code]]<ref name=":0" /> come very close to the theoretical maximum given by the Shannon channel capacity under the hypothesis of an infinite length frame.

==Method==

ECC is accomplished by adding [[redundancy (information theory)|redundancy]] to the transmitted information using an algorithm. A redundant bit may be a complicated function of many original information bits. The original information may or may not appear literally in the encoded output; codes that include the unmodified input in the output are '''[[systematic code|systematic]]''', while those that do not are '''non-systematic'''.

A simplistic example of ECC is to transmit each data bit 3three times, which is known as a (3,1) [[repetition code]]. Through a noisy channel, a receiver might see 8eight versions of the output, see table below.

{| class=wikitable

Line 51 ⟶ 52:

|}

This allows an error in any one of the three samples to be corrected by "majority vote", or "democratic voting". The correcting ability of this ECC is:

* Up to 1one bit of triplet in error, or

* up to 2two bits of triplet omitted (cases not shown in table).

Though simple to implement and widely used, this [[triple modular redundancy]] is a relatively inefficient ECC. Better ECC codes typically examine the last several tens or even the last several hundreds of previously received bits to determine how to decode the current small handful of bits (typically in groups of 2two to 8eight bits).

==Averaging noise to reduce errors==

Line 65 ⟶ 66:

[[adaptive modulation and coding]] uses a variety of ECC rates, adding more error-correction bits per packet when there are higher error rates in the channel, or taking them out when they are not needed.

==Types of ECC==

{{Main|Block code|Convolutional code}}

[[File:Block code error correction.png|thumb|upright=1.3|A block code (specifically a [[Hamming code]]) where redundant bits are added as a block to the end of the initial message]]

[[File:Convolutional code error correction.png|thumb|A continuous code [[convolutional code]] where redundant bits are added continuously into the structure of the code word]]

The two main categories of ECC codes are [[block code]]s and [[convolutional code]]s.

Line 77 ⟶ 78:

There are many types of block codes; [[Reed–Solomon error correction|Reed–Solomon coding]] is noteworthy for its widespread use in [[compact disc]]s, [[DVD]]s, and [[hard disk drive#Error rates and handling|hard disk drives]]. Other examples of classical block codes include [[Golay code (disambiguation)|Golay]], [[BCH code|BCH]], [[Multidimensional parity-check code|Multidimensional parity]], and [[Hamming code]]s.

Hamming ECC is commonly used to correct [[ECC memory]] and early SLC [[NAND flash]] memory errors.<ref>[http://www.eetasia.com/ART_8800575062_499486_AN_7549c493.HTM "Hamming codes for NAND flash memory devices"] {{Webarchive|url=https://web.archive.org/web/20160821122453/http://www.eetasia.com/ART_8800575062_499486_AN_7549c493.HTM |date=21 August 2016 }}. EE Times-Asia. Apparently based on [http://www.micron.com/~/media/Documents/Products/Technical%20Note/NAND%20Flash/tn2908_NAND_hamming_ECC_code.pdf "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices"] {{Webarchive|url=https://web.archive.org/web/20170829073235/http://www.micron.com/~/media/Documents/Products/Technical%20Note/NAND%20Flash/tn2908_NAND_hamming_ECC_code.pdf |date=29 August 2017 }}. 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications."</ref>

This provides single-bit error correction and 2-bit error detection.

Hamming codes are only suitable for more reliable [[single-level cell]] (SLC) NAND.

Denser [[multi-level cell]] (MLC) NAND may use multi-bit correcting ECC such as [[BCH orcode|BCH]], Reed–Solomon, or [[Low-density parity-check code|LDPC]].<ref name="spansion">{{cite web|url=http://www.spansion.com/Support/Application%20Notes/Types_of_ECC_Used_on_Flash_AN.pdf|title =What Types of ECC Should Be Used on Flash Memory?|publisher=Spansion|format=Application note|year=2011|quote=Both Reed–Solomon algorithm and BCH algorithm are common ECC choices for MLC NAND flash. ... Hamming based block codes are the most commonly used ECC for SLC.... both Reed–Solomon and BCH are able to handle multiple errors and are widely used on MLC flash.}}</ref><ref>{{cite web|author=Jim Cooke|url=https://cushychicken.github.io/assets/cooke_inconvenient_truths.pdf |title=The Inconvenient Truths of NAND Flash Memory|date=August 2007|page=28|quote=For SLC, a code with a correction threshold of 1 is sufficient. t=4 required ... for MLC.}}</ref><ref>https://www.thinkmind.org/articles/icons_2015_5_20_40055.pdf {{Bare URL PDF|date=July 2025}}</ref> NOR Flashflash typically does not use any error correction.<ref name="spansion"/>

Classical block codes are usually decoded using '''hard-decision''' algorithms,<ref>{{cite journal |author-last1=Baldi |author-first1=M. |author-last2=Chiaraluce |author-first2=F. |title=A Simple Scheme for Belief Propagation Decoding of BCH and RS Codes in Multimedia Transmissions |journal=[[International Journal of Digital Multimedia Broadcasting]] |volume=2008 |pages=1–12 |date=2008 |doi=10.1155/2008/957846 |doi-access=free }}</ref> which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using '''soft-decision''' algorithms like the Viterbi, MAP or [[BCJR algorithm|BCJR]] algorithms, which process (discretized) analog signals, and which allow for much higher error-correction performance than hard-decision decoding.

Line 88 ⟶ 89:

In contrast to classical block codes that often specify an error-detecting or error-correcting ability, many modern block codes such as [[LDPC codes]] lack such guarantees. Instead, modern codes are evaluated in terms of their bit error rates.

Most [[forward error correction]] codes correct only bit-flips, but not bit-insertions or bit-deletions.

In this setting, the [[Hamming distance]] is the appropriate way to measure the [[bit error rate]].

A few forward error correction codes are designed to correct bit-insertions and bit-deletions, such as Marker Codes and Watermark Codes.

Line 102 ⟶ 103:

One interesting question is the following: how efficient in terms of information transfer can an ECC be that has a negligible decoding error rate? This question was answered by Claude Shannon with his second theorem, which says that the channel capacity is the maximum bit rate achievable by any ECC whose error rate tends to zero:<ref name="shannon paper">{{cite journal|first=C. E.|last=Shannon|title=A mathematical theory of communication|journal=[[Bell System Technical Journal]]|volume=27|issue=3–4|pages=379–423 & 623–656|date=1948|url=http://www.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf|doi=10.1002/j.1538-7305.1948.tb01338.x|hdl=11858/00-001M-0000-002C-4314-2|hdl-access=free}}</ref> His proof relies on Gaussian random coding, which is not suitable to real-world applications. The upper bound given by Shannon's work inspired a long journey in designing ECCs that can come close to the ultimate performance boundary. Various codes today can attain almost the Shannon limit. However, capacity achieving ECCs are usually extremely complex to implement.

The most popular ECCs have a trade-off between performance and computational complexity. Usually, their parameters give a range of possible code rates, which can be optimized depending on the scenario. Usually, this optimization is done in order to achieve a low decoding error probability while minimizing the impact to the data rate. Another criterion for optimizing the code rate is to balance low error rate and retransmissions number in order to the energy cost of the communication.<ref>{{Cite conference |title=Optimizing the code rate for achieving energy-efficient wireless communications |first1=F. |last1=Rosas |first2=G. |last2=Brante |first3=R. D. |last3=Souza |first4=C. |last4=Oberli |url=https://ieeexplore.ieee.org/document/6952166 |date=2014 |pages=775–780 |doi=10.1109/WCNC.2014.6952166 |isbn=978-1-4799-3083-8 |book-title=Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC)}}</ref>

==Concatenated ECC codes for improved performance==

Line 133 ⟶ 134:

[[Locally decodable code]]s are error-correcting codes for which single bits of the message can be probabilistically recovered by only looking at a small (say constant) number of positions of a codeword, even after the codeword has been corrupted at some constant fraction of positions. [[Locally testable code]]s are error-correcting codes for which it can be checked probabilistically whether a signal is close to a codeword by only looking at a small number of positions of the signal.

Not all locally decodable codes (LDCs) are locally testable codes (LTCs)<ref name="decNotTest">{{cite web |last1=Kaufman |first1=Tali |author1-link=Tali Kaufman |last2=Viderman |first2=Michael |title=Locally Testable vs. Locally Decodable Codes |url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/}}</ref> neither locally correctable codes (LCCs),<ref>{{Cite web |last=Brubaker |first=Ben |date=2024-01-09 |title='Magical' Error Correction Scheme Proved Inherently Inefficient |url=https://www.quantamagazine.org/magical-error-correction-scheme-proved-inherently-inefficient-20240109/ |access-date=2024-01-09 |website=Quanta Magazine |language=en}}</ref> q-query LCCs are bounded exponentially<ref>{{Cite arXiv |last1=Kothari |first1=Pravesh K. |last2=Manohar |first2=Peter |date=2023 |title=An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes |class=cs.CC |eprint=2311.00558}}</ref><ref>{{Cite book |last1=Kerenidis |first1=Iordanis |last2=de Wolf |first2=Ronald |chapter=Exponential lower bound for 2-query locally decodable codes via a quantum argument |date=2003-06-09 |title=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing |chapter-url=https://dl.acm.org/doi/10.1145/780542.780560 |language=en |publisher=ACM |pages=106–115 |doi=10.1145/780542.780560 |arxiv=quant-ph/0208062 |isbn=978-1-58113-674-6|s2cid=10585919 }}</ref> while LDCs can have [[Subexponential time|subexponential]] lengths.<ref>{{Cite journal |last=Yekhanin |first=Sergey |date=February 2008 |title=Towards 3-query locally decodable codes of subexponential length |url=https://dl.acm.org/doi/10.1145/1326554.1326555 |journal=Journal of the ACM |language=en |volume=55 |issue=1 |pages=1–16 |doi=10.1145/1326554.1326555 |s2cid=14617710 |issn=0004-5411|url-access=subscription }}</ref><ref>{{Cite book |last=Efremenko |first=Klim |chapter=3-query locally decodable codes of subexponential length |date=2009-05-31 |title=Proceedings of the forty-first annual ACM symposium on Theory of computing |chapter-url=https://dl.acm.org/doi/10.1145/1536414.1536422 |journal=[[Journal of the ACM]] |language=en |publisher=ACM |pages=39–44 |doi=10.1145/1536414.1536422 |isbn=978-1-60558-506-2|s2cid=263865692 }}</ref>

== Interleaving ==

{{redirect|Interleaver|the fiber-optic device|optical interleaver}}

[[File:Interleaving1.png|right|upright=2.25|thumb|A short illustration of the interleaving idea]]

Interleaving is frequently used in digital communication and storage systems to improve the performance of forward error correcting codes. Many [[communication channel]]s are not memoryless: errors typically occur in [[burst error|burst]]s rather than independently. If the number of errors within a [[Code word (communication)|code word]] exceeds the error-correcting code's capability, it fails to recover the original code word. Interleaving alleviates this problem by shuffling source symbols across several code words, thereby creating a more [[Uniform distribution (continuous)|uniform distribution]] of errors.<ref name="turbo-principles">{{cite book |author-first1=B. |author-last1=Vucetic |author-first2=J. |author-last2=Yuan |title=Turbo codes: principles and applications |publisher=[[Springer Verlag]] |isbn=978-0-7923-7868-6 |date=2000}}</ref> Therefore, interleaving is widely used for [[burst error-correcting code|burst error-correction]].

The analysis of modern iterated codes, like [[turbo code]]s and [[LDPC code]]s, typically assumes an independent distribution of errors.<ref>{{cite journal |author-first1=Michael |author-last1=Luby |author-link1=Michael Luby |author-first2=M. |author-last2=Mitzenmacher |author-first3=A. |author-last3=Shokrollahi |author-first4=D. |author-last4=Spielman |author-first5=V. |author-last5=Stemann |title=Practical Loss-Resilient Codes |journal=Proc. 29th Annual Association for Computing Machinery (ACM) Symposium on Theory of Computation |date=1997}}</ref> Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.<ref>{{Cite journal |title=Digital Video Broadcast (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other satellite broadband applications (DVB-S2) |journal=En 302 307 |issue=V1.2.1 |publisher=[[ETSI]] |date=April 2009}}</ref>

Line 210 ⟶ 213:

| 3 (single-error correcting) || [[Triple modular redundancy]]

|-

| 3 (single-error correcting) || perfectPerfect Hamming such as [[Hamming(7,4)]]

|-

| 4 ([[SECDED]]) || Extended Hamming

Line 218 ⟶ 221:

| 6 (double-error correct-/triple error detect) || [[Nordstrom-Robinson code]]

|-

| 7 (three-error correcting) || perfectPerfect [[binary Golay code]]

|-

| 8 (TECFED) || extendedExtended [[binary Golay code]]

|}

Line 256 ⟶ 259:

* [[Turbo code]]

* [[Walsh–Hadamard code]]

* [[Cyclic redundancy check]]s (CRCs) can correct 1-bit errors for messages at most <math>2^{n-1}-1</math> bits long for optimal generator polynomials of degree <math>n</math>, see [[{{section link|Mathematics of cyclic redundancy checks#|Bitfilters]]}}

* [[Locally Recoverable Codes]]

* [[Message authentication code]]

==See also==

* [[Burst error-correcting code]]

* [[Code rate]]

* [[Erasure code]]s

* [[Soft-decision decoder]]

* [[Burst error-correcting code]]

* [[Error detection and correction]]

* [[Error-correcting codes with feedback]]

* [[Linear code]]

* [[Quantum error correction]]

* [[Soft-decision decoder]]

==References==

Line 280 ⟶ 285:

* [https://web.archive.org/web/20160304050018/http://www.eetasia.com/ARTICLES/2004NOV/A/2004NOV29_MEM_AN10.PDF?SOURCES=DOWNLOAD "Error Correction Code in NAND Flash memories"] 2004-11-29

* [http://perspectives.mvdirona.com/2012/02/observations-on-errors-corrections-trust-of-dependent-systems/ Observations on Errors, Corrections, & Trust of Dependent Systems], by James Hamilton, 2012-02-26

* ''[[Sphere Packings, Lattices and Groups]],'' Byby J. H. Conway, Neil James Alexander Sloane, [[Springer Science & Business Media]], 2013-03-09 – Mathematics – 682 pages.

==External links==

* {{Cite web |author-last=Morelos-Zaragoza |author-first=Robert |date=2004 |url=http://www.eccpage.com/ |title=The Correcting Codes (ECC) Page |access-date=2006-03-05}}

* [https://errorcorrectionzoo.org/ error correction zoo]. Database of error correcting codes.

* [https://github.com/supermihi/lpdec lpdec: library for LP decoding and related things (Python)]