DocumentCode
2949917
Title
New model for rigorous analysis of LT-codes
Author
Maneva, Elitza ; Shokrollahi, Amin
Author_Institution
Div. of Comput. Sci., Berkeley California Univ., CA
fYear
2006
fDate
9-14 July 2006
Firstpage
2677
Lastpage
2679
Abstract
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 bit-error probability as the length of the code goes to infinity via recent results in random hypergraphs by Darling and Norris, Ann. Appl. Probab., 2005. For a code of finite length, we provide an algorithm for computing the probability of block-error of the decoder. This algorithm improves by a linear factor the algorithm of Karp, Luby, and Shokrollahi, Proc. of ISIT, 2004
Keywords
decoding; error statistics; LT-codes; belief propagation; bit-error probability; block-error decoder probability; random hypergraphs; Algorithm design and analysis; Belief propagation; Computer science; Decoding; Dynamic programming; Error analysis; Error probability; H infinity control; Polynomials; Random variables;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory, 2006 IEEE International Symposium on
Conference_Location
Seattle, WA
Print_ISBN
1-4244-0505-X
Electronic_ISBN
1-4244-0504-1
Type
conf
DOI
10.1109/ISIT.2006.262139
Filename
4036458
Link To Document