Research On Improved Decoding Algorithms For Low-density Parity-check (LDPC) Codes

Low-density parity-check (LDPC) codes have been widely used in the real systembecause of its outstanding metrics, such as simple description, low decoding complexity,possible parallel implementation, flexible to be used, low error floor, etc. With the potential ofLDPC codes being continuously excavated, the codes are expected to have broaderapplications in broadband wireless communications, satellite communications, Ethernettransmission, etc. That is why LDPC codes have been a hot research field in recent years.We focus on the construction of LDPC codes. In code construction, it is necessary toreduce the number of short cycles to achieve better code performance. Therefore we need todetect the number of cycles in the Tanner graph of the corresponding LDPC code. Anotherfocus of our research is to improve decoding performance. The improvement could be carriedout in two ways. One is to improve the decoding performance and speed of convergencewithout increasing the total computational complexity. The other is to reduce the totalcomputational complexity without performance loss.In this dissertation, we focus on the improved algorithms for counting the number ofcycles and decoding for LDPC codes. The target of this study is to propose a faster algorithmfor counting the number of cycles and better decoding algorithms. The major contributions ofthis dissertation are as follows:(1) Three new modified weighted bit-flipping (WBF) decoding algorithms have beenproposed to achieve better performance. They are combined modified weighted bit-flipping(CM-WBF) decoding algorithm, mixed modified weighted bit-flipping (MM-WBF) decodingalgorithm and reliability adjustment weighted bit-flipping (RA-WBF) decoding algorithm.CM-WBF is proposed for finite geometry low-density parity-check (FG-LDPC) codes. Itis constructed by combining two WBF algorithms and makes use of the feature that two WBFalgorithms often select different error bits in decoding process. Simulation results show thatby carefully choosing the two WBF algorithms to be combined, the new algorithm can offer abetter trade-off among performance, complexity, and convergence compared with M-WBF,LC-WBF and RR-WBF algorithms for FG-LDPC codes. With almost the same complexity,CM-WBF performs about0.15dB~0.3dB better and reduces the average convergence numberof iterations by half compared with other WBF algorithms.MM-WBF is proposed mainly for irregular LDPC codes. Based on CM-WBF algorithm,MM-WBF innovatively proposes the concepts of the main and assistant algorithms, anddevelops priority strategies of the two algorithms to achieve performance improvements. Simulation results show that with almost the same computational complexity, MM-WBFperforms about0.3dB~2.0dB better and reduces the average convergence number of iterationsby half compared with RR-WBF, IM-WBF and LC-WBF algorithms. Moreover, MM-WBFachieves similar improvement for regular LDPC codes.RA-WBF is an innovative WBF algorithm. It locates and corrects the error bits moreaccurately to obtain better performance by adjusting the reliability of some bits of a receivedcodeword in the decoding process. This idea of RA-WBF algorithm can be easily extended toexisting WBF decoding algorithms and improve the decoding performance effectively.The research productions are published in Journal of Computational InformationSystems (JCIS),2012International Conference on Wireless Communications and SignalProcessing (WCSP’2012) and2013International Conference on Computational Intelligenceand Security (CIS’2013).(2) Three new belief propagation decoding algorithms have been proposed to achievebetter performance or lower complexity. They are Oscillating Shuffled BP (OS-BP),Tchebyshev-Padé approximation BP (TPA-BP) and rational function approximation BP(RFA-BP) decoding algorithms.OS-BP is based on shuffled BP decoding algorithm and optimizes the messagetransmission route from check nodes to bit nodes. It improves performance by0.15dB andreduces the average number of iterations for convergence by about30%without increasingthe total complexity compared with the shuffled BP algorithm. Furthermore, to solve theproblem of relatively large delay in hardware implementation, we propose group oscillatingshuffled BP (GOS-BP) decoding algorithm, which solves the problem by the groupingprocess.TPA-BP and RFA-BP decoding algorithm are proposed to reduce the high computationalcomplexity in the standard LLR BP algorithm. TPA-BP and RFA-BP use Tchebyshev-Padéapproximation polynomial and rational functions approximation polynomial respectively toreplace tanh(x) function to reduce complexity. Compared with the standard LLR BP decodingalgorithm, the proposed algorithms significantly reduce computational complexity withoutnoticeable performance loss. These approximation ideas can be easily extended to othervariations of BP decoding.The research productions are published in Journal of Computational InformationSystems (JCIS), etc.(3) A new fast algorithm for counting the number of cycles in LDPC codes is proposedin this dissertation. The existing typical counting algorithm called cycle shape analysis counting algorithm counts the number of cycles sequentially, such as4-cycle first, then6-cycle, next8-cycle, etc., which is not efficient. The proposed algorithm, which is based onDijkstra algorithm in graph theory and the nature of the Tanner graph of LDPC codes, countsthe number of cycles once detected. The new algorithm greatly improves counting efficiency.Simulation results show that the new algorithm reduces counting time by1to2orders ofmagnitude compared with the typical counting algorithm.The research productions are published in Journal of Computer Applications.