Analysis and design of a new fountain codec under belief propagation

Error-prone patterns have been extensively studied for low-density parity-check codes yet they have never been fully explored for generator-based `Fountain codes´. It is shown here that these phenomena are related to certain combinatorial structures within the Tanner graph (TG) representation of the code, previously termed absorbing sets. The authors systematically define the `absorbing sets´ in the generator-based TG of a code. They then demonstrate how these substructures are damaging to the `realised rate, delay´ and `decoding cost´ of Fountain codes particularly at low error rates. They further analyse the existence probability of certain absorbing sets and propose a new encoder/decoder pair forming a new family of Fountain codes. The authors experimental results show that these new codecs lead to improvements in all system features. Typical gains for Luby-transform codes include 20% reduction in the decoding complexity and simultaneous coding gains of 0.6 and 0.9 dB at bit error rates of 10^-5 and 10^-6, respectively. As such, this work takes a step towards better rateless code design and construction.