Research On Symbol Flipping Decoding Algorithms For Non-binary LDPC Codes

Low-Density Parity-Check Codes(LDPC Codes)have been widely used in many digital communication fields,such as disk storage and deep space communications,due to their low decoding complexity and Shannon limit-approaching good performance.Compared with binary LDPC codes,non-binary LDPC codes have stronger ability of correcting burst errors.However,the classical decoding algorithms for non-binary LDPC codes,known as the q-ary sum-product algorithm and the extended min-sum algorithm and so on,generally have higher computational complexity.The majority logic decoding algorithms and symbol flipping decoding algorithms can reduce the decoding complexity of non-binary LDPC codes with little error rate performance loss.The symbol flipping decoding algorithms based on prediction(SFDP)can narrow the performance gap between the existing symbol flipping decoding algorithms and the message passing decoding algorithms greatly by comparing the information before and after symbol flipping to determine which symbol should be flipped.However,compared with the existing symbol flipping decoding algorithms,the SFDP algorithms have higher decoding complexity,especially at low signal-to-noise ratios.Meanwhile,the SFDP algorithms suffer error floors for some non-binary LDPC codes.In order to improve the decoding performance and accelerate the decoding convergence rate,the SFDP algorithms for non-binary LDPC codes are thoroughly investigated in this dissertation.The main research works are summarized as follows:1.The value of the objective function in the SFDP algorithms fluctuates around the local maximum and thus cannot converge correctly.To solve this problem,two randomly penalized SFDP algorithms for non-binary LDPC codes are proposed,by introducing the Gaussian noise or uniform noise into the flipping metric as a random penalty item to overcome the pseudo local maximum problem.Theoretical analysis shows that the proposed randomly penalized SFDP algorithms can increase the probability of correctly flipping symbols compared with the existing SFDP algorithms.Simulation results show that the proposed randomly penalized SFDP algorithms have significant performance improvement than that of the existing SFDP algorithms,especially at high signal-to-noise ratio regions.2.The SFDP algorithms for non-binary LDPC codes only flip one symbol per iteration which results in slow decoding convergence speed.To solve this problem,phased flipping rules of the SFDP algorithms for non-binary LDPC codes are proposed by observing the changing trend of the objective function values during the iterations while flipping different number of symbols.The SFDP algorithms based on these two flipping rules flip two symbols fixedly or flip more symbols dynamically at each iteration in the first phase to increase the value of the objective functions rapidly,whereas only one symbol at each iteration in the second phase is flipped to make sure that the objective functions converge to the maximum correctly.Simulation results shows that the proposed SFDP algorithms based on two-phased flipping rules can significantly reduce the average number of iterations and speed up the decoding convergence with similar decoding performance to that of the existing SFDP algorithms.3.In order to reduce the decoding complexity of SFDP algorithms,an early stopping criterion of the SFDP algorithms for non-binary LDPC codes is proposed by tracking the fluctuation features of the objective function during the iterations.The early stopping strategy can help the SFDP algorithms reduce some unnecessary decoding iterations.Simulations results shows that the proposed stopping criterion can significantly reduce the average number of iterations with slight error performance degradation,especially at low signal-to-noise ratio regions.4.In order to avoid the SFDP algorithms for non-binary LDPC codes trapping into the local optimum,the momentum-based SFDP algorithms for non-binary LDPC codes are proposed by introducing the momentum term which represents the ability of each symbol to maintain the current state into the flipping metrics.On this basis,the momentum-based randomly penalized SFDP algorithms for non-binary LDPC codes are proposed.Simulation results show that the momentum-based SFDP algorithms perform better than the existing SFDP algorithms with a little extra complexity,and the proposed momentum-based randomly penalized SFDP algorithms can further reduce the error floor of non-binary LDPC codes.