Information Theory and Applications Workshop (ITA)

Trapping set structure of LDPC codes on finite geometries

Qiuju Diao, Ying Yu Tai, Shu Lin, Khaled Abdel-Ghaffar

Published Feb 1, 2013• 9 citations

Abstract

The trapping set structure of LDPC codes constructed based on finite geometries, called finite geometry (FG) LDPC codes, is analyzed using a geometric approach. In this approach, trapping sets in the Tanner graph of an FG-LDPC code are represented by subgeometries of the geometry based on which the code is constructed. Using this geometrical representation, bounds and configurations of trapping sets of an FG-LDPC code can be derived and analyzed.

DOI: 10.1109/ita.2013.6502922

Related papers

LDPC Codes on Partial Geometries: Construction, Trapping Set Structure, and Puncturing

Qiuju Diao, Ying Yu Tai, Shu Lin +1 more

Many known constructions of LDPC codes can be placed in a general framework using the notion of partial geometries. Based on this notion, the structure of such LDPC codes can be analyzed using a geometric approach that illuminates important properties of their parity-check matrices. In this approach, trapping sets are represented by subgeometries of the geometry used to construct the code. Based on the incidence relations between lines and points in this geometry, the structure of trapping sets is investigated. On the other hand, it is shown that removing a subgeometry corresponding to a trapping set gives a punctured matrix which can be used as a parity-check matrix of an LDPC code. This relates trapping sets, represented by subgeometries, and punctured matrices, represented by the residual geometries. The null spaces of these punctured matrices are LDPC codes which inherit many of the good structural properties of the original code. Hence, new LDPC codes, with various lengths and rates, can be obtained by puncturing an LDPC code constructed based on a partial geometry. Furthermore, these punctured matrices and codes can be used in a two-phase decoding scheme to correct combinations of errors and erasures.

IEEE Transactions on Information TheoryNov 19, 201341 citations

Trapping set structure of finite geometry LDPC codes

Qiuju Diao, Ying Yu Tai, Shu Lin +1 more

The trapping set structure of LDPC codes constructed using finite geometries is analyzed. A trapping set is modeled as a sub-geometry of the geometry used to construct an LDPC code. The variable nodes of a trapping set are viewed as points of the geometry and the check nodes adjacent to the variable nodes are viewed as the lines passing through any of these points. Based on this geometrical representation of a trapping set, its configuration can be determined.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 201214 citations

On the stopping distance of finite geometry ldpc codes

Shu‐Tao Xia, Fang‐Wei Fu

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.

IEEE Communications LettersMay 1, 200629 citations

Error floors and finite geometries

Shu Lin, Qiuju Diao, Ian F. Blake

The structure of certain subgraphs of the Tanner graph of an LDPC code, the trapping sets, has been identified as important for the error floor performance of iterative decoding algorithms. To investigate such sets requires the parity check matrix of the code to be generated with sufficient structure that allows useful information to be obtained while giving good codes. Structures that have been considered include combinatorial designs and classical finite geometries. More recently other finite geometric notions such as partial geometries and generalized d-gons have been considered with some success. This work considers aspects of this approach.

International Symposium on Turbo Codes and Iterative Information ProcessingAug 1, 20146 citations

Finite-Geometry LDPC Codes

W.E. Ryan, Shu Lin

Finite geometries, such as Euclidean and projective geometries, are powerful mathematical tools for constructing error-control codes. In the 1960s and 1970s, finite geometries were successfully used to construct many classes of easily implementable majority-logic decodable codes. In 2000, Kou, Lin, and Fossorier [1–3] showed that finite geometries can also be used to construct LDPC codes that perform well and close to the Shannon theoretical limit with iterative decoding based on belief propagation. These codes are called finite-geometry (FG) -LDPC codes. FG-LDPC codes form the first class of LDPC codes that are constructed algebraically. Since 2000, there have been many major developments in construction of LDPC codes based on various structural properties of finite geometries [4–18]. In this chapter, we put together all the major constructions of LDPC codes based on finite geometries under a unified frame. We begin with code constructions based on Euclidean geometries and then go on to discuss those based on projective geometries. Construction of LDPC Codes Based on Lines of Euclidean Geometries This section presents a class of cyclic LDPC codes and a class of quasi-cyclic (QC) LDPC codes constructed using lines of Euclidean geometries. Before we present the constructions of these two classes of Euclidean-geometry (EG)-LDPC codes, we recall some fundamental structural properties of a Euclidean geometry that have been discussed in Chapter 2.

Cambridge University Press eBooksSep 17, 20091 citation

Algorithmic and Combinatorial Analysis of Trapping Sets in Structured LDPC Codes

Stefan Laendner, Olgica Milenković

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 address both these problems from an algorithmic and combinatorial perspective. We 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 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.

Dec 10, 2005140 citations