In this paper, we present a layered decoding algorithm for non-binary LDPC codes. Differing from the flooding message-passing schedule in conventional designs, the proposed scheme updates check node messages in serial. Furthermore, since fully serial decoding will lead to long latency, the locally-parallel globally-serial schedule is adopted. Basically the check nodes can be divided into several groups, i.e. layers. The layers are processed one by one while the check nodes in each layer are processed in parallel. Simulation results show that the proposed algorithm not only brings some improvement in error correcting performance but also gives some advantage in VLSI implementation of efficient partially parallel decoders.
In this paper, we present a layered decoding algorithm for non-binary LDPC codes. Differing from the flooding message-passing schedule in conventional designs, the proposed scheme updates check node messages in serial. Furthermore, since fully serial decoding will lead to long latency, the locally-parallel globally-serial schedule is adopted. Basically the check nodes can be divided into several groups, i.e. layers. The layers are processed one by one while the check nodes in each layer are processed in parallel. Simulation results show that the proposed algorithm not only brings some improvement in error correcting performance but also gives some advantage in VLSI implementation of efficient partially parallel decoders.
Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved.
The conventional message-passing schedule for LDPC decoding algorithms is the so-called flooding schedule. It has the disadvantage that the updated messages cannot be used until next iteration, thus reducing the convergence speed . In this case, the Layered Decoding algorithm (LBP) based on serial message-passing schedule is proposed. In this paper the decoding principle of LBP algorithm is briefly introduced, and then proposed its two improved algorithms, the grouped serial decoding algorithm (Grouped LBP) and the semi-serial decoding algorithm .They can improve LBP algorithm's decoding speed while maintaining a good decoding performance.
LDPC and sum product decoding algorithm based on flooding schedule which invented by Gallager are briefly introduced.On this condition,present a serial schedule for LDPC decoding.Such serial decoding algorithm processes and passes messages according to some order of check nodes or variable nodes,assuring the updated messages could join iterative process immediately,therefore improve convergence property,and utilize the relationship between messages,improve message passing process,it can reduce required memory.Analyses the complexity of both algorithms,verifies the serial algorithm which based on check nodes could reduces decoding complexity greatly,and simulates over AWGN channel.Results of simulation show that the decoding performance could be improved by serial algorithm.
An efficient decoding schedule for low-density parity-check (LDPC) codes that outperforms the conventional approach, in terms of both complexity and performance, is presented. Conventionally, in each iteration, all symbol nodes and, subsequently, all the check nodes, send messages to their neighbors ("flooding schedule"). In contrast, in the proposed method, the updating of nodes is performed according to a serial schedule which propagates the information twice as fast. A density evolution (DE) algorithm for asymptotic analysis of the new schedule is derived, showing that, when working near the code's capacity, the decoder converges in approximately half the number of iterations. In addition, a concentration theorem is proved, showing that, for a randomly chosen serial schedule, code graph, and decoder input, the decoder's performance approaches its expected one as predicted by the DE algorithm, when the code length increases.
Non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes when the code length is moderate. For the first time, this paper proposes a partial-parallel decoder architecture based on the Min-max algorithm for quasi-cyclic NB-LDPC codes. A novel boundary tracking based scheme and corresponding architecture are developed to implement the elementary step of the check node processing. In addition, layered decoding is applied, and the hardware units are optimized to reduce the latency and area. This paper also introduces an overlapped method for the check node processing among different layers to further speed up the decoding. From complexity analysis, the proposed decoder with 5 iterations for a (837,726) code over GF(25) can easily achieve 60 Mbps throughput on ASIC devices. It is 40% more efficient than prior designs.
A new fast decoding method of Quasi-Cyclic LDPC(QC-LDPC)codes, named semi-serial decoding algorithm, is presented through contraposing the shortcoming of flood decoding method.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 are updated simultaneously. In this way,the decoding speed would be faster than the common serial decoding algorithm several times. An efficient grouping method suitable for the quasi-cyclic LDPC codes based on the circulant architecture is proposed.Simulation results show that,under the same complexiry,the proposed algorithm fastens the decoding speed of quasi-cyclic LDPC codes, meanwhile, it inherits all the merits of the serial massage-passing decoding algorithm. The conclusion is that the speed of the semi-serial decoding method is at least p times than that of the serial one(p is the number of rows of the cyclic permutation matrix in the parity check matrix of quasi-cyclic LDPC codes).