The algebraic low-density parity-check (LDPC) codes have received great attention in the practical applications to communication and data storage systems due to their fruitful structural properties and excellent overall performances. This dissertation investigates the following topics regarding the construction, analysis and decoding of the algebraic LDPC codes.The first contribution is a comprehensive rank analysis of the algebraic quasi-cyclic (QC) LDPC (QC-LDPC) codes constructed based on two arbitrary subsets of a finite field, which generalizes the rank analysis results in the previous literature. Also investigated is a flexible algebraic construction of QC-LDPC codes with large row redundancy based on field partitions. This construction results in a large class of binary regular QC-LDPC codes with flexible choices of rates and lengths that are shown to perform well over the additive white Gaussian noise (AWGN) channel. Secondly, to resolve the issue of decoder complexity caused by relatively high density of the parity-check matrices of algebraic LDPC codes, an effective revolving iterative decoding (RID) scheme is developed for algebraic cyclic and QC-LDPC codes. The proposed RID scheme significantly reduces the hardware implementation complexities. Also presented is a variation of the RID scheme, called merry-go-round (MGR) decoding scheme, which maintains the circulant permutation matrix (CPM) structure that is desirable for the hardware implementation but lost in the RID scheme, while preserving the merits of reducing decoder complexity. The proposed RID and MGR decoding schemes may enhance the applications of algebraic LDPC codes.Lastly, a general algebraic construction of QC-LDPC convolutional codes, also called spatially coupled (SC) QC-LDPC codes, is proposed. Simulation results show that the constructed algebraic SC-QC-LDPC codes can outperform their non-algebraic counterparts. Also investigated is the rate compatibility of the constructed SC-QC-LDPC codes using the regular puncturing scheme.

Due to their capacity-approaching performance which can be achieved with practically implementable iterative decoding algorithms devised based on belief-propagation, low-density parity-check (LDPC) codes have rapid dominance in the applications requiring error control coding. This dissertation is intended to address certain important aspects of the aforementioned issues about LDPC codes. Subjects to be investigated include: (1) flexible and systematic methods for constructing binary LDPC codes with quasi-cyclic structure based on finite fields; (2) construction of high-rate and low-rate quasi-cyclic (QC) LDPC codes to achieve very low error rates without error-floor and with high rate of decoding convergence; (3) construction of binary QC-LDPC codes whose Tanner graphs have girth 8 or larger and contain minimum number of short cycles; (4) developing effective algorithms for enumerating short cycles in the Tanner graph of LDPC codes; (5) devising reduced-complexity decoding schemes and algorithms for binary QC-LDPC codes; (6) effective matrix-theoretic methods for constructing nonbinary (NB) LDPC codes; and (7) reduced-complexity decoding schemes and algorithms for NB LDPC codes. The dissertation presents a simple, flexible and systematic method to construct both binary and nonbinary LDPC codes with quasi-cyclic (QC) structure based on two arbitrary subsets of a finite field. One technique for constructing QC-LDPC codes whose Tanner graphs have girth 8 or larger is also proposed. Simulation results show that these constructed codes perform well over both the additive white Gaussian noise and the binary erasure channels. Also presented in this dissertation is a reduced-complexity decoding scheme to decode binary QC-LDPC codes. The decoding scheme is devised based on the section-wise cyclic structure of the parity-check matrix of a QC-LDPC code. The proposed decoding scheme combined with iterative decoding algorithms of LDPC codes results in no or a relative small performance degradation. Two efficient algorithms for enumerating short cycles in the Tanners graph of LDPC codes are presented. One algorithm is devised based on iterative message-passing algorithm by introducing messages in term of monomials, which is an improvement of the work of Karimi and Banihashemi. The other one is based on the trellis of an LDPC code by finding the partial paths which can form cycles. By removing certain number of cycles, a new code whose Tanner graph has a smaller number of short cycles, a larger girth, or both can be constructed. An algorithm to count and find cycles of lengths four and six in a class of QC-LDPC codes is also proposed. In this dissertation, we also briefly investigate one of the algebraic-based constructions of LDPC code, namely superposition (SP) construction, and one of the graph-based constructions, namely protograph-based (PTG-based) construction. The SP-construction method is re-interpreted in a broader scope from both the algebraic and the graph-theoretic perspectives. From the graph-theoretic point of view, it is shown that the PTG-based construction of LDPC codes is a special case of the SP-construction. An algebraic method for constructing PTG-based QC-LDPC codes through decomposing a small matrix is proposed. Several methods for constructing QC-LDPC codes through the SP-construction are also presented.

In this book, leading authorities unify algebraic- and graph-based LDPC code designs and constructions into a single theoretical framework.

It has long been recognized that there are fascinating connections between cod ing theory, cryptology, and combinatorics. Therefore it seemed desirable to us to organize a conference that brings together experts from these three areas for a fruitful exchange of ideas. We decided on a venue in the Huang Shan (Yellow Mountain) region, one of the most scenic areas of China, so as to provide the additional inducement of an attractive location. The conference was planned for June 2003 with the official title Workshop on Coding, Cryptography and Combi natorics (CCC 2003). Those who are familiar with events in East Asia in the first half of 2003 can guess what happened in the end, namely the conference had to be cancelled in the interest of the health of the participants. The SARS epidemic posed too serious a threat. At the time of the cancellation, the organization of the conference was at an advanced stage: all invited speakers had been selected and all abstracts of contributed talks had been screened by the program committee. Thus, it was de cided to call on all invited speakers and presenters of accepted contributed talks to submit their manuscripts for publication in the present volume. Altogether, 39 submissions were received and subjected to another round of refereeing. After care ful scrutiny, 28 papers were accepted for publication.