2005/12/08 by Elitza Maneva, Maneva, Elitza N., Amin Shokrollahi +1
Computer Science · Biochemistry, Genetics and Molecular Biology · #Error Correcting Code Techniques #Cooperative Communication and Network Coding #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.cs/0512029
We present a new model for LT codes which simplifies the analysis of the error probability of decoding by belief propagation. For any given degree distribution, we provide the first rigorous expression for the limiting error probability as the length of the code goes to infinity via recent results in random hypergraphs [Darling-Norris 2005]. For a code of finite length, we provide an algorithm for computing the probability of error of the decoder. This algorithm improves the one of [Karp-Luby-Shokrollahi 2004] by a linear factor.