Efficient Algorithms for the Construction of QC-LDPC Codes from a Girth and Cycle Analysis

Quasi-cyclic low-density parity-check (QC-LDPC) codes constitute a subclass of LDPC codes that enjoys significant relevance for application purposes due in part to their ability to be described compactly, and the existence of efficient encoding and decoding algorithms. They now appear in industry standards and are used in many settings, such as deep-space, satellite, cellular, and wireless communications. One way to construct QC-LDPC codes is by taking an N-fold graph cover, called Tanner graph, of a relatively small bipartite graph, called protograph, and imposing the condition that the permutation matrices assigned to the edges are circulant permutation matrices. Certain substructures in the Tanner graph play a fundamental role in determining the performance of the code under iterative decoding algorithms. A question that arises is whether it is possible to reduce, or eliminate, these undesirable substructures. Solving the following problem, in the case of QC-LDPC codes, can help to answer this question: What is the smallest positive integer N for which there exists a QC-LDPC code with blocklength n_vN and girth g constructed from a protograph G having an n_c x n_v biadjacency matrix B?

In this dissertation, we investigate four projects that are related to this problem. First, we determine the necessary and sufficient conditions required to obtain a desired girth in the Tanner graph of QC-LDPC codes. We provide some efficient algorithms to generate these conditions. Second, we provide a general formula to count the number of k-cycles, N_k, for k < 2g, in the Tanner graph of QC-LDPC codes. This formula works for both regular and irregular protographs. We present an efficient strategy to calculate N_k. Third, we modify the progressive edge-growth (PEG) algorithm using the necessary and sufficient girth conditions in the form of forbidden sets and propose four efficient construction strategies of QC-LDPC codes. Fourth, we present a promising connection between the lifting factor N (and therefore the blocklength of a QC-LDPC code) and the product of the pivots of the Hermite normal form of a matrix constructed from certain substructures in the protograph called tailless backtrackless closed walks. This connection is presented as a conjecture and appears to be a necessary condition to answer the problem stated above.