ABSTRACT
A large file sent over the Internet to many receivers splits into smaller packets. The packets may become corrupted or lost (erased) during transmission. Varying bandwidth may cause different receivers to receive these packets at different times. Large transmissions can be solved by the following three methods: (i) use acknowledgments for each received packet to signal which packets are to be retransmitted, as in TCP/IP, a very complex and inefficient process; (ii) use erasure correction codes in which redundancy is added by encoding a k-packet file as n packets (n > k), but not without issues when different receivers have unknown and varying loss rates; and (iii) produce an indefinitely long sequence of packets such that any collection of k(1 + ε) packets is sufficient to recover the entire file with high probability, where ε > 0 is an arbitrarily small number that measures the tradeoff between the loss recovery property of the code and the encoding and decoding processes. This process, which is independent of loss rate of the receiver, is known as a ‘Fountain code’, where the metaphor is analogous to filling a bucket under a fountain spraying water drops. Recall that coding theory is used to either remove redundancy from messages (source coding) or to add redundancy in order to make error correction possible (error correcting codes).
