The Analysis of Error Floor and Graphical Structure of LDPC Codes
Public Deposited- Resource Type
- Creator
- 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
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2013 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2013
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
karimidehkordi-theanalysisoferrorfloorandgraphicalstructure.pdf | 2023-05-04 | Public | Download |