Investigations on Certain LDPC Decoding Algorithms for Efficient Hardware Implementation

Abstract

In a variety of transmission systems, the data transferred between a source and a receiver gets corrupted due to bandwidth limitations, noise and nonlinearities. Error Control Coding (ECC) is a widely used methodology to minimize the bit and frame error probabilities in various data transfer systems. In recent times, many coding schemes were proposed to improve the reliability, coverage, performance and quality of the transmission by minimizing the probability of the lost information. Low-Density Parity-Check (LDPC) codes belong to a class of linear block codes. They are widely used in many practical applications as they approach Shannon limit with superior error correcting performance. Due to their excellent decoding performance with a relatively simple computational process and suitability for hardware implementation, LDPC codes are considered to be a promising alternative to the other coding schemes. Hence, they are preferred in many advanced wireless communication standards such as IEEE 802.11n, IEEE 802.16e, DVB-S2 etc. In this thesis, various aspects of regular and irregular LDPC codes that can improve their decoding performance without increasing the computational complexity are investigated. The main objective of this thesis is oriented towards two aspects of LDPC decoders: algorithm improvements for efficient error correcting performance and development of low complexity LDPC decoder architectures. These contributions make an effort to achieve a good trade-off between decoding performance and computational complexity. An improved low complex Sum-Product decoding algorithm (SPA) for LDPC codes is proposed. In the proposed algorithm, reduction in the computational complexity is achieved by utilizing Fast Fourier Transform with time shift in the check node update process (FFTh). The improvement in the decoding performance is achieved by utilizing optimized integer constant in the variable node process. The simulation results show that the proposed algorithm achieves overall coding gain improvement in the range of 0.04 dB to 0.46 dB. Moreover, when compared with SPA the proposed decoding algorithm can reduce the total number of arithmetic operations required for the decoding process in the range of 42% to 67%. A modified normalized Min-Sum algorithm is proposed for decoding irregular LDPC codes. The proposed algorithm provides an efficient decoding scheme to enhance the error performance of an irregular LDPC codes without increasing the hardware complexity. An efficient 6-bit quantization scheme is utilized in the proposed algorithm along with the optimally combined normalization and down scaling factors to resolve the magnitude overestimation issue. Through simulation results, the proposed algorithm with good error correcting performances is shown to achieve overall Frame Error Rate (FER) and Bit Error Rate (BER) coding gain improvement in the range of 0.03 dB to 0.39 dB and 0.04 dB to 0.48 dB at FER of 10-3 and BER of 10-5 respectively when compared to other min-sum based decoding algorithms (MSAs). In addition to the coding gain improvement, the proposed algorithm achieves about 10% to 17% reduction in the total number of decoding iterations required to correct the channel errors at relatively low Signal-to-Noise ratio. A modified optimally quantized offset Min-Sum decoding algorithm for low complexity LDPC decoder is proposed. In the proposed algorithm, more effective adjustment for the check node and variable node updating process is achieved by introducing optimally quantized adaptive offset correction factors. Unlike the conventional Offset Min-Sum algorithm and its variants, the offset correction factor of the proposed algorithm can self adapt itself according to the states of both the check node and variable node during each iteration. Simulation results show that the proposed decoding algorithm achieves significant coding gain improvement over other MSAs without additional hardware complexity. In addition to the coding gain improvement, the proposed algorithm reduces 8% to 14% of the decoding iterations required to correct the channel errors at relatively low Signal-toNoise ratio (SNR). Furthermore, in the proposed algorithm the finite word length effects are reduced by utilizing a 6-bit non-uniform quantization scheme. The proposed algorithm with a 6-bit non-uniform quantization scheme achieves about 21.6% reduction in the total number of memory bits required to store the processed data without degradation in the decoding performance. An improved low complex hybrid weighted bit-flipping algorithm is proposed for decoding LDPC codes. Compared to the state-of-the art weighted bit-flipping (WBF) algorithms, the proposed algorithm improves both the coding gain and decoding speed with low computational complexity. From the simulation results, the proposed algorithm is shown to achieve coding gain improvement in the range of 0.14 dB to 1.5 dB at a BER of 10-5 while reducing up to 22% of the iterations required for decoding when compared with conventional WBF algorithms. Moreover, the proposed algorithm while maintaining less computational complexity, achieves about 65% faster decoding convergence when compared to IERRWBF algorithm. An area efficient and high throughput multi-rate quasi-cyclic low-density parity-check (QC-LDPC) decoder for IEEE 802.11n applications is proposed. An overlapped message passing scheme and the non-uniform quantization scheme are incorporated to reduce the overall area and power of the proposed QC-LDPC decoder. In order to enhance the decoding throughput and reduce the size of memories storing soft messages, an improved early termination (ET) scheme and base matrix reordering technique is employed. These techniques significantly reduce the total number of decoding iterations and memory accessing conflicts without mitigating the decoding performance. Equipped with these techniques an area efficient and high throughput multi-rate QC- LDPC decoder is designed, simulated and implemented with Xilinx Virtex6 FPGA for an irregular LDPC code of length 1944 and code rates (1/2–5/6) specified in IEEE 802.11n standard. With a maximum clock frequency of 574.136 MHz to 587.458 MHz the proposed QC-LDPC decoder can achieve throughput in the range of 1.27 Gb/s to 2.17 Gb/s for 10 decoding iterations. Furthermore, by using Cadence RTL compiler with UMC 130nm technology, the core area of the proposed QC-LDPC decoder is found to be 1.42 mm2 with a power dissipation in the range of 101.25 mW to 140.42 mW at 1.2V supply voltage. A power and area efficient multi-rate QC-LDPC decoder is proposed. The proposed decoder design is based on a simplified adaptive normalized min-sum algorithm. The proposed algorithm effectively utilizes two correction factors for check node and variable node update process. This corrects the channel errors at relatively low SNR. In order to reduce the finite word length effects, a 6-bit non-uniform quantization with the overlapped message passing scheme is used. In addition, an improved early termination scheme is also used to reduce the total number of decoding iterations. This reduces the overall power consumption of the decoder. The simulations have been carried out using Xilinx ISE 14.1 and implemented on Virtex 5 FPGA. The proposed QC-LDPC decoder is synthesized using CADENCE Tool with UMC 130 nm technology. The core area of the proposed decoder is 1.16 mm2 . The power consumption of the proposed decoder is 114.3 mW. For a clock frequency of 474 MHz, the proposed decoder achieves a throughput of 3.4Gb/s for 15 decoding iterations. Therefore, through the implementation results, it is evident that the proposed decoder can achieve higher throughput by utilizing only few hardware resources when compared to other LDPC decoders of IEEE 802.11n standard.