▼ Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area. The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees. With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm. However, regular LDPC codes outperform their irregular counterparts in term of their error floors. Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic. Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied. In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair. The contribution mainly includes three parts. In the first part, the relationship between cycles and unfavorable combinatorial characteristics (or trapping set for codes over AWGN channels and stopping set for codes over BEC channels) of LDPC codes is analyzed. The analysis indicates that large girths of LDPC codes could lead to low error floors. Based on this analysis, an approach of designing any individual irregular LDPC code with girth of six is proposed. The second part presents a novel algorithm of enumerating the worst unfavorable combinatorial characteristics with the help of building a searching tree. With the help of the enumeration results of this novel algorithm, the worst unfavorable combinatorial characteristics can be eliminated by refining the parity-check matrices of LDPC codes, which results in the improvement of the error floor performance of LDPC codes based on our simulation results. The above mentioned methods focus on designing LDPC codes with low error floors from the encoder side of the LDPC codes. Another possible approach of lowering the error floors is from the decoder side, which is studied in the third part of this dissertation. In the third part, the trapping sets of LDPC codes are extensively analyzed and a concept of pseudo-cycle is proposed. Based on the analysis, we present an improved decoder, a two-stage decoder, for LDPC codes to enable dealing with the negative influence caused by those unfavorable combinatorial properties of LDPC codes. The simulation results show that the error floors of LDPC codes can be lowered by more than one order of magnitude. Unlike the current methods for lowering the error floors of LDPC codes, all the approaches proposed in this dissertation can be applied to any individual LDPC code. Based on our simulation results, these approaches can effectively decrease the error floors for any specific LDPC code. Advisors/Committee Members: Dill, Jeffrey.

▼ 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. Advisors/Committee Members: Takeshita, Oscar Y.

▼ Tail biting circular trellis block codes (TBC)2 used along with iterative Maximum A-Posteriori (MAP) decoders achieve performance very close to the Shannon limit. A Low Density Parity Check (LDPC) code using a Sum Product Algorithm (SPA) decoder is also known to achieve comparable performance. In this work the performance of (TBC)2 encoder used with an SPA decoder is presented. The goal of this research is to compare the performance of (TBC)2 encoder with different iterative decoders.In order to use the SPA for decoding, a parity check (H) matrix representation of the (TBC)2 is developed. It is shown that for small block lengths this H matrix achieves comparable performance. For larger block sizes the H matrix representation of the (TBC)2 encoder is found non-optimal for SPA decoding and the performance of the code is degraded. Advisors/Committee Members: Dill, Jeffrey.

▼ Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate at the cost of higher decoding complexity. The high complexity is mainly caused by the complicated computations in the check node processing and the large memory requirement. In this thesis, two VLSI designs for NB-LDPC decoders based on two novel check node processing schemes are proposed. The first design is based on forward-backward check node processing. A novel scheme and corresponding architecture are developed to implement the elementary step of the check node processing. In our design, layered decoding is applied and only nm less than q messages are kept on each edge of the associated Tanner graph. The computation units and the scheduling of the computations are optimized in the context of layered decoding to reduce the area requirement and increase the speed. This thesis also introduces an overlapped method for the check node processing among different layers to further speed up the decoding. From complexity and latency analysis, our design is much more efficient than any previous design. Our proposed decoder for a (744, 653) code over GF(32) has also been synthesized on a Xilinx Virtex-2 Pro FPGA device. It can achieve a throughput of 9.30 Mbps when 15 decoding iterations are carried out. The second design is based on a proposed trellis based check node processing scheme. The proposed scheme first sorts out a limited number of the most reliable variable-to-check (v-to-c) messages, then the check-to-variable (c-to-v) messages to all connected variable nodes are derived independently from the sorted messages without noticeable performance loss. Compared to the previous iterative forward-backward check node processing, the proposed scheme not only significantly reduced the computation complexity, but eliminated the memory required for storing the intermediate messages generated from the forward and backward processes. Inspired by this novel c-to-v message computation method, we propose to store the most reliable v-to-c messages as ‘compressed’ c-to-v messages. The c-to-v messages will be recovered from the compressed format when needed. Accordingly, the memory requirement of the overall decoder can be substantially reduced. Compared to the previous Min-max decoder architecture, the proposed design for a (837, 726) code over GF(32) can achieve the same throughput with only 46% of the area. Advisors/Committee Members: Zhang, Xinmiao.

▼ With the rapid increase in the utility of data and voice services, there is a demand for higher data rates and reliability in wireless communications. A wireless communication channel is prone to regrading effects such as shadow fading, multi-path fading, and inters symbol interference (ISI) etc. Orthogonal Frequency Division Multiplexing (OFDM), a candidate for the 4th generation wireless systems, mitigates these effects and supports higher data rates. The performance analysis of a complex system like COFDM, is a challenging task where analytical methods become cumbersome to be used. Simulation based approaches provide a fair estimate of the performance in such cases. In this thesis, the performance of an OFDM system on Additive White Gaussian(AWGN), Rayleigh fading channels and Clarke/Jake’s [11] fading Channels have been analyzed with different coding schemes. Reed-Solomon (RS) codes, convolutional codes, TCM codes and LDPC codes have been analyzed in detail. Some of the modern wireless communication channel models have been studied and remodeled, the performances and characteristics have been showed clearly by the simulation result of these models. The effect of inter-carrier interference (ICI) and inter-symbol interference (ISI) on OFDM systems for different channel conditions has been studied and the performances of few techniques to mitigate the degradation due to ISI, ICI have been investigated, such as Cyclic Prefix (CP) or Zero Padding (ZP). Advisors/Committee Members: Kim, Junghwan.

▼ As newly invented packet erasure codes, digital fountain codes (LT codes and Raptor codes) under iterative message passing decoding can work very efficiently in computer networks for large scale data distribution (e.g., greater than 64000 bits) without knowledge of the states of individual lossy channels, regardless of the propagation modes. Some researchers have moved further and found that fountain codes can achieve near capacity performance over AWGN channels. However, little literature on the research of a fountain code’s decoding overhead had been obtained, especially for short and moderate-length data (e.g., smaller than 10000 bits). We are interested in the overheads of fountain codes of different kinds or designs because a harsh communication condition can hurt some decoding schemes by limiting the number of received encoded symbols. Moreover, we have only found in literature studies of Raptor codes whose precodes are rate 0.98 left-regular, right-Poisson LDPC codes, but performance with other types of pre-codes is unknown. In this dissertation, we review conventional fountain codes and describe two system models for packet erasure fountain codes and bit error correcting fountain codes under message passing decoding over binary erasure channels or AWGN channels. We assess Raptor codes with different kinds of pre-codes, introduce maximum likelihood decoding to both LT codes and Raptor codes, and propose a hybrid message passing and fast maximum likelihood decoding algorithm for LT codes. Our simulation results show that error rate and overhead depends on both decoding algorithm and pre-code characteristics. In general, maximum likelihood decoding consumes much less overhead than message passing decoding. Our hybrid algorithm can realize very low overhead with short-length LT codes but still enable fast decoding. LT codes can decrease the fraction of overhead as data length grows but Raptor codes may not. A higher rate pre-code can accomplish better performance of Raptor codes than a lower rate pre-code, and the structure of the pre-code may not matter. Advisors/Committee Members: Dill, Jeffrey.

▼ Due to its near Shannon limit performance in high speed communication, low-density parity check (LDPC) code has performed a strong comeback recent years. In this work, a partial parallel decoding architecture is proposed based on a column-layered LDPC decoding scheme [2]. The purpose of this work is to make a tradeoff between area cost and throughput. I construct the structure of the partial parallel decoder, and compare its throughput and area cost with the design in [2]. Then I obtain the synthesis results of my design with Xilinx FPGA tool. The device utilization summary and timing summary are provided at the end of this work. Comparing with the design in [2], the partial parallel design in my work needs much less hardware resources. As a result, when the area is limit and a lower throughput is acceptable, my design can be considered instead of the design in [2]. Advisors/Committee Members: Zhang, Xinmiao.