Efficient Search of Girth-Optimal QC-LDPC Codes

• Published in: IEEE transactions on information theory 2016-04, Vol.62 (4), p.1552-1564
• Main Authors: Tasdighi, Alireza, Banihashemi, Amir H., Sadeghi, Mohammad-Reza
• Format: Article
• Language: English
• Subjects: Bipartite graph; Codes; Computer science; Computers; Cyclic Liftings; Girth; Girth- Optimal QC-LDPC Codes; Graph theory; Indexes; Information theory; Manganese; Parity check codes; Probability distribution; Protograph Codes; Quasi-Cyclic Low-Density Parity-Check (QCLDPC) Codes
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2016.2523979

In this paper, we study the cycle structure of quasi-cyclic (QC) low-density parity-check (LDPC) codes with the goal of obtaining the shortest code with a given degree distribution and girth. We focus on QC-LDPC codes, whose Tanner graphs are cyclic liftings of fully connected base graphs of size 3 × n, n ≥ 4, and obtain minimal lifting degrees that result in girths 6 and 8. This is performed through an efficient exhaustive search, and as a result, we also find all the possible non-isomorphic codes with the same minimum block length, girth, and degree distribution. The exhaustive search, which is ordinarily a formidable task, is made possible by pruning the search space of many codes that are isomorphic to those previously examined in the search process. Many of the pruning techniques proposed in this paper are also applicable to QC-LDPC codes with base graphs other than the 3 × n fully connected ones discussed here, as well as to codes with a larger girth. To further demonstrate the effectiveness of the pruning techniques, we use them to search for QC-LDPC codes with girths 10 and 12, and find a number of such codes that have a shorter block length compared with the best known similar codes in the literature. In addition, motivated by the exhaustive search results, we tighten the lower bound on the block length of QC-LDPC codes of girth 6 constructed from fully connected 3 × n base graphs, and construct codes that achieve the lower bound for an arbitrary value of n ≥ 4.