|
In computer science and information theory, the issue of error correction and detection has great practical importance. Error detection is the ability to detect errors that are made due to noise or other impairments in the course of the transmission from the transmitter to the receiver. Error correction has the additional feature that enables localization of the errors and correcting them. Given the goal of error correction, the idea of error detection may seem to be insufficient. However, error-correction schemes may be computationally intensive, or require excessive redundant data which may be inhibitive for a certain application. Error correction in some applications, such as a sender-receiver system, can be achieved with only a detection system in tandem with an automatic repeat request scheme to notify the sender that a portion of the data sent was received incorrectly and will need to be retransmitted, however where efficiency is important, it is possible to detect and correct errors with far less redundant data. Wikipedia does not have an article with this exact name. ...
It has been suggested that this article or section be merged with Error correction and detection. ...
Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
ARQ is an acronym for: Automatic Repeat-reQuest. ...
Typical schemes Several schemes exist to achieve error detection, and are generally quite simple.
Repetition schemes Variations on this theme exist. Given a stream of data that is to be sent, the data is broken up into blocks of bits, and in sending, each block is sent some predetermined number of times. For example, if we want to send "1011", we may repeat this block three times each.
Suppose we send "1011 1011 1011", and this is received as "1010 1011 1011". As one group is not the same as the other two, we can determine that an error has occurred. This scheme is not very efficient, and can be susceptible to problems if the error occurs in exactly the same place for each group (e.g. "1010 1010 1010" in the example above will be detected as correct in this scheme).
The scheme however is extremely simple, and is in fact used in some transmissions of numbers stations. Numbers stations are shortwave radio stations of uncertain origin. ...
Parity schemes - Main article: Parity bit
Given a stream of data that is to be sent, the data is broken up into blocks of bits, and the number of 1 bits is counted. Then, a "parity bit" near the block is set or cleared if the number of one bits is odd or even. If the tested blocks overlap, then the parity bits can be used to isolate the error, and even correct it if the error is isolated to one bit: This is the principle of the Hamming code. In computing and telecommunication, a parity bit is a binary digit that indicates whether the number of 1 bits in the preceding data was even or odd. ...
In telecommunication, a Hamming code is an error-correcting code named after its inventor, Richard Hamming. ...
There is a limitation to parity schemes. A parity bit is only guaranteed to detect single bit errors. If two or more bits have an error, the parity bit can record the correct number of ones, even though the data is corrupt.
Cyclic redundancy checks - Main article: Cyclic redundancy check
Many more complex error detection (and correction) methods make use of the properties of finite fields and polynomials over such fields. A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum - which is a small, fixed number of bits - against a block of data, such as a packet of network traffic or a block of a computer file. ...
The cyclic redundancy check considers a block of data as the coefficients to a polynomial and then divides by a fixed, predetermined polynomial. The coefficients of the result of the division is taken as the redundant data bits, the CRC.
- Checking the received data can be achieved by multiplying the predetermined polynomial by the CRC.
- If this is the same as the payload data, then the data has been received without error.
- Alternatively, one can recompute the CRC from the payload bits and compare the CRC with the CRC that has been received.
Error correction
The above methods are sufficient to determine whether some data has been received in error. But often, this is not enough. Consider an application such as simplex teletype over radio (SITOR). If a message needs to be received quickly and needs to be complete without error, merely knowing where the errors occurred may not be enough, the second condition is not satisfied as the message will be incomplete. Suppose then the receiver waits for a message to be repeated (since the situation is simplex), the first condition is not satisfied since the receiver will have to wait (possibly a long time) for the message to be repeated to fill the gaps left by the errors. In geometry, a simplex (plural: simplices) or n-simplex is an n-dimensional analogue of a triangle. ...
SITOR (simplex teletype over radio) is a transmission mode used to transmit textual messages akin to regular radioteletype (RTTY), but implements simple error correction. ...
It would be advantageous if the receiver could somehow determine what the error was and thus correct it. Is this even possible? Yes, consider the NATO phonetic alphabet -- if a sender were to be sending the word "WIKI" with the alphabet by sending "WHISKEY INDIA KILO INDIA" and this was received (with * signifying letters received in error) as "W***KEY I**I* **LO **DI*", it would be possible to correct all the errors here since there is only one word in the NATO phonetic alphabet which starts with "W" and ends in "KEY", and similarly for the other words. This idea is also present in some error correcting codes (ECC). FAA radiotelephony phonetic alphabet and Morse code chart. ...
Error-correcting schemes also have their limitations. Some can correct a certain number of bit errors and only detect further numbers of bit errors. Codes which can correct one error are termed single error correcting (SEC), and those which detect two are termed double error detecting (DED). There are codes which can correct and detect more errors than these.
Applications
The Internet In a typical TCP/IP stack, error detection is performed at multiple levels: The Internet protocol suite is the set of communications protocols that implement the protocol stack on which the Internet runs. ...
- Each Ethernet frame carries a CRC-32 checksum. The receiver discards frames if their checksums don't match.
- The IPv4 header contains a header checksum of the contents of the header (excluding the checksum field). Packets with checksums that don't match are discarded.
- The checksum was omitted from the IPv6 header, because most current link layer protocols have error detection.
- UDP has an optional checksum. Packets with wrong checksums are discarded.
- TCP has a checksum of the payload, TCP header (excluding the checksum field) and source- and destination addresses of the IP header. Packets found to have incorrect checksums are discarded and eventually get retransmitted when the sender receives a triple-ack or a time-out occurs.
Ethernet is a frame-based computer networking technology for local area networks (LANs). ...
In telecommunications, a frame is a packet which has been encoded for transmission over a particular link. ...
A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum - which is a small, fixed number of bits - against a block of data, such as a packet of network traffic or a block of a computer file. ...
A checksum is a form of redundancy check, a very simple measure for protecting the integrity of data by detecting errors in data that is sent through space (telecommunications) or time (storage). ...
IPv4 is version 4 of the Internet Protocol (IP) and it is the first version of the Internet Protocol to be widely deployed. ...
A packet is the fundamental unit of information carriage in all modern computer networks. ...
Internet Protocol version 6 (IPv6) is a network layer standard used by electronic devices to exchange data across a packet-switched internetwork. ...
The data link layer is level two of the seven-level OSI model. ...
The User Datagram Protocol (UDP) is one of the core protocols of the Internet protocol suite. ...
The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite. ...
The TCP uses various variations of an additive-increase-multiplicative-decrease (AIMD) scheme, with other schemas such as slow-start in order to achieve congestion avoidance. ...
In telecommunication, the term time-out has the following meanings: A network parameter related to an enforced event designed to occur at the conclusion of a predetermined elapsed time. ...
Deep Space Telecommunications NASA has used many different error correcting codes. For missions between 1969 and 1977 the Mariner spacecraft used a Reed-Muller code. The noise these spacecraft were subject to was well approximated by a "bell-curve" (normal distribution), so the Reed-Muller codes were well suited to the situation. This article or section is missing references or citation of sources. ...
The Reed-Muller codes are a family of linear error-correcting codes used in communications. ...
The normal distribution, also called Gaussian distribution, is an extremely important probability distribution in many fields. ...
The Voyager 1 & Voyager 2 spacecraft transmitted color pictures of Jupiter and Saturn in 1979 and 1980. Voyager 1 lifted off with a Titan 3E Centaur A NASA artists rendition of a Voyager spacecraft The Voyager 1 spacecraft is an 815-kilogram unmanned probe of the outer solar system and beyond, launched September 5, 1977, and currently operational. ...
The Voyager 2 spacecraft was launched in August, 1977. ...
Adjective Jovian Atmospheric characteristics Atmospheric pressure 70 kPa Hydrogen ~86% Helium ~14% Methane 0. ...
Adjective Saturnian Atmospheric characteristics Atmospheric pressure 140 kPa Hydrogen >93% Helium >5% Methane 0. ...
- Color image transmission required 3 times the amount of data, so the Golay (24,12,8) code was used.
- This Golay code is only 3-error correcting, but it could be transmitted at a much higher data rate.
- Voyager 2 went on to Uranus and Neptune and the code was switched to a concatenated Reed-Solomon code-Convolutional code for its substantially more powerful error correcting capabilities.
- Current DSN error correction is done with dedicated hardware.
- For some NASA deep space craft such as those in the Voyager program, Cassini-Huygens (Saturn), New Horizons (Pluto) and Deep Space 1 -- the use of hardware ECC may not be feasible for the full duration of the mission.
A Golay code can be binary or ternary. ...
Adjective Uranian Atmospheric characteristics Atmospheric pressure 120 kPa (at the cloud level) Hydrogen 83% Helium 15% Methane 1. ...
Adjective Neptunian Atmospheric characteristics Surface pressure ≫100 MPa Hydrogen - H2 80% ±3. ...
Reed-Solomon error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols themselves. ...
In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n >= m) and (b) the transformation is a function...
The Voyager spacecraft Launch of Voyager 2 Voyager is also the name of a planned series of unmanned probes to Mars, cancelled in 1968. ...
This is an artists concept of Cassini during the Saturn Orbit Insertion (SOI) maneuver, just after the main engine has begun firing. ...
Adjective Saturnian Atmospheric characteristics Atmospheric pressure 140 kPa Hydrogen >93% Helium >5% Methane 0. ...
New Horizons is a NASA unmanned mission to fly by Pluto and its moons. ...
Adjective Plutonian Atmospheric characteristics Atmospheric pressure 0. ...
The spacecraft Deep Space 1 was launched October 24, 1998 on top of a Delta II rocket. ...
 NASA's Deep Space Missions ECC Codes (code imperfectness)
Image File history File links NASA_ECC_Codes-imperfection. ...
Image File history File links NASA_ECC_Codes-imperfection. ...
The different kinds of deep space and orbital missions that are conducted suggest that trying to find a "one size fits all" error correction system will be an ongoing problem for some time to come.
- For missions close to the earth the nature of the "noise" is different from that on a spacecraft headed towards the outer planets
- In particular, if a transmitter on a spacecraft far from earth is operating at a low power, the problem of correcting for noise gets larger with distance from the earth
Satellite Broadcasting (DVB) Official DVB logo, found on compliant devices DVB, short for Digital Video Broadcasting, is a suite of internationally accepted, open standards for digital television maintained by the DVB Project, an industry consortium with more than 270 members, and published by a Joint Technical Committee (JTC) of European Telecommunications Standards Institute...
Information theory and error correction and detection Information theory tells us that whatever the probability of error in transmission or storage, it is possible to construct error-correcting codes in which the likelihood of failure is arbitrarily low, although this requires adding increasing amounts of redundant data to the original, which might not be practical when the error probability is very high. Shannon's theorem sets an upper bound to the error correction rate that can be achieved (and thus the level of noise that can be tolerated) using a fixed amount of redundancy, but does not tell us how to construct such an optimal encoder. To meet Wikipedias quality standards, this article or section may require cleanup. ...
In telecommunication, a redundancy check is extra data added to a message for the purposes of error detection and error correction. ...
In information theory, the Shannon-Hartley theorem states the maximum amount of error-free digital data (that is, information) that can be transmitted over a communication link with a specified bandwidth in the presence of noise interference. ...
NOiSE is a one volume manga created by Tsutomu Nihei as a prequel to his acclaimed ten-volume work, Blame!. It offers some rather sketchy information concerning the Megastructures origins and initial size, as well as the origins of Silicon life. ...
Error-correcting codes can be divided into block codes and convolutional codes. Other block error-correcting codes, such as Reed-Solomon codes transform a chunk of bits into a (longer) chunk of bits in such a way that errors up to some threshold in each block can be detected and corrected. The Railway Block Code is a system of bells used to send simple messages about train operations from one signalbox to another. ...
In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n >= m) and (b) the transformation is a function...
Reed-Solomon error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols themselves. ...
However, in practice errors often occur in bursts rather than at random. This is often compensated for by shuffling (interleaving) the bits in the message after coding. Then any burst of bit-errors is broken up into a set of scattered single-bit errors when the bits of the message are unshuffled (de-interleaved) before being decoded. In telecommunication, an error burst is a contiguous sequence of symbols, received over a data transmission channel, such that the first and last symbols are in error and there exists no contiguous subsequence of m correctly received symbols within the error burst. ...
List of error-correction, error-detection methods A check bit is a single bit that is added to a byte or string as a part of an error detection (or sometimes error_correction) system. ...
A check digit is a form of redundancy check used for error detection, the decimal equivalent of a binary checksum. ...
In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n >= m) and (b) the transformation is a function...
Iterative Viterbi Decoding is an algorithm that spots the subsequence S of an observation O={o1,...,on} having the highest average probability (i. ...
Differential space–time codes[1][2] are a way of transmitting data in wireless communications. ...
Space–time block coding is a technique used in wireless communications to transmit multiple copies of a data stream across a number of antennas and to exploit the various received versions of the data to improve the reliability of data-transfer. ...
In general, an erasure code transforms a message of n blocks into a message with > n blocks such that the original message can be recovered from a subset of those blocks. ...
Fountain codes are a class of Erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can be recovered from any subset of the encoding symbols of size equal to or...
It has been suggested that this article or section be merged with Error correction and detection. ...
In Error correction and detection, Group codes are length Linear block codes which are subgroups of , where is a Finite Abelian group. ...
A Golay code can be binary or ternary. ...
The extended binary Golay code is an error-correcting code which encodes 12 bits of data in a 24-bit word in such a way that any triple-bit error can be corrected and any quadruple-bit error can be detected. ...
In mathematics, a Goppa code is a general type of linear code constructed by using an algebraic curve X over a finite field . ...
In cryptography, the McEliece cryptosystem is an asymmetric key algorithm developed in 1978 by Robert McEliece. ...
In telecommunication, a Hagelbarger code is a convolutional code that enables error bursts to be corrected provided that there are relatively long error-free intervals between the error bursts. ...
In telecommunication, a Hamming code is an error-correcting code named after its inventor, Richard Hamming. ...
In telecommunication, a longitudinal redundancy check (LRC) or horizontal redundancy check is a form of redundancy check based on the formation of a block check following preset rules. ...
A low-density parity-check code (LDPC code) is an error correcting code, a method of transmitting message over a noisy transmission channel. ...
LT-codes are a class of near optimal rateless erasure correcting codes introduced by Michael Luby. ...
Online codes are an example of rateless erasure codes. ...
In computing and telecommunication, a parity bit is a binary digit that indicates whether the number of 1 bits in the preceding data was even or odd. ...
Raptor codes, introduced by Amin Shokrallahi, are the first known class of fountain codes with linear time encoding and decoding. ...
Reed-Solomon error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols themselves. ...
The Reed-Muller codes are a family of linear error-correcting codes used in communications. ...
A Sparse graph code is a code which is represented by a sparse graph. ...
A space–time code (STC) is a method employed to improve the reliability of data transmission in wireless communication systems using multiple transmit antennas. ...
Space–time trellis codes (STTCs) are a type of space–time code used in multiple-antenna wireless communications. ...
Tornado codes are a revolutionary new class of erasure codes that support error-correcting and have fast encoding and decoding algorithms. ...
Fountain codes are a class of Erasure code with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can be recovered from any subset of the encoding symbols of size equal to or...
Turbo codes are a class of recently-developed high-performance error correction codes finding use in deep-space satellite communications and other applications where designers seek to achieve maximal information transfer over a limited-bandwidth communication link in the presence of data-corrupting noise. ...
The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ...
The Walsh code is used to uniquely define individual communication channels. ...
See also Error Correction Standardization Research Conferences on Error Correction Federal Standard 1037C entitled Telecommunications: Glossary of Telecommunication Terms is a U.S. Federal Standard, issued by the General Services Administration pursuant to the Federal Property and Administrative Services Act of 1949, as amended. ...
MIL-STD-188 is a series of U.S. military standards relating to telecommunications. ...
- 4th INTERNATIONAL SYMPOSIUM ON TURBO CODES
- Website http://www-turbo.enst-bretagne.fr/
- Website http://www.turbo-coding-2006.org/
External links - The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David MacKay, contains chapters on elementary error-correcting codes; on the theoretical limits of error-correction; and on the latest state-of-the-art error-correcting codes, including low-density parity-check codes, turbo codes, and digital fountain codes.
- Article: Memory errors and SECDED
|
Feeds |
Contact