To make full use of the valuable radio spectrum, one of the targets of communications system design is to convey as much information as possible through the spectrum (the channel) allocated for the purpose. For a given channel, the amount of information that can be passed through it is upper bounded by the well-known Shannon channel capacity.
The invention of turbo codes in 1993 was a key step in the 50-year effort to design good coding schemes achieving the Shannon capacity. Since then, other coding schemes with similar performance, such as Low Density Parity Check (LDPC) codes and turbo product codes, have been re-discovered or invented. The common characteristics of these codes are that they all can be represented by a large (pseudo-)random graph, and iteratively decoded.
In this dissertation, we treat three topics in the design and analysis of the two most important graph-based coding schemes: turbo codes and LDPC codes.
Together with two component convolutional codes, an interleaver is a key component of a turbo code. We introduce a class of deterministic interleavers for turbo codes based on permutation polynomials over Z N . It is observed that the performance of a turbo code using these permutation polynomial-based interleavers is usually dominated by a subset of input weight 2m error events. Due to the structure of these interleavers, we derive a simple method to find the weight spectrum of those error events. Therefore good permutation polynomials can be searched for a given component code to achieve better performance.
LDPC codes can be constructed using an interleaver. In a previous work, the use of maximum length linear congruential sequences (MLLCS) has been proposed for the construction of interleavers for regular LDPC codes with data node degree 3. Since the smallest loop size (girth) is a key characteristic of the graph of the LDPC code, a sufficient condition on the parameters of the MLLCS to generate a graph with girth larger than 4 is given. We extend the sufficient condition to general irregular LDPC codes and also provide sufficient conditions to guarantee even larger girth.
It is observed that the error floor of LDPC code (bit error performance at high signal-to-noise ratios) is usually caused by trapping sets, which are sets of data nodes that cannot be corrected by the iterative decoder. We develop an approximated linear system model for the iterative decoding process in a trapping set. Then the probability that the trapping set can be corrected can be estimated by observing the response of the linear system. Using the idea from the analysis of the linear system, the iterative decoder for regular LDPC codes can be slightly modified to greatly decrease the error floor.