Error correction coding or "coding theory" is the means by which data transmitted over a noisy medium is recovered at the receiver. ECC works by adding redundant bits to the data being transmitted in an intelligent manner. There are many different kinds of error correction codes that offer different levels of error correction and require more or less computational power.
Error correction codes operate on the different levels: error detection, error correction, and erasure correction. The most basic error correction codes offer only error detection. More advanced coding scheme can correct higher numbers of bit errors and bit erasures.
Bit errors are when the receiver hardware incorrectly translates a received value. Bit erasures are when the receiver hardware marks a bit as erased when it is not confident of the bit's intended value. For example, suppose a received value of -1 represents a 0 bit and a received value of +1 represents a 1 bit. In this case, received values in the range [-0.2, 0.2] might be marked as bit erasures to be corrected by the error correction code. If a value greater than 0.2 is received when a 0 bit was sent by the transmitter, that would be an example of a bit error that would be marked as erased.
The most basic error correction code is the parity code. It cannot correct any errors, but the receiver can use it to determine if the data received is correct or not and request the data to be resent if necessary. The parity code adds a 1 to the end of the binary data to be sent if the binary data contains an odd number of 1s and a 0 otherwise. By counting the number of 1s received, the receiver can detect any time an odd number of but errors have occurred. Even numbers of errors are undetectable by the parity code. More advanced error codes can detect and correct higher numbers of errors.
Some error codes can correct errors without asking the transmitter to resend the data. They do this by comparing the data received to valid code words. A code word is data plus redundant bits that are added by the coding scheme at the transmitter.
Hamming codes are examples of codes that can correct one bit error. The [7,4] Hamming code uses codewords of length 7 to transmit 4 bits of data. The three redundant bits are each calculated as the parity bit for three of the for data bits. Each parity bit covers a different set of three data bits.
Since any one of the data bits is covered by at least two parity bits, changing one data bit causes at least 3 bits to change in the resulting codeword. The minimum number of bits that can be changed in one codeword to produce a second valid codeword in this case is three. This is known as the Hamming distance of the code. Usually, a code is capable of correcting floor(d/2) bit errors where d is the code's Hamming distance.
Other examples of error correction codes include Reed-Solomon (used on CDs), Hadamard, Viterbi, and Turbo Codes.
Photo by Satoshi KAYA