Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes

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.