Construction of structured low-density parity-check codes: Combinatorial and algebraic approaches

This dissertation presents several combinatorial and algebraic methods for constructing quasi-cyclic (QC) low-density parity-check (LDPC) codes. Codes designed with these approaches perform as well as pseudo-random LDPC codes in terms of bit-error performance, block-error performance and error-floor collectively. Furthermore, QC-LDPC codes have encoding advantages over other types of LDPC codes. The encoder of a QC-LDPC code can be implemented using simple feedback shift-registers with linear complexity. The construction based on decomposition of circulants derived from finite geometries results in two classes of QC-LDPC codes. A new method for constructing QC-LDPC codes based on Reed-Solomon (RS) codes is also proposed. This method yields a class of QC-LDPC codes with various lengths, rates and minimum distances, whose parity check matrices consist of circulant permutation matrices and whose Tanner graphs have a girth of at least 6. When masking technique is combined, both regular and irregular QC-LDPC codes can be constructed. QC-LDPC codes can also be developed by superposition. This method is especially suited for the design of long codes. An efficient encoding scheme for QC-LDPC codes are proposed, in which the generator matrix in systematic-circulant form is obtained.