forward error correction

In digital telecommunications, forward error correction (or FEC) is a method of error correction in which redundancy is added to a data stream before it is likely to get corrupted, e.g. by being transmitted over air. At the receiver side, the redundant information can be used to detect and reconstruct a certain amount of data corruption.

                              (retransmit request)
    _________       _________   |   _________   |   _________       _________
   |         |     |         |(<--)|         |(<--)|         |     |         |
   |user data| --> |FEC coder| --> | channel | --> | decoder | --> |User data|
   |_________|     |_________|     |_________|     |_________|     |_________|

There are several different FEC schemes, ranging from the simple checksum to the complicated turbo coding:

• checksums: somewhat efficient in detecting errors, not really useful in correcting them - and what do you do if your checksum gets corrupted?
• CRC: a bit better than a simple checksum, but still not too useful when it comes to correcting the detected errors.
• Cross Interleave Reed-Solomon Code: Quite good at detecting and reasonably efficient at correcting errors - as you can hear when listening to a CD.
• convolutional coding: One of the coders used for e.g. cellular phones in order to permit you talking to each other. Convolutionally coded data is decoded with a so-called Viterbi decoder. In the usually used versions, a convolutional coder adds a lot of redundancy to the data stream. At the comon coder rates of 1/2 or 1/3, the data going into the coder only accounts for 1/2 (or 1/3) of the data going out of the coder. On the other hand, with in this way convolutionally coded data it doesn't matter which bits of the coded stream are corrupted.
• turbo coding: Another coder/decoder pair used in wireless telecommunications. The coder uses a feedback system, taking some of the coded data back to the coder's input. Again, at common coder rates of 1/2 or 1/3, a turbo coder adds a lot of redundancy to the data stream and, again, all of the bits in the coded data stream are equally (in)sensitive towards being corrupted. The description of how a turbo coder does what it does and the proof that it does that correctly fills several PhD theses.

So why does anybody want to apparently waste 1/2 or 2/3 of the available (and expensive) bandwidth by transmitting redundant data? Simply because it's not a waste but a necessity if you want to recieve your data

• completely,
• with comparetively low delay and
• in the order it was transmitted.

Without forward error correction, you'd have the chance of:

• No error detection, which crud bh somrw_at_plebremitag...,
• error detection without correction, sti_l not qui_e w_at you'd li_e to h_ve...,
• error detection with retransmits, either without waiting for the retransmitted data to arrive - possible e.g. for web access, bu_ itm_ospsib_e lfor_sp ee_h.c..
• ..or waiting for retransmits, whi__ch coul__d be__come__ somew__hat an__noy__ing...

So, in order to be able to cope with streaming real-time data, a system is needed that can correct errors in the incoming data without waiting for a retransmit, and the bandwidth increasing FEC schemes are the best we have today.