Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.
Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.
Finding coding schemes that approach the Shannon capacity limit has been the central theme during the development of error-control coding (ECC).In recent years low-density parity-check (LDPC) codes, due to their remarkable performance under iterative decoding, have received extensive study and have been adopted by many modern advanced communication systems.LDPC codes can be further extended to generalized LDPC (GLDPC) codes and doublygeneralized LDPC (DGLDPC) codes.GLDPC and DGLDPC codes are supersets of LDPC codes that possess more generic code structures.GLDPC and DGLDPC codes are more flexible than LDPC codes, since a richer variety of check nodes (CNs) or variable nodes (VNs) offers additional options and flexibility, which enable many advantages over LDPC codes in numerous scenarios.In this dissertation we focus on improved design methods for finite-length (FL) GLDPC and DGLDPC codes.The first research topic is the error floor behavior of FL-GLDPC and FL-DGLDPC codes.In GLDPC and DGLDPC codes, the existence of generalized CNs and VNs requires more careful management of edge connections for achieving low error floors.In this work the approximate cycle extrinsic message degree (ACE), a cycle parameter used in LDPC codes that reflects the resilience of the cycle to the noise, is generalized to extended ACE (eACE) for GLDPC and DGLDPC codes.By integrating eACE into the progressive-edge-growth (PEG) algorithm and adding more constraints on the connectivity of nodes, the error floor performance of GLDPC and DGLDPC codes can be greatly improved.In practice, designing codes capable of fast encoding is an important issue.Efficiently-encodable (EE) GLDPC and DGLDPC codes are studied and a self-consistent unified framework is proposed for constructing EE iteratively-decodable block codes, including EE-LDPC, EE-GLDPC and EE-DGLDPC codes.The competing nature of the fast encoding speed and the low error floor performance iv Abstract v is analyzed and verified via various simulation results.EE codes are systematic and suitable for puncturing; therefore, they are good candidates for rate-compatible (RC) data transmissions.Based on the characteristics of GLDPC and DGLDPC codes, we devise several systematic puncturing algorithms to provide good puncturing patterns for them.It is shown that we can significantly improve the code performance compared with random puncturing.Over a wide range of code rates, RC EE-GLDPC and EE-DGLDPC codes show advantages over EE-LDPC codes, especially at high signal-to-noise ratios (SNRs).
The design of low-density parity-check (LDPC) code ensembles optimized for a finite number of decoder iterations is investigated. Our approach employs EXIT chart analysis and differential evolution to design such ensembles for the binary erasure channel and additive white Gaussian noise channel. The error rates of codes optimized for various numbers of decoder iterations are compared and it is seen that in the cases considered, the best performance for a given number of decoder iterations is achieved by codes which are optimized for this particular number. The design of generalized LDPC (GLDPC) codes is also considered, showing that these structures can offer better performance than LDPC codes for low-iteration-number designs. Finally, it is illustrated that LDPC codes which are optimized for a small number of iterations exhibit significant deviations in terms of degree distribution and weight enumerators with respect to LDPC codes returned by more conventional design tools.
The design of low-density parity-check (LDPC) code ensembles optimized for a finite number of decoder iterations is investigated. Our approach employs EXIT chart analysis and differential evolution to design such ensembles for the binary erasure channel and additive white Gaussian noise channel. The error rates of codes optimized for various numbers of decoder iterations are compared and it is seen that in the cases considered, the best performance for a given number of decoder iterations is achieved by codes which are optimized for this particular number. The design of generalized LDPC (GLDPC) codes is also considered, showing that these structures can offer better performance than LDPC codes for low-iteration-number designs. Finally, it is illustrated that LDPC codes which are optimized for a small number of iterations exhibit significant deviations in terms of degree distribution and weight enumerators with respect to LDPC codes returned by more conventional design tools.
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 modern communication systems Low-Density Parity Check (LDPC) codes are widely used. It is because of their performance under iterative decoding, hardware-friendly structure and well-known construction methods. For one to construct good LDPC code Density Evolution (DE) can be used, it estimates the decoding threshold, that is it estimates performance of the code. LDPC codes can be further extended to Generalized LDPC (GLDPC) codes, where simple SPC code is replaced with some component code. With more complex structure common DE is no longer correct. This letter presents the upper bound for decoding error and, therefore, an upper bound of a iterative threshold (in dB). It will be shown that the Gaussian approximation gives an upper bound for a decoding error. As one of the results it means that EXIT-charts analysis also gives an upper bound for an iterative threshold for a GLDPC code.
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.