It is possible to combine the two, so that minor errors are corrected without retransmission, and major errors are detected and a retransmission requested. The combination is called hybrid automatic repeat-request.
Several schemes exist to achieve error detection, and are generally quite simple. All error detection codes (which include all error-detection-and-correction codes) transmit more bits than were in the original data. Most codes are "systematic": the transmitter sends a fixed number of original data bits, followed by fixed number of check bits (usually referred to as redundancy in the literature) which are derived from the data bits by some deterministic algorithm. The receiver applies the same algorithm to the received data bits and compares its output to the received check bits; if the values do not match, an error has occurred at some point during the transmission. In a system that uses a "non-systematic" code, such as some raptor codes, data bits are transformed into at least as many code bits, and the transmitter sends only the code bits.
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.
The stream of data is broken up into blocks of bits, and the number of 1 bits is counted. Then, a "parity bit" is set (or cleared) if the number of one bits is odd (or even). (This scheme is called even parity; odd parity can also be used.) If the tested blocks overlap, then the parity bits can be used to isolate the error, and even correct it if the error affects a single bit: this is the principle behind the Hamming code.
There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors (one, three, five, and so on). If an even number of bits (two, four, six and so on) are flipped, the parity bit appears to be correct, even though the data is corrupt.
On the receiver side, a new checksum may be calculated, from the extended message. If the new checksum is not 0, error is detected.
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.
On reception, one can recompute the CRC from the payload bits and compare this with the CRC that was received. A mismatch indicates that an error occurred.
Polarity symbol reversal is (probably) the simplest form of Turbo code, but technically not a Turbo code at all.
Original transmitted symbol 1011
This polarity reversal scheme works fairly well at low data rates (below 300 baud) with very redundant data like telemetry data.
Automatic Repeat-reQuest (ARQ) is an error control method for data transmission which makes use of error detection codes, acknowledgment and/or negative acknowledgement messages and timeouts to achieve reliable data transmission. An acknowledgment is a message sent by the receiver to the transmitter to indicate that it has correctly received a data frame.
Usually, when the transmitter does not receive the acknowledgment before the timeout occurs (i.e. within a reasonable amount of time after sending the data frame), it retransmits the frame until it is either correctly received or the error persists beyond a predetermined number of retransmissions.
Hybrid ARQ is a combination of ARQ and forward error correction.
An error-correcting code (ECC) or forward error correction (FEC) code is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. It is used in computer data storage, for example in dynamic RAM, and in data transmission.
The basic idea is for the transmitter to apply one or more of the above error detecting codes; then the receiver uses those codes to narrow down exactly where in the message the error (if any) is. If there is a single bit error in transmission, the decoder uses those error detecting codes to narrow down the error to a single bit (1 or 0), then fix that error by flipping that bit. (Later we will discuss ways of dealing with more than one error per message.)
Some codes 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). Hamming codes can correct single-bit errors and detect double-bit errors (SEC-DED) -- more sophisticated codes correct and detect even more errors.
An error-correcting code which corrects all errors of up to n bits correctly is also an error-detecting code which can detect at least all errors of up to 2n bits.
Two main categories are convolutional codes and block codes. Examples of the latter are Hamming code, BCH code, Reed-Solomon code, Reed-Muller code, Binary Golay code, and low-density parity-check codes.
Shannon's theorem is an important theorem in error correction which describes the maximum attainable efficiency of an error-correcting scheme versus the levels of noise interference expected. In general, these methods put redundant information into the data stream following certain algebraic or geometric relations so that the decoded stream, if damaged in transmission, can be corrected. The effectiveness of the coding scheme is measured in terms of code rate, which is the code length divided by the useful information, and the Coding gain, which is the difference of the SNR levels of the uncoded and coded systems required to reach the same BER levels.
Applications that require low latency (such as telephone conversations) cannot use Automatic Repeat reQuest (ARQ); they must use Forward Error Correction (FEC). By the time an ARQ system discovers an error and re-transmits it, the re-sent data will arrive too late to be any good.
Applications where the transmitter immediately forgets the information as soon as it is sent (such as most television cameras) cannot use ARQ; they must use FEC because when an error occurs, the original data is no longer available. (This is also why FEC is used in data storage systems such as RAID and distributed data store).
Applications that use ARQ must have a return channel. Applications that have no return channel cannot use ARQ.
Applications that require extremely low error rates (such as digital money transfers) must use ARQ.
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.
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.
The demand for satellite transponder bandwidth continues to grow, fueled by the desire to deliver television (including new channels and High Definition TV) and IP data. Transponder availability and bandwidth constraints have limited this growth, because transponder capacity is determined by the selected modulation scheme and Forward error correction (FEC) rate.
Error detection and correction codes are often used to improve the reliability of data storage media.
Some file formats, particularly archive formats, include a checksum (most often CRC32) to detect corruption and truncation and can employ redundancy and/or parity files to recover portions of corrupted data.
Modern hard drives use CRC codes to detect and Reed-Solomon codes to correct minor errors in sector reads, and to recover data from sectors that have "gone bad" and store that data in the spare sectors.
RAID systems use a variety of error correction techniques, to correct errors when a hard drive completely fails.
The Vandermonde matrix is used in some RAID techniques.
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.
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.
Practical uses of Error Correction methods
Patent Application Titled "Systems and Methods for Error Detection and Correction in a Memory Module Which Includes a Memory Buffer" under Review
Nov 08, 2012; By a News Reporter-Staff News Editor at Politics & Government Week -- According to news reporting originating from Washington,...
US Patent Issued to Kabushiki Kaisha Toshiba on June 18 for "Error Detection and Correction System Including a Syndrome Element Calculating Unit" (Japanese Inventor)
Jun 24, 2013; ALEXANDRIA, Va., June 24 -- United States Patent no. 8,468,434, issued on June 18, was assigned to Kabushiki Kaisha Toshiba...
US Patent Issued to Super Talent Electronics on Jan. 4 for "Data Error Detection and Correction in Non-Volatile Memory Devices" (American, Taiwanese Inventors)
Jan 11, 2011; ALEXANDRIA, Va., Jan. 11 -- United States Patent no. 7,865,809, issued on Jan. 4, was assigned to Super Talent Electronics Inc....
US Patent Issued to SAMSUNG ELECTRONICS on May 24 for "Semiconductor Memory Device and Data Error Detection and Correction Method of the Same" (South Korean Inventors)
May 25, 2011; ALEXANDRIA, Va., May 25 -- United States Patent no. 7,949,928, issued on May 24, was assigned to SAMSUNG ELECTRONICS Co. Ltd....