Probabilities of decoding of random linear fountain codes and a code
transmitting checksums of only three randomly selected source packets
2006-03-17
Consider random linear fountain code for a file of size K source packets. At each clock cycle,
labeled by n, the encoder generates K random bits 
, and the transmitted packet 
is set to the bitwise
sum, modulo 2, of the source packets for which 
is 1 [MacKay05].
Here are two programs computing the decoding probability of
source K packets as a function of the
number 
of received packets.
The first program [ cpp | txt ]
uses a brute force method for checking each new packet’s linear independence [MathWorld]
from all previously received packets. The brute force method uses all possible
subsets of previous packets, resulting therefore to a complexity of a factor of
. The second program [ cpp | txt ] uses Gaussian elimination [MathWorld] for
computing the rank of the matrix [MathWorld] resulting
therefore to a complexity of a factor of 
.
We computed also the decoding probabilities for random packets, obtained by exclusive-or-ing of only three randomly taken source packets. For this case the decoding probabilities depend on the number of source packets and the three brown non-dashed curves of the below chart show correspondingly the probabilities for 10, 15 and 20 source packets. The black curve, for the random linear fountain code, (remarkably) does not depend on the number of the source packets.
[xls]
The dashed curves represent:
- systematic encoding of 9 source packets together with 9 checksums of pairs of the source packets and 9 checksums of triplets of source packets (the pairs and triplets are selected according to a K-ring hypergraph), [ ch | us ] section V
- systematic encoding of 18 source packets together with 36 checksums of triplets selected according to a K-ring hypergraph, [ ch | us ] section VII
Related links:
- C++ program computing the solvability with Gaussian elimination [ cpp | txt | out | xls ]
- C++ program computing the solvability with the brute-force method with subsets (for demo) [ cpp | txt | out | xls ]
- 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]
- Computing the decoding probabilities of K-ring hypergraphs with 9 and 18 source packets [ ch | us ]
* * *