Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes

Stefan Ländner, Olgica Milenkovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Several combinatorial properties of low-density parity-check (LDPC) codes, such as minimum distance, diameter, stopping number, girth and cycle-length distribution of the corresponding Tanner graph, are known to influence their performance under iterative decoding. Recently, a new class of combinatorial configurations, termed trapping sets, was shown to be of significant importance in determining the properties of LDPC codes in the error-floor region. Very little is known both about the existence/parameters of trapping sets in structured LDPC codes and about possible techniques for reducing their negative influence on the code's performance. In this paper, we will address both these problems from an algorithmic and combinatorial perspective. We will first provide a numerical study of the trapping phenomena for the Margulis code, which exhibits a fairly high error-floor. Based on this analysis, conducted for two different implementations of iterative belief propagation, we will propose a novel decoding process, termed averaged decoding. Averaged decoding provides for a significant reduction in the number of incorrectly decoded frames in the error-floor region of the Margulis code. Furthermore, based on the results of the algorithmic approach, we suggest a novel combinatorial characterizations of trapping sets in the class of LDPC codes based on finite geometries. Projective geometry LDPC codes are suspected to have extremely low error-floors, which is a property that we may attribute to the non-existence of certain small trapping sets in the code graph.

Original languageEnglish (US)
Title of host publication2005 International Conference on Wireless Networks, Communications and Mobile Computing
Pages630-635
Number of pages6
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event2005 International Conference on Wireless Networks, Communications and Mobile Computing - Maui, HI, United States
Duration: Jun 13 2005Jun 16 2005

Publication series

Name2005 International Conference on Wireless Networks, Communications and Mobile Computing
Volume1

Other

Other2005 International Conference on Wireless Networks, Communications and Mobile Computing
CountryUnited States
CityMaui, HI
Period6/13/056/16/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes'. Together they form a unique fingerprint.

  • Cite this

    Ländner, S., & Milenkovic, O. (2005). Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes. In 2005 International Conference on Wireless Networks, Communications and Mobile Computing (pp. 630-635). [1549481] (2005 International Conference on Wireless Networks, Communications and Mobile Computing; Vol. 1). https://doi.org/10.1109/WIRLES.2005.1549481