Data Coding Theory/Forward Error Correction
Forward Error Correction
[edit | edit source]
If we are sending data through an unreliable communications channel, it is frequently a good idea to provide some mechanism to correct data that has been received in error. Incorporating redundancy into your packet, in order to detect and possibly correct errors in the data is known as forward error correction (FEC).
Forms of FEC
[edit | edit source]There are many forms of FEC. Some of the most simple are repitition codes where the data is replicated and transmitted multiple times. If the information does not match between the repititions, the value that has been received most commonly is selected as the "correct" version.
More advanced forms of FEC are block codes and hamming codes. We will discuss all these things later.
Parity
[edit | edit source]Parity is not strictly an FEC technique, but it's one that we will reference frequently. In a parity situation, an extra bit is appended to the data to detect simple errors. There are two types of parity: even and odd parity.
- Even parity
- Even parity counts the number of 1's in the data. If there is an odd number of 1's the parity bit is 1. Otherwise, the parity bit is 0.
- Odd parity
- Odd parity counts the number of 1's in the data. If there is an even number of 1's, the parity bit is 1. Otherwise it is zero.
Parity can detect when a single bit is in error, but it cannot determine which bit is wrong. Also, parity cannot detect errors in multiple bits. If two bits, 4 bits, or 6 bits are in error, the parity will indicate that the data is correct.
FEC Limitations
[edit | edit source]Just as parity can only account for situations with up to 1 error, various FEC codes are designed for other situations. FEC codes can detect one number of errors, and can correct another number. For instance, a particular code could detect up to 3 errors, but only be able to correct up to 1 error.