Error Correction

There are two main ways of dealing with errors. One involves resending the corrupted data once an error has been detected - Automatic Repeat Request (ARQ); the other involves sending error correcting codes along with the data - Forward Error Correction (FEC). Each method has its advantages and disadvantages. Visit the relevant Wikipedia pages to learn more.

ARQ

To quote the Wikipedia ARQ page:

Automatic Repeat reQuest

is
 an error control method for data transmission that makes use of 
error-detection codes, acknowledgment and/or negative acknowledgment 
messages, and

timeouts

to
 achieve reliable data transmission. An acknowledgment is a message sent
 by the receiver 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.

Three types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ, and Selective Repeat ARQ.

ARQ is appropriate if the communication channel has varying or unknown capacity, such as is the case on the Internet. However, ARQ requires the availability of a back channel, results in possibly increased latency due to retransmissions, and requires the maintenance of buffers and timers for retransmissions, which in the case of network congestion can put a strain on the server and overall network capacity.

FEC

To quote this FEC Wikipedia page:

In telecommunication and information theory, forward error correction (FEC) (also called channel coding) is a system of error control for data transmission, whereby the sender adds systematically generated redundant data to its messages, also known as an error-correcting code (ECC). The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first FEC code, the Hamming (7,4) code, in 1950.

The carefully designed redundancy allows the receiver to detect 
and correct a limited number of errors occurring anywhere in the message
 without the need to ask the sender for additional data. FEC gives the 
receiver an ability to correct errors without needing a

reverse channel


 to request retransmission of data, but this advantage is at the cost of
 a fixed higher forward channel bandwidth. FEC is therefore applied in 
situations where retransmissions are relatively costly, or impossible 
such as when broadcasting to multiple receivers. In particular, FEC 
information is usually added to

mass storage devices to enable recovery of corrupted data.

There are many forms of FEC. Below is an edited example from the page mentioned above.

FEC is accomplished by adding redundancy to the transmitted information using a predetermined algorithm. A redundant bit may be a complex function of many original information bits. The original information may or may not appear literally in the encoded output; codes that include the unmodified input in the output are systematic, while those that do not are non-systematic.

A simplistic example of FEC is to transmit each data bit 3 times, which is known as a (3,1) repetition code. Say the two digits 0 and 1 are to be transmitted. Instead of just sending 01, 000 and 111 are sent respectively.

Through a noisy channel (prone to interference), a receiver might see 8 versions of the output - see table below. This allows an error in any one of the three samples to be corrected by "majority vote" or "democratic voting".

`Triplet received`	`Interpreted as`
`000`	`0 (error free)`
`001`	`0 (corrected)`
`010`	`0 (corrected)`
`100`	`0 (corrected)`
`111`	`1 (error free)`
`110`	`1 (corrected)`
`101`	`1 (corrected)`
`011`	`1 (corrected)`

The correcting ability of this FEC is:

Up to 1 bit of triplet in error, or
up to 2 bits of triplet omitted (cases not shown in table).

Though simple to implement and widely used, this triple modular redundancy is a relatively inefficient FEC. Better FEC codes typically examine the last several dozen, or even the last several hundred, previously received bits to determine how to decode the current small handful of bits (typically in groups of 2 to 8 bits).

Comments