The use of partial geometries to construct parity-check matrices for binary low-density parity-check (LDPC) codes has resulted in the design of successful codes with a probability of error on the AWGN channel close to the Shannon capacity at bit error rate down to $10^{-15}$ . Such considerations have motivated this further investigation. A new and simple construction of a type of partial geometries with a quasi-cyclic (QC) structure is given and their properties are investigated. Two new classes of this type of partial geometries, one based on prime fields and the other based on cyclic subgroups of prime orders of finite fields, are constructed. QC-LDPC codes with good error performances are constructed based on these two new classes of partial geometries. The trapping sets of the partial geometry codes were previously considered using the geometric aspects of the underlying structure to derive information on the size of allowable trapping sets. This topic is further considered here. Finally, there is a natural relationship between partial geometries and strongly regular graphs. The eigenvalues of the adjacency matrices of such graphs are well known, and it is of interest to determine if any of the Tanner graphs derived from the partial geometries are good expanders for certain parameter sets, since it can be argued that codes with good geometric and expansion properties might perform well on the AWGN channel under message-passing decoding.

It is shown that Euclidean geometry LDPC codes in conjunction with their shortened codes obtained by puncturing their parity-check matrices are effective in correcting combinations of errors and erasures with a two-phase decoding scheme. This is due to the large row redundancies of the parity-check matrices of these codes which are given by the incidence matrices of Euclidean geometries.

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.

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.

A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.

Several classes of quasi-cyclic LDPC codes have been proposed in the literature and shown to have excellent performance over noisy channels when decoded with iterative message-passing algorithms. However, by and large, important properties of the codes, including their dimensions, are only given for specific codes based on computer programming. Using Fourier transforms, it is shown that the ranks of parity-check matrices of quasi-cyclic codes can be computed. From these ranks, the dimensions of the codes can be determined. The approach, which unifies most of the known algebraic constructions, is given in detail for three large classes of quasi-cyclic LDPC codes which appear in the literature.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.

This paper shows that a cyclic code can be put into quasi-cyclic form by decomposing a circular parity-check matrix through column and row permutations. Such a decomposition of a circular parity-check matrix of a cyclic code produces a group of shorter cyclic or quasi-cyclic codes and leads to a new method for constructing long cyclic codes from short cyclic codes. Also in this paper, new classes of cyclic and quasi-cyclic LDPC codes are derived from cyclic Euclidean geometry LDPC codes by decomposing their circular parity-check matrices. These new LDPC codes perform well and enlarge the repertoire of cyclic and quasi-cyclic LDPC codes.