Error Correcting Code

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) was. If there was 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.)

  • repetition schemes -- if the transmitter repeat each data bit at least 3 different times (triple modular redundancy), the receiver can correct any single-bit error by taking the majority vote of the received data bits.
  • parity schemes -- if the transmitter sends parity bits covering various overlapping groups of the data bits, a single-bit error will cause a parity error in every group that covers that erroneous bit. The receiver can correct any single-bit error by flipping the one bit covered by every group that indicates an error, but not covered by any group that checks out good. There are a wide variety of parity-based codes, differing in exactly how groups of data bits are chosen -- we will discuss them later.
  • cyclic redundancy checks -- when a transmitter adds a CRC code to a message, any single-bit error will cause the received CRC to differ from the receiver-calculated CRC. If the message is short enough, the receiver can figure out exactly which bit was flipped, and correct it -- Header Error Correction.
  • Hamming distance based checks -- Since it takes many bit errors to convert one valid Hamming code word to any other valid Hamming code word, the receiver can correct any single-bit error in a word by finding the "closest" valid Hamming code, the one code word that has only 1 bit different from the received word.

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.