Fountain Codes over Arbitrary Channels and Threshold Phenomena

August 16, 2005
Omid Etesami | UC Berkeley/MSR

Given a vector of k input symbols, a fountain code produces a potentially limitless stream of output symbols, each generated independently and at random. These codes have applications in scalable data distribution over heterogeneous networks with multiple transmitters and receivers.

For the erasure channel, Luby and Shokrollahi have designed efficient capacity-achieving fountain codes based on sparse graphs. We will look at their generalization to channels with errors, where belief propagation is used for decoding.

We observe a connection between the performance of belief propagation and a generalization of the giant component threshold of random graphs. This shows that no code can simultaneously achieve the capacity of all channels. On the other hand, we prove that the codes beat the so-called “cut-off” rate on all channels, even when the encoder is totally oblivious of the underlying channel.

This is joint work with Amin Shokrollahi.

Speaker Details

Omid is a graduate student of computer science at University of California, Berkeley. Earlier he did his undergraduate studies at Sharif University of Technology, Iran. Omid is an intern in the Theory Group at MSR this summer.