Research On Low-Complexity And Fast LDPC Decoding Algorithms

Low Density Parity Check Codes are a class of linear block error-correcting codes that can be defined by the very sparse parity-check matrix. Their error performance approach Shannon limits. There are three indexes to assess a decoding algorithm, including the decoding convergence rate, the computation complexity and the decoding performance. How to find a fast LDPC codes decoding method with low complexity and good performance turns to be very important and meaningful.This work in this paper mainly contains the following five aspects:(1).The effects to decoding performance brought by the cycles in the LDPC codes Tanner Graphy were studied. After illustrating the essence of message passing,the thesis describes several LLR-BP decoding methods based on different message passing schedule. Then the convengece rate of the different decoding methods were compared through Density Evolution analyse tool.(2).Considering the drawbacks of flooding and serial message passing schedules, a new schedule named grouping serial were presented. For the algorithm,the message was updated in a serial sequence of m subsets of check nodes(or variable nodes), while the check nodes(or variable nodes) in the same subset were updated simultaneously. In this way,the decoding speed would be faster than the common serial decoding algorithm several times. And the complexity was lower than the flooding decoding algorithm.(3).By studying the structure of Quasi-cyclic LDPC codes, we find that an efficient grouping method suitable for the Quasi-cyclic LDPC codes based on the circulant architecture.Hence,the grouping serial decoding algorithm was fit for Quasi-cyclic LDPC codes,whose speed was at least p times than that of the serial one(p is the dimension of the cyclic permutation matrix in the parity check matrix of Quasi-cyclic LDPC codes).(4).We explained why the magnitudes of a posterior LLRs and ex-LLRs of some bits oscillated every iterations. Two improved algorithms were proposed, IOB BPⅠand IOB BPⅡ, which could improve the decoding performance deteriorated by ex-LLR oscillation.From the computer simulation,we found that for short and middle length LDPC codes,with a simple modification,our proposed algorithms could lower the error floor with low complexity, so they can achieve better BER and BLER than the conventional LLR-BP decoding algorithm.(5).Two improved decoding algorithms were set forth to low the complexity of IOB BPⅡa lgorithm from two different aspects. Firstly, we decreased the messages computation of IOB BPⅡwith forced convergence schedule in each iterations, so we could reduce the overall decoding computation to lower the dedoding complexity. Secondly,a new iteration stopping detemine rule was put forward. We could detect the mean of all the variables'absolute judying message whether be stable or not to decide to stop the current iteration or to let it continue. By doing so,we might reduce the mean decoding iterations to lower the algorithm's complexity. The two improved decoding algorithms all better performance and lower complexity than BP algorithm.