Forward error correction (FEC) and Error correction code (ECC)
In: 5
The basic idea behind ECC is to add redundancy to a message such that you can detect and correct common types of errors. There are many different versions used, heavily varying depending on the nature of the communication and the expected types of errors that will occur. ECC, and related systems, have been developed for voice communication, writing, and electronic communication.
The absolute simplest is to merely duplicate, or more, the data. If you know I am sending you a 12 digit number, I could send you the number twice and, if you get different values, you know something went wrong and can request it again. If I send it to you three times and one gets corrupted, the one that is different is likely wrong and can be discarded and you use the matching two; if all three differ, you know *something* went wrong, but don’t know which is correct and need to request it again. Such a system is really good if you expect a *lot* of corruption, or the message is *really* important. However, such a system is also very inefficient given that I sent you two, or three, times the needed data to ensure you got it. Luckily, we could use any number of different tricks, mostly based in mathematics, to devise a smarter system, and make sure it can detect, and ideally correct, the most commonly expected errors.
One example of an ECC that is used for voice is the [NATO phonetic alphabet](https://en.wikipedia.org/wiki/NATO_phonetic_alphabet), parts of which are very well known. In this case, redundancy is added by adding extra sounds to the letter names to help make them more distinct and easier to identify. As such, even if you miss part of what was said, you can still understand the message, such as due to noise or very short signal loss.
Credit card numbers use a version called the [Luhn algorithm](https://en.wikipedia.org/wiki/Luhn_algorithm) that was designed to help with transcription errors. In this case, the digits of the card number are added together in a specific pattern and reduced to a single digit using modulus. This specific one was designed to detect most types of errors that a human would likely make when copying the number, such as miswriting a single digit or swapping two numbers around. It, however, does not normally encode enough data to allow for actual correction of errors – merely detection of them. If you know you got all but one digit, you could reverse the math to calculate what the missing digit was, however.
[QR codes](https://en.wikipedia.org/wiki/QR_code#Error_correction) have a few different versions depending on how much reliability you want. These use quite a bit of math to store the same data in multiple places around the code. The main intent here was to handle codes getting ripped or otherwise physically damaged after printing. The basic idea is to use a polynomial as, if you have any two of a, b, or c from a^(2) + b^(2) = c^(2), you can calculate the missing one (you might remember this from middle or high school math classes) – by storing all three of a, b, and c in the code, you can lose one and calculate the missing one. In most cases, this is expanded to additional variables and you can be missing any one. If you do this complex enough, you can have a lot of variables and chain calculate others so long as you are not missing too many.
Latest Answers