David MacKay

Fountain Codes

In this talk I will explain fountain codes, which are record-breaking  codes for reliable communication over channels with erasures. Channels with erasures are of great importance. For example, files  sent over the internet are chopped into packets, and each packet is  either received without error or not received.  Standard methods  involve retransmissions of the erased packets. Fountain codes offer a  much more efficient and elegant solution that requires no feedback  channel from receiver to sender. Fountain codes are "rateless" - they perform near the capacity of _any_ channel, whatever the statistics of erasures.

Fountain codes are described in Chapter 50 of my book "Information Theory,  Inference, and Learning Algorithms" (Cambridge University Press, 2003).