This is one of my very first posts. But it remained a draft for years.
Error correcting codes are a fascinating part of applied mathematics. They allow both detecting errors introduced by the communication channel and correcting them, both to a certain extent.
We'll go through the basics of ECCs and take a look at interesting applications of these codes in file distribution scenarios, as they offer pretty nifty solutions in this domain.
Introduction to error-correcting codes
The basics behind ECCs is that you have words that you want to transmit error-free over an channel that isn't perfect.
Each of the possible words is first associated a codeword. This is called the encoding.
For the code to have any correcting properties, the space that contains the codewords has to be larger than the space that contains the words. For example, if the words are 5-bits messages, the codewords might be 8-bits messages.
The main characteristic of the code is that codewords don't fill up the codeword space, they are spread apart. You can define a distance between codewords, as for example the number of bit to bit differences if your codewords are binary words: 1001 and 0011 have 2 differences, so their distance is 2.
This allows you to find the mimimum distance between codewords for a given code, which we'll see is a important value that defines some of the properties of the code. For example, the code composed of the four codewords 0000, 1100, 0011 and 1111, has a minimum distance of 2, as it takes a least two bit changes to transform one of them into another.
Now, let's send the codewords over the imperfect channel. Changes are likely to occur during the transmission depending on the error rate of the channel, so it is possible you don't get a codeword on the receiving end. If so, you can tell for sure that changes occured. And if the number of changes is low enough, the received message will be close -in terms of distance or differences- to the sent codeword. If you can find which codeword is the closest to the received message, then you probably have recovered the original message, that is, decoded the received message.
This works fine as a way of safely transfering messages over an imperfect channel, but only if the minimum distance for the code is large enough compared to the error rate of the channel. If too many errors are introduced by the channel, then the received message might not be close to the correct codeword. For example, if I have two codewords 00 and 11, it is possible that 00 becomes 11 after being transfered over a channel that introduced 2 errors. Also with this code, if the channel introduces even 1 error, then I'll know that there was an error if I receive 01 or 10, but I won't be able to figure out what was the codeword before the error was introduced.
-> first constraint: the minimum distance
-> second constraint: the codeword space and codeword distribution (sphere packing problem).
par archives and reed-solomon codes
onion networks
tornado codes, Low-Density Parity-Check Codes
open content network
bit torrent
http://onionnetworks.com/developers/
http://open-content.net/specs/
Bunch of links
Matrix Hamming Codes
Entropy and Information
Stanford University Professor - Robert M. Gray
A Short Course in Information Theory
A Mathematical Theory Of Communication
R.W. Hamming - Error Detecting and Error Correcting Codes (1/15)
Improved Low-Density Parity-Check Codes Using Irregular Graphs
Low-Density Parity-Check Codes
gallager code
forward error correction library
http://onionnetworks.com/developers/index.php
Rateless codes:
http://project-iris.net/talks/