WAN Optimization Forward Error Correction
Forward Error Correction is a method, as the name suggests, of controlling error in the transmission of data. The forward error correction techniques consist of sending redundant data and the receiver or destination on recognizing portions of the data that are effort free. Forward error correction does not require a handshake between sender and receiver and this allows for the transmission of data to multiple destinations from a single source.
Since a part of the original transmission is redundant data, it allows the destination to detect and correct a limited number of errors. These errors can be corrected without retransmission. While forward error correction gives the ability to do this, it comes at a cost. The bandwidth required at the origin is higher because redundant data has to be transmitted. Therefore forward error correction techniques are only applied in situations where retransmissions are costly or impossible in instances where data is being broadcast to multiple destinations.
As stated earlier, forward error correction adds redundancy to the transmitted data stream using a predetermined algorithm. A complex function of the original data may be used to form the redundant bit and the original data may or may not appear literally in the coded output. If a code includes unmodified input data in the output it is called systematic and those that are modified are called non-systematic. Several types of forward error correction exisit and the following is a brief overview of these.
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.
