Random linear fountain codes [doc]
Redundant packets are formed as checksums of random subsets
of the original source K packets. A
checksum of some source packets is their XOR packet or, which is the same, a
packet obtained by a bitwise sum, modulo
2, of the considered source packets. Only redundant packets are
transmitted. Once K redundant packets
are received, the probability of decoding the original K packets depends remarkably only on the number of excess packets.
If the number of excess packets is E
the probability of a failure is below 
, does not matter on the number of original packets [MacKay05].
The below chart shows results of simulations with 10 and 20 source packets. In both cases the probabilities of decoding behave identically in respect to the number of exceeding packets.
[xls]
For example 4 exceeding packets signify 14 received packets for the case with 10 original packets and 24 received packets for the case with 20 original packets. For the 10-packets case 10’000 random matrices (random sequences of redundant packets) were considered and 1’000 random matrices for the 20-packets case.
Using redundant packets formed from pairs of original packets (relying on a K-ring graph as one of the best methods for choosing the pairs) required not only a relative growth of exceeding packets, as the number of source packets increases, but a relative growth which is even faster than that of the number of source packets [ ch | us ].
In contrast with the random linear fountain codes the relative number of exceeding packets decreases as the number of the source packets increases.
Related links:
- David J. C. MacKay, “Fountain codes”, Communications, IEE Proceedings Volume 152 Issue 6, December 2005, pages 1062 – 1068 [MacKay05]
- A C program generating the sequences of redundant packets and computing the decoding probabilities [ cpp | txt | screenshot ]
- Computing the curves of packet recovery probabilities for various numbers of original packets, when the redundant packets are XOR checksums of pairs of original packets selected according to a K-ring graph [ ch | us ]
-
Comparing the recovery probabilities of a 
Torus graph and a K-ring graph with 9 nodes
and 18 edges [ ch
| us
]
- Computing the recovery probabilities for 2500 random graphs with 18 edges [ ch | us ]
- Computing the recovery probabilities for a double cycle graph [ ch | us ]
- Computing the recovery probabilities for a torus graph [ ch | us ]
* * *