Error detection and correction: Difference between revisions

{{Short description|Reliable digital data delivery methods on unreliable channels}}

In classical antiquity, [[copyist]]s of the [[Hebrew Bible]] were paid for their work according to the number of [[Wiktionary:stich|stich]]s (lines of verse). As the prose books of the Bible were hardly ever written in stichs, the copyists, in order to estimate the amount of work, had to count the letters.<ref name="Jewish">{{cite encyclopedia |url=http://www.jewishencyclopedia.com/articles/10465-masorah |encyclopedia=Jewish Encyclopedia |article=Masorah}}</ref> This also helped ensure accuracy in the transmission of the text with the production of subsequent copies.<ref>{{cite book |last1=Pratico |first1=Gary D. |last2=Pelt |first2=Miles V. Van |title=Basics of Biblical Hebrew Grammar: Second Edition |date=2009 |publisher=Zondervan |isbn=978-0-310-55882-8 |url=https://books.google.com/books?id=p3FIoT0s3yYC&pg=PT448}}</ref><ref>{{cite book |last1=Mounce |first1=William D. |title=Greek for the Rest of Us: Using Greek Tools Without Mastering Biblical Languages |date=2007 |publisher=Zondervan |isbn=978-0-310-28289-1 |page=289 |url=https://books.google.com/books?id=AF-5ptJ0l2gC&pg=PA289}}</ref> Between the 7th and 10th centuries CE a [[Masoretes|group of Jewish scribes]] formalized and expanded this to create the [[Masoretic Text#Numerical Masorah|Numerical Masorah]] to ensure accurate reproduction of the sacred text. It included counts of the number of words in a line, section, book and groups of books, noting the middle stich of a book, word use statistics, and commentary.<ref name="Jewish" /> Standards became such that a deviation in even a single letter in a Torah scroll was considered unacceptable.<ref>[[Mishneh Torah]], Tefillin, Mezuzah, and Sefer Torah, 1:2. Example English translation: {{cite book |title=The Rambam's Mishneh Torah |author=Eliyahu Touger |publisher=Moznaim Publishing Corporation |url=https://www.chabad.org/library/article_cdo/aid/925417/jewish/Tefillin-Mezuzah-and-Sefer-Torah-Chapter-One.htm}}</ref> The effectiveness of their error correction method was verified by the accuracy of copying through the centuries demonstrated by discovery of the [[Dead Sea Scrolls]] in 1947–1956, dating from {{Circa|150 BCE&nbsp;–&nbsp;75 CE}}.<ref>{{cite book |author=Brian M. Fagan |title=The Oxford Companion to Archaeology |section=Dead Sea Scrolls |publisher=[[Oxford University Press]] |date=5 December 1996 |isbn=0195076184}}</ref>

All error-detection and correction schemes add some [[Redundancy (information theory)|redundancy]] (i.e., some extra data) to a message, which receivers can use to check consistency of the delivered message and to recover data that has been determined to be corrupted. Error detection and correction schemes can be either [[systematic code|systematic]] or non-systematic. In a systematic scheme, the transmitter sends the original (error-free) data and attaches a fixed number of ''check bits'' (or ''parity data''), which are derived from the data bits by some encoding algorithm. If error detection is required, a receiver can simply apply the same algorithm to the received data bits and compare its output with the received check bits; if the values do not match, an error has occurred at some point during the transmission. If error correction is required, a receiver can apply the decoding algorithm to the received data bits and the received check bits to recover the original error-free data. In a system that uses a non-systematic code, the original message is transformed into an encoded message carrying the same information, and that has at least as many bits as the original message.

If the channel characteristics cannot be determined or are highly variable, an error-detection scheme may be combined with a system for retransmission of erroneous data. This is known as [[automatic repeat request]] (ARQ), and is most notably used on the Internet. An alternate approach for error control is [[hybrid automatic repeat request]] (HARQ), which is a combination of ARQ and error-correction coding.

[[Shannon's theorem]] is an important theorem in forward error correction, and describes the maximum [[information rate]] at which reliable communication is possible over a channel that has a certain error probability or [[signal-to-noise ratio]] (SNR). This strict upper limit is expressed in terms of the [[channel capacity]]. More specifically, the theorem says that there exist codes such that with increasing encoding length the probability of error on a [[channel model|discrete memoryless channel]] can be made arbitrarily small, provided that the [[code rate]] is lower than the channel capacity. The code rate is defined as the fraction ''k/n'' of ''k'' source symbols and ''n'' encoded symbols.

Parity bits added to each ''word'' sent are called [[transverse redundancy check]]s, while those added at the end of a stream of ''words'' are called [[longitudinal redundancy check]]s.  For example, if each of a series of m-bit ''words'' has a parity bit added, showing whether there were an odd or even number of ones in that word, any word with a single error in it will be detected. It will not be known where in the word the error is, however. If, in addition, after each stream of n words a parity sum is sent, each bit of which shows whether there were an odd or even number of ones at that bit-position sent in the most recent group, the exact position of the error can be determined and the error corrected. This method is only guaranteed to be effective, however, if there are no more than 1 error in every group of n words.  With more error correction bits, more errors can be detected and, in some cases, corrected.

The development of error-correction codes was tightly coupled with the history of deep-space missions due to the extreme dilution of signal power over interplanetary distances and the limited power availability aboard space probes. Whereas early missions sent their data uncoded, starting in 1968, digital error correction was implemented in the form of (sub-optimally decoded) [[convolutional code]]s and [[Reed–Muller code]]s.<ref name="deep-space-codes">K. Andrews et al., ''The Development of Turbo and LDPC Codes for Deep-Space Applications'', Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.</ref> The Reed–Muller code was well suited to the noise the spacecraft was subject to (approximately matching a [[Gaussian function|bell curve]]), and was implemented for the Mariner spacecraft and used on missions between 1969 and 1977.

Error detection and correction codes are often used to improve the reliability of data storage media.<ref>{{Cite book|last1=Kurtas|first1=Erozan M.|title=Advanced Error Control Techniques for Data Storage Systems|last2=Vasic|first2=Bane|date=2018-10-03|publisher=CRC Press|isbn=978-1-4200-3649-7|language=en}}</ref>  A parity track capable of detecting single-bit errors was present on the first [[magnetic tape data storage]] in 1951. The [[optimal rectangular code]] used in [[group coded recording]] tapes not only detects but also corrects single-bit errors. Some [[file format]]s, particularly [[archive formats]], include a checksum (most often CRC-32]) to detect corruption and truncation and can employ redundancy or [[parity file]]s to recover portions of corrupted data. [[Reed-Solomon code]]s are used in [[compact disc]]s to correct errors caused by scratches.

  | url = https://bluesmoke.sourceforge.net/

[[Category:Error detection and correction]]

[[Category:Computer errors]]