Dynamic Schedule Algorithm For Sum-product Decoding Of LDPC Codes

Low-density parity-check (LDPC) codes have the potential of approaching Shannon limit with sum-product algorithm. The message passing schedule over the Tanner graph directly affects convergence rate, complexity and error performance. In general flooding schedule, all the variable nodes, and subsequently all the check nodes, pass new messages to their neighbors. The complexity of the algorithm is normal and the convergence speed is low. As to some dynamic schedules based on residual, the convergence of decoding can be accelerated, thus improve the error floor effect. The main problems of dynamic schedules exist in the greediness and decoding complexity.Firstly, relative-residual-based dynamic schedule (RRDS) is proposed to abate the greediness. Among those nodes that have the same residual, the node with the least reliability, i.e., the greatest relative residual, has the priority of update. Obviously, the schedule is more purposeful and thus weakens the greediness. Simulation results show that RRDS can accelerate the convergence stably and obtain lower error floor than the famous variable to check residual belief propagation (VC-RBP) for different types of LDPC codes.Secondly, check-node-wise RRDS (CN-RRDS) and variable-node-wise RRDS (VN-RRDS) are proposed to reduce the complexity of RRDS. In RRDS, the edge with the greatest relative residual is found before its neighboring nodes are updated. Herein the search space consists of all the edges in the Tanner graph. While in the node-wise RRDS's, the search space is composed of nodes instead of edges. Because the number of nodes is much less than the number of edges in the Tanner, the searching time of node-wise schedule is shortened greatly. Simulation results, the performance of the two node-wise RRDS's is very close to the RRDS for a variety of LDPC codesFinally, min-sum VN-RRDS (MVN-RRDS) and min-sum CN-RRDS (MCN-RRDS) are proposed. Min-sum is used to get relative-residual, which further lowers the computation complexity. Simulation results show that the two min-sum versions of node-wise RRDS's have faster convergence rate and lower error floor than VC-RBP for various LDPC codes. Since variable-nodes have more check information, variable-node-wise schedules are generally better than check-node-wise schedules.