The Analysis of Error Floor and Graphical Structure of LDPC Codes

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Karimi Dehkordi, Mehdi

Date: 

2013

Abstract: 

In this thesis, we analyze the graphical structure of trapping sets and study their relationships to short cycles and to the code parameters such as block length and degree distributions. As a result, we develop new characterizations of trapping sets and novel techniques to efficiently find them.Our study on short cycles leads to two efficient algorithms for counting them in the Tanner graph of LDPC codes, one for Tanner graphs of general LDPC codes, and one tailored for Tanner graphs of practically important quasi cyclic (QC) protograph LDPC codes.We show that for sparse graphs, the proposed algorithms significantly outperform the existing techniques, in terms of computational complexity and memory requirements. For QC protograph LDPC codes, we also derive bounds to describe the relationships between the size of the shortest cycles in the Tanner graph and some of the code parameters such as the lifting degree, and the size of the base graph. These bounds are in some cases tighter and in some other cases more general than existing bounds.Our analysis of the graphical structure of trapping sets and their relationships to short cycles results in an efficient algorithm for finding the trapping sets of LDPC codes. The algorithm is universal in the sense that it can be applied to an arbitrary graph (regular or irregular) and that it can be tailored to find a variety of important graphical objects, such as absorbing sets. The algorithm is significantly faster than similar existing search algorithms.We also devote special attention to elementary trapping sets (ETS), which are known to be the main cause of error floor for many LDPC codes. Our study leads to a simple characterization of ETSs by introducing a new property called layered superset (LSS) property. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graphand finds all the ETSs with LSS property in a guaranteed fashion.

Subject: 

PHYSICAL SCIENCES Engineering - Electronics and Electrical
PHYSICAL SCIENCES Mathematics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 
Ph.D.

Thesis Degree Level: 

Doctoral

Thesis Degree Discipline: 

SYST: Electrical and Computer

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).