Low-Density Parity-Check (LDPC) codes have recaptured the attention of the scientific community a few years after Turbo codes were invented in the early nineties. Originally proposed in the 1960s at MIT by R. Gallager, LDPC codes represent powerful error correcting codes that allow working very close to the Shannon limit and achieve excellent Bit Error Rate (BER) due to computationally intensive algorithms on the decoder side of the system. Advances in microelectronics introduced small process technologies that allowed developing complex designs incorporating a high number of transistors in Very Large Scale Integration (VLSI) systems. Recently, these processes have been used to develop architectures able of performing LDPC decoding in real-time and delivering considerably high throughputs. Mainly for these reasons and naturally because the patent has expired, they have been adopted by modern communication standards which triggered their popularity, showing how actual they are. Due to the increase of transistor density in VLSI systems, and also to the fact that recently processing speed has risen faster than bandwidth, power and memory walls have created a new paradigm in computer architectures: rather than just increasing the frequency of operation supported by smaller process designs, the introduction of multiple cores on a single chip has become the new trend to provide augmented computational power. This thesis proposes new approaches for these computationally intensive algorithms, by performing parallel LDPC decoding based on ubiquitous multi-core architectures and achieves efficient throughputs that compare well with dedicated VLSI systems. We extensively address the challenges faced in the investigation and development of these programmable solutions, with focus mainly given on flexibility and scalability of the proposed algorithms, throughput and BER performance, and general efficiency of the programmable solutions here presented, that also achieve results more than an order of magnitude superior to those obtained with conventional CPUs. Furthermore, the investigation herein described follows a methodology that analyzes in detail the computational complexity of these decoding algorithms in order to propose strategies to accelerate their processingwhich, if conveniently transposed to other areas of computer science, can demonstrate that in this new multi-core era we may be in the presence of valid alternatives to non-reprogrammable dedicated VLSI hardware that requires non-recurring engineering.
Low-Density Parity-Check (LDPC) codes have recaptured the attention of the scientific community a few years after Turbo codes were invented in the early nineties. Originally proposed in the 1960s at MIT by R. Gallager, LDPC codes represent powerful error correcting codes that allow working very close to the Shannon limit and achieve excellent Bit Error Rate (BER) due to computationally intensive algorithms on the decoder side of the system. Advances in microelectronics introduced small process technologies that allowed developing complex designs incorporating a high number of transistors in Very Large Scale Integration (VLSI) systems. Recently, these processes have been used to develop architectures able of performing LDPC decoding in real-time and delivering considerably high throughputs. Mainly for these reasons and naturally because the patent has expired, they have been adopted by modern communication standards which triggered their popularity, showing how actual they are. Due to the increase of transistor density in VLSI systems, and also to the fact that recently processing speed has risen faster than bandwidth, power and memory walls have created a new paradigm in computer architectures: rather than just increasing the frequency of operation supported by smaller process designs, the introduction of multiple cores on a single chip has become the new trend to provide augmented computational power. This thesis proposes new approaches for these computationally intensive algorithms, by performing parallel LDPC decoding based on ubiquitous multi-core architectures and achieves efficient throughputs that compare well with dedicated VLSI systems. We extensively address the challenges faced in the investigation and development of these programmable solutions, with focus mainly given on flexibility and scalability of the proposed algorithms, throughput and BER performance, and general efficiency of the programmable solutions here presented, that also achieve results more than an order of magnitude superior to those obtained with conventional CPUs. Furthermore, the investigation herein described follows a methodology that analyzes in detail the computational complexity of these decoding algorithms in order to propose strategies to accelerate their processingwhich, if conveniently transposed to other areas of computer science, can demonstrate that in this new multi-core era we may be in the presence of valid alternatives to non-reprogrammable dedicated VLSI hardware that requires non-recurring engineering.
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area.
This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.
In recent years, the amount of digital data which is stored and transmitted for private and public usage has increased considerably. To allow a save transmission and storage of data despite of error-prone transmission media, error correcting codes are used. A large variety of codes has been developed, and in the past decade low-density parity-check (LDPC) codes which have an excellent error correction performance became more and more popular. Today, low-density parity-check codes have been adopted for several standards, and efficient decoder hardware architectures are known for the chosen structured codes. However, the existing decoder designs lack flexibility as only few structured codes can be decoded with one decoder chip. In consequence, different codes require a redesign of the decoder, and few solutions exist for decoding of codes which are not quasi-cyclic or which are unstructured. In this thesis, three different approaches are presented for the implementation of fully programmable LDPC decoders which can decode arbitrary LDPC codes. As a design study, the first programmable decoder which uses a heuristic mapping algorithm is realized on a field-programmable gate array (FPGA), and error correction curves are measured to verify the correct functionality. The main contribution of this thesis lies in the development of the second and the third architecture and an appropriate mapping algorithm. The proposed fully programmable decoder architectures use one-phase message passing and layered decoding and can decode arbitrary LDPC codes using an optimum mapping and scheduling algorithm. The presented programmable architectures are in fact generalized decoder architectures from which the known decoder architectures for structured LDPC codes can be derived.
This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.
Low-Density Parity-Check (LDPC) codes are powerful error correcting codes (ECC). They have recently been adopted by several data communication standards such as DVB-S2 and WiMax. LDPCs are represented by bipartite graphs, also called Tanner graphs, and their decoding demands very intensive computation. For that reason, VLSI dedicated architectures have been investigated and developed over the last few years. This paper proposes a new approach for LDPC decoding on graphics processing units (GPUs). Efficient data structures and an new algorithm are proposed to represent the Tanner graph and to perform LDPC decoding according to the stream-based computing model. GPUs were programmed to efficiently implement the proposed algorithms by applying data-parallel intensive computing. Experimental results show that GPUs perform LDPC decoding nearly three orders of magnitude faster than modern CPUs. Moreover, they lead to the conclusion that GPUs with their tremendous processing power can be considered as a consistent alternative to state-of-the-art hardware LDPC decoders.
Layered decoding is well appreciated in low-density parity-check (LDPC) decoder implementation since it can achieve effectively high decoding throughput with low computation complexity. This work, for the first time, addresses low-complexity column-layered decoding schemes and very-large-scale integration (VLSI) architectures for multi-Gb/s applications. At first, the min-sum algorithm is incorporated into the column-layered decoding. Then algorithmic transformations and judicious approximations are explored to minimise the overall computation complexity. Compared to the original column-layered decoding, the new approach can reduce the computation complexity in check node processing for high-rate LDPC codes by up to 90% while maintaining the fast convergence speed of layered decoding. Furthermore, a relaxed pipelining scheme is presented to enable very high clock speed for VLSI implementation. Equipped with these new techniques, an efficient decoder architecture for quasi-cyclic LDPC codes is developed and implemented with 0.13 µm VLSI implementation technology. It is shown that a decoding throughput of nearly 4 Gb/s at a maximum of 10 iterations can be achieved for a (4096, 3584) LDPC code. Hence, this work has facilitated practical applications of column-layered decoding and particularly made it very attractive in high-speed, high-rate LDPC decoder implementation.
Low-density parity-check (LDPC) codes had a renaissance when they were rediscovered in the 1990’s. Since then LDPC codes have been an important part of the field of error-correcting codes, and have been shown to be able to approach the Shannon capacity, the limit at which we can reliably transmit information over noisy channels. Following this, many modern communications standards have adopted LDPC codes. Error-correction is equally important in protecting data from corruption on a hard-drive as it is in deep-space communications. It is most commonly used for example for reliable wireless transmission of data to mobile devices. For practical purposes, both encoding and decoding need to be of low complexity to achieve high throughput and low power consumption. This thesis provides a literature review of the current state-of-the-art in encoding and decoding of LDPC codes. Message- passing decoders are still capable of achieving the best error-correcting performance, while more recently considered bit-flipping decoders are providing a low-complexity alternative, albeit with some loss in error-correcting performance. An implementation of a low-complexity stochastic bit-flipping decoder is also presented. It is implemented for Graphics Processing Units (GPUs) in a parallel fashion, providing a peak throughput of 1.2 Gb/s, which is significantly higher than previous decoder implementations on GPUs. The error-correcting performance of a range of decoders has also been tested, showing that the stochastic bit-flipping decoder provides relatively good error-correcting performance with low complexity. Finally, a brief comparison of encoding complexities for two code ensembles is also presented.