Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Radio and communications technology

Modeling for LDPC serial decoding algorithm

Lei Jing

Published Jan 1, 2006• 0 citations
OpenAlex

Abstract

Message-passing mechanism is an important factor affecting the performance of LDPC decoding. In this paper, we introduce briefly LDPC and sum product decoding algorithm based on floodwater message-passing mechanism proposed by Gallager. On this basis, we introduce a serial mechanism based on check nodes and propose a concrete and feasible decoding algorithm modeling. This serial decoding algorithm processes and passes the messages in a definite sequence of check nodes for ensuring that the updated messages can immediately enter the iterative process so as to improve convergence characteristics of the message passing, and use the feature of interdependence between messages to fuse the message passing steps to reduce required memory and decoding complexity. We use respectively the floodwater decoding algorithm and serial decoding algorithm to perform the performance simulation over AWGN channel. The simulation results show that the decoding performance could be improved by serial decoding algorithm.

Related papers

Analysis of LDPC Decoding Algorithm Based on Serial Schedule

Lei Jing, Caac Scientific

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.

Journal of Sichuan University•Jan 1, 2006•1 citation

Convergence analysis for LDPC serial decoding

Lei Jing

Tanner graph of LDPC and flooding decoding algorithm are briefly introduced.On this condition,present serial decoding algorithm and semi-serial decoding algorithm which based on check nodes.By analysing DE(Density Evolution) and tree depth of message convergence,it's proved that the message convergence speed grows about twice as fast in the serial decoding algorithm compared to the flooding decoding algorithm,and reduce the decoding complexity.Respectively apply flooding decoding algorithm and serial decoding algorithm to simulate over AWGN channel.Theory and results of simulation show that the decoding performance could be improved by serial decoding algorithm.

Journal of Chongqing University of Posts and Telecommunications•Jan 1, 2006•1 citation

The serial message-passing schedule for LDPC decoding algorithms

Mingshan Liu, Shanshan Liu, Yuan Zhou +1 more

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.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Dec 9, 2015•1 citation

Research on a Fast Decoding Method of the Quasi-cyclic LDPC Codes Based on Serial Message-Passing Schedule

Lei Jing, Yongqiang Gao, Jianhui Wang +1 more

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).

•Jan 1, 2008•2 citations

Efficient Serial Message-Passing Schedules for LDPC Decoding

Eran Sharon, Simon N. Litsyn, Jacob Goldberger

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.

IEEE Transactions on Information Theory•Nov 1, 2007•155 citations

Analysis of LDPC code performance over binary symmetric channel

Yuxiang Li

Low-Density Parity-Check code (LDPC) is a kind of linear block error-correcting codes.Sum-product algorithm is an iterative decoding algorithms commonly used in LDPC code decoding.This paper studies into the LDPC code message passing iterative decoding algorithm under the binary symmetric channel (BSC) and simulates the bit error probability,then simulates the convergence of check nodes' and variable nodes' probability density in the iterative process using the method of density evolution.The result show that under a given channel threshold,LDPC code has a good correction performance.

Journal of Northeast Normal University•Jan 1, 2010•0 citations
Message-passing mechanism is an important factor affecting the performance of LDPC decoding. In this paper, we introduce briefly LDPC and sum product decoding algorithm based on floodwater message-passing mechanism proposed by Gallager. On this basis, we introduce a serial mechanism based on check nodes and propose a concrete and feasible decoding algorithm modeling. This serial decoding algorithm processes and passes the messages in a definite sequence of check nodes for ensuring that the updated messages can immediately enter the iterative process so as to improve convergence characteristics of the message passing, and use the feature of interdependence between messages to fuse the message passing steps to reduce required memory and decoding complexity. We use respectively the floodwater decoding algorithm and serial decoding algorithm to perform the performance simulation over AWGN channel. The simulation results show that the decoding performance could be improved by serial decoding algorithm.
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.
Tanner graph of LDPC and flooding decoding algorithm are briefly introduced.On this condition,present serial decoding algorithm and semi-serial decoding algorithm which based on check nodes.By analysing DE(Density Evolution) and tree depth of message convergence,it's proved that the message convergence speed grows about twice as fast in the serial decoding algorithm compared to the flooding decoding algorithm,and reduce the decoding complexity.Respectively apply flooding decoding algorithm and serial decoding algorithm to simulate over AWGN channel.Theory and results of simulation show that the decoding performance could be improved by serial decoding algorithm.
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.
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).
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.
Low-Density Parity-Check code (LDPC) is a kind of linear block error-correcting codes.Sum-product algorithm is an iterative decoding algorithms commonly used in LDPC code decoding.This paper studies into the LDPC code message passing iterative decoding algorithm under the binary symmetric channel (BSC) and simulates the bit error probability,then simulates the convergence of check nodes' and variable nodes' probability density in the iterative process using the method of density evolution.The result show that under a given channel threshold,LDPC code has a good correction performance.