On the Construction of Structured LDPC Codes Free of Small Trapping Sets

• Published in: IEEE transactions on information theory 2012-04, Vol.58 (4), p.2280-2302
• Main Authors: Dung Viet Nguyen, Chilappagari, S. K., Marcellin, M. W., Vasic, B.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Applied sciences; Charge carrier processes; Codes; Coding, codes; Decoding; Error correction & detection; Error floor; Exact sciences and technology; Graphs; Information theory; Information, signal and communications theory; Iterative decoding; Latin squares; Merging; Signal and communications theory; structured low-density parity-check codes; Symmetry; Telecommunications and information theory; trapping sets
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2011.2173733

We present a method to construct low-density parity-check (LDPC) codes with low error floors on the binary symmetric channel. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the trapping set ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four cycles.