Event Title

:

"Pseudocodewords of LDPC Constraint Graphs
and Construction of LDPC Codes"

Speaker

:

Dr. Deepak Sridhar

Affiliation

:

Institut fur Mathematik
University of Zurich
 

Subject Area

:

Mathematics

Date  

:

August 17, 2005

Time

:

4.00 pm

Venue

:

Lecture Hall I, Dept of Mathematics

We begin with a brief background on low-density parity-check (LDPC) codes -- a class of codes that can be described on sparse graphs. At long block lengths, LDPC codes have been designed to achieve near capacity performance via easy-to-implement, but sub-optimal, graph-based message-passing decoders. However, the design of short to moderate length LDPC codes that are well-suited for message-passing decoding is still an open area of research. In recent years, there has been some progress in explaining the behavior of message-passing decoders using the terminology of graph covers and pseudocodewords. It has been further shown that low-weight pseudocodewords dominate the performance of message-passing decoders and therefore, the minimum pseudocodeword weight is an important parameter for the design of LDPC codes.

We provide a tree-based lower bound on minimum pseudocodeword weight and outline a construction of LDPC constraint graphs wherein the minimum pseudocodeword weight is equal/almost equal to the minimum distance of the corresponding LDPC code. The construction involves enumerating a $d$-regular tree for a fixed number of layers and employing a connection algorithm based on mutually orthogonal Latin squares to close the tree. Methods are presented for degrees $d=p^s$ and $d = p^s+1$, for $p$ a prime, one of which includes the well-known finite-geometry-based LDPC codes.