Low-Density Parity-Check Codes: Asymptotic Behavior and Zeta Functions
Open Access
Author:
Lu, Min
Graduate Program:
Mathematics
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
May 07, 2009
Committee Members:
Wen Ching Winnie Li, Dissertation Advisor/Co-Advisor Wen Ching Winnie Li, Committee Chair/Co-Chair John Metzner, Committee Member David Jonathan Miller, Committee Member Gary Lee Mullen, Committee Member
A LDPC code is binary linear code equipped with a sparse parity-check matrix. A bipartite graph, called Tanner graph, can be associated to a parity-check matrix. Then message passing iterative decoding (MPID) algorithms can be applied on the Tanner graph to do fast efficient decoding. Richardson and Urbanke proposed a scheme, called density evolution, to analyze the performance of MPID algorithms. Using density evolution we shall report new approaches to designing asymptotically good LDPC code ensembles over binary erasure channel (BEC). We then answer an open question raised by Shokrollahi and Oswald during their study on capacity-achieving sequences over BEC. Next, in order to understand MPID algorithms better we bring up the discussion of pseudo-codewords, which are regarded as the cause of decoding errors. We shall present two rational functions whose monomials in the Taylor expansion enumerate all the pseudo-codewords of a general binary parity-check code.
