ANALYSIS OF FINITE-LENGTH LOW-DENSITY PARITY-CHECK CODES

Open Access
Author:
Wang, Chenying
Graduate Program:
Mathematics
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
June 10, 2010
Committee Members:
  • Wen Ching Winnie Li, Dissertation Advisor
  • Wen Ching Winnie Li, Committee Chair
  • John Metzner, Committee Member
  • Gary Lee Mullen, Committee Member
  • Stephen George Simpson, Committee Member
Keywords:
  • LDPC codes
  • Min-Sum Decoding
  • Decoding Performance
  • Maximal Allowable Error
  • LU(m
  • q) Codes
Abstract:
A low-density parity-check (LDPC) code is a binary linear code specified by a sparse parity check matrix. The min-sum decoding (MSD) algorithm can be applied on the Tanner graph modeling the structure of the LDPC code to do fast efficient decoding. We introduce the concept of maximal allowable error which describes the error-correcting capability of a code when MSD is implemented on LDPC codes over binary symmetric channel (BSC). Two powerful tools, called computation tree and deviation, were introduced by Wiberg to analyze the performance of MSD algorithm of finite-length LDPC codes. By using these tools, we obtain the maximal allowable error over BSC for cycle codes and a lower bound of that for general LDPC codes. By investigating the decoding process of codes LU(2 ,q) and LU(3,q) which were constructed by using certain q-regular bipartite graphs as Tanner graphs, we prove that the lower bound of the maximal allowable error for general LDPC codes is tight for odd q and differs from the tight bound by 1 for even q. Furthermore, the Tanner graphs of codes LU(2,q) and LU(3,q) are shown to be Ramanujan graphs.