WAN Optimization Forward Error Correction
Types of Forward Error Correction
Block and convolutional codes are the two main categories of forward error correction codes. Sometimes these are combined in concatenated coding schemes.
- Block codes – this type of forward error correction works on fixed block sizes or symbols of predetermined size. These are generally decoded in polynomial time to their length.
- Convolutional codes – this type of forward error correction works on data of arbitrary length. These are frequently decoded using the Viterbi algorithm. This algorithm allows variable lengths data decoding but exponentially introduces complexity.
- Concatenated forward error correction codes – In concatenated forward error correction schemes, a short length Viterbi decoded convolutional code is primary while a block with large size finishes up any errors made by the convolutional decoder. This is a very effective method of forward error correction with low error rates.
Low density parity check – these are highly efficient liner block codes that provide close to channel capacity which is the theoretical maximum. They work by an iterated soft decision decoding approach. This is heavy in the computation department. Hence even though they were proposed sometime ago, they were ignored. Since computation power have increased several fold over the last few decades, these techniques have found favor again. Low density parity check codes are now used in several high speed communications standards. A list of these are: DVB-S2 (digital video broadcasting), WiMAX (this is an IEEEE standard – IEEE 802.16c – microwave communications, High Speed Wireless LAN (IEEE 802.11a).
Local Decoding and Testing
In a streaming setting, it makes sense to decode single bits of the message or determine if a given signal is a codeword or not by not having to examine the whole message. When streaming data, code words are large and cannot be decoded fast enough. These are very important in computational complexity theory for the design of probabilistically checkable proofs.
Locally decodable codes are error correcting codes where single bits of the message can be probabilistically recovered by looking at a constant position of the code word. In contrast locally testable codes are error correcting codes which can be checked probabilistically by examining only a small number of positions.