Fountain codes
2006-03-23
A file can be chopped into packets. Instead of the source packets of the file we can transmit checksum packets of various subsets of the source packets. If the receiver received fewer packets than the number of original packets in the file, then definitely there is not enough information has yet been collected for recovering the file. The file recovery becomes possible as soon as there are as many packets received as there are source packets in the file. In this page we measure the probability of file recovery as a function of the number of received excess packets. The same measurements are presented in 060318-fountain-code-gaussian-elimination [ ch | us ]. This page contains an improved version of a C++ program. The measurements are compared with the previous results and are identical:
[xls]
- Curves having the label “(old)” are obtained with the previous program [ ch | us ]
- Label “random” signifies that the checksum packets are obtained from randomly selected source packets
- Option “degree=3” signifies that the checksum packets are obtained only from three random source packets
- Options “K=10”, “K=15” and “K=20” point to the number of source packets in the file, i.e. 10, 15 and 20 packets respectively
- When the checksum packets are formed according to the “random” method the performance curve does not depend on the number of source packets (remarkable!)
Related links:
- C++ program [ cpp | txt ] (corrected on 2006-03-24)
- MS Word version of this page [doc]
- Previous version of the program [ ch | us ]
- David J. C. MacKay, “Fountain codes”, Communications, IEE Proceedings Volume 152 Issue 6, December 2005, pages 1062 – 1068 [MacKay05]
- Gaussian elimination [ MathWorld | PlanetMath | Wikipedia ]
- Linearly independent [MathWorld]
- Matrix rank [MathWorld]
* * *