Fountain Codes over Arbitrary Channels and Threshold Phenomena

Опубликовано 6 сентября 2016, 5:44

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.