Since the rediscovery of low-density parity-check (LDPC) codes in the late 1990s, tremendous progress has been made in code construction and design, decoding algorithms, and decoder implementation of these capacity-approaching codes. Recently, LDPC codes are considered for applications such as high-speed satellite and optical communications, the hard disk drives, and high-density flash memory based storage systems, which require that the codes are free of error-floor down to bit error rate (BER) as low as 10−12 to 10−15. FPGAs are usually used to evaluate the error performance of codes, since one can exploit the finite word length and extremely high internal memory bandwidth of an FPGA. Existing FPGA-based LDPC decoders fail to utilize the configurability and read-first mode of embedded memory in the FPGAs, and thus result in limited throughput and codes sizes. Four optimization techniques, i.e., vectorization, folding, message relocation, and circulant permutation matrix (CPM) sharing, are proposed to improve the throughput, scalability, and efficiency of FPGA-based decoders. Also, a semi-automatic CAD tool called QCSYN (Quasi-Cyclic LDPC decoder SYNthesis) is designed to shorten the implementation time of decoders. Using the above techniques, a high-rate (16129,15372) code is shown to have no error-floor down to the BER of 10−14. Also, it is very difficult to construct codes that do not exhibit an error floor down to 10−15 or so. Without detailed knowledge of dominant trapping sets, a backtracking-based reconfigurable decoder is designed to lower the error floor of a family of structurally compatible quasi-cyclic LDPC codes by one to two orders of magnitudes. Hardware reconfigurability is another significant feature of LDPC decoders. A tri-mode decoder for the (4095,3367) Euclidean geometry code is designed to work with three compatible binary message passing decoding algorithms. Note that this code contains 262080 edges (21.3 times of the (2048,1723) 10GBASE-T code) in its Tanner graph and is the largest code ever implemented. Besides, an efficient QC-LDPC Shift Network (QSN) is proposed to reduce the interconnect delay and control logic of circular shift network, a core component in the reconfigurable decoder that supports a family of structurally compatible codes. The interconnect delay and control logic area are reduced by a factor of 2.12 and 8, respectively. Non-binary LDPC codes are effective in combating burst errors. Using the power representation of the elements in the Galois field to organize both intrinsic and extrinsic messages, we present an efficient decoder architecture for non-binary QC-LDPC codes. The proposed decoder is reconfigurable and can be used to decode any code of a given field size. The decoder supports both regular and irregular non-binary QC-LDPC codes. Using a practical metric of throughput per unit area, the proposed implementation outperforms the best implementations published in research literature to date.

Low-density parity-check (LDPC) codes have been intensively studied in the past decade for their capacity-approaching performance. LDPC code implementation complexity and the error-rate floor are still two significant unsolved issues which prevent their application in some important communication systems. In this dissertation, we make efforts toward solving these two problems by introducing the design of a class of LDPC codes called structured irregular repeat-accumulate (S-IRA) codes. These S-IRA codes combine several advantages of other types of LDPC codes, including low encoder and decoder complexities, flexibility in design, and good performance on different channels. It is also demonstrated in this dissertation that the S-IRA codes are suitable for rate-compatible code family design and a multi-rate code family has been designed which may be implemented with a single encoder/decoder. The study of the error floor problem of LDPC codes is very difficult because simulating LDPC codes on a computer at very low error rates takes an unacceptably long time. To circumvent this difficulty, we implemented a universal quasi-cyclic LDPC decoder on a field programmable gate array (FPGA) platform. This hardware platform accelerates the simulations by more than 100 times as compared to software simulations. We implemented two types of decoders with partially parallel architectures on the FPGA: a circulant-based decoder and a protograph-based decoder. By focusing on the protograph-based decoder, different soft iterative decoding algorithms were implemented. It provides us with a platform for quickly evaluating and analyzing different quasi-cyclic LDPC codes, including the S-IRA codes. A universal decoder architecture is also proposed which is capable of decoding of an arbitrary LDPC code, quasi-cyclic or not. Finally, we studied the low-floor problem by focusing on one example S-IRA code. We identified the weaknesses of the code andproposed several techniques to lower the error floor. We successfully demonstrated in hardware that it is possible to lower the floor substantially by encoder and decoder modifications, but the best solution appeared to be an outer BCH code.

Low-Density Parity-check (LDPC) codes have attracted considerable attention due to their capacity approaching performance over AWGN channel and highly parallelizable decoding schemes. They have been considered in a variety of industry standards for the next generation communication systems. In general, LDPC codes achieve outstanding performance with large codeword lengths (e.g., N>1000 bits), which lead to a linear increase of the size of memory for storing all the soft messages in LDPC decoding. In the next generation communication systems, the target data rates range from a few hundred Mbit/sec to several Gbit/sec. To achieve those very high decoding throughput, a large amount of computation units are required, which will significantly increase the hardware cost and power consumption of LDPC decoders. LDPC codes are decoded using iterative decoding algorithms. The decoding latency and power consumption are linearly proportional to the number of decoding iterations. A decoding approach with fast convergence speed is highly desired in practice. This thesis considers various VLSI design issues of LDPC decoder and develops efficient approaches for reducing memory requirement, low complexity implementation, and high speed decoding of LDPC codes. We propose a memory efficient partially parallel decoder architecture suited for quasi-cyclic LDPC (QC-LDPC) codes using Min-Sum decoding algorithm. We develop an efficient architecture for general permutation matrix based LDPC codes. We have explored various approaches to linearly increase the decoding throughput with a small amount of hardware overhead. We develop a multi-Gbit/sec LDPC decoder architecture for QC-LDPC codes and prototype an enhanced partially parallel decoder architecture for a Euclidian geometry based LDPC code on FPGA. We propose an early stopping scheme and an extended layered decoding method to reduce the number of decoding iterations for undecodable and decodable sequence received from channel. We also propose a low-complexity optimized 2-bit decoding approach which requires comparable implementation complexity to weighted bit flipping based algorithms but has much better decoding performance and faster convergence speed.

This book takes a practical hands-on approach to developing low complexity algorithms and transforming them into working hardware. It follows a complete design approach – from algorithms to hardware architectures - and addresses some of the challenges associated with their design, providing insight into implementing innovative architectures based on low complexity algorithms.The reader will learn: - Modern techniques to design, model and analyze low complexity LDPC algorithms as well as their hardware implementation - How to reduce computational complexity and power consumption using computer aided design techniques - All aspects of the design spectrum from algorithms to hardware implementation and performance trade-offs - Provides extensive treatment of LDPC decoding algorithms and hardware implementations - Gives a systematic guidance, giving a basic understanding of LDPC codes and decoding algorithms and providing practical skills in implementing efficient LDPC decoders in hardware - Companion website containing C-Programs and MATLAB models for simulating the algorithms, and Verilog HDL codes for hardware modeling and synthesis

The main contribution of this thesis is the development of LDPC code construction methods for some classes of structured LDPC codes and techniques for reducing decoding time. Two main methods for constructing structured codes are introduced. In the first method, column-weight two LDPC codes are derived from distance graphs. A wide range of girths, rates and lengths are obtained compared to existing methods. The performance and implementation complexity of obtained codes depends on the structure of their corresponding distance graphs. In the second method, a search algorithm based on bit-filing and progressive-edge growth algorithms is introduced for constructing quasi-cyclic LDPC codes. The algorithm can be used to form a distance or Tanner graph of a code. This method could also obtain codes over a wide range of parameters. The outcome of this study is a simple, programmable and high throughput decoder architecture based on matrix permutation and space restriction techniques.