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

Turbo-schedule for LDPC Decoding

Alexandre de Baynast, Predrag Radosavljevic, Joseph R. Cavallaro

Published Sep 28, 2005• 0 citations
OpenAlex

Abstract

A major drawback of the low density parity-check codes (LDPC) versus the turbo-codes is their comparative low convergence speed: 30 iterations vs. 8-10 iterations for the turbo-codes.Recently, Hocevar showed by simulations that the convergence rate of the LDPC decoder can be accelerated by exploiting a 'turboscheduling' for the bit-node messages.In this paper, we extend this principle 1) for the check messages, 2) for both check and bit nodes messages alternatively (hybrid version).We compare the convergence speed of these schedules by performing the Density Evolution Analysis.Results show that that the convergence rate is about two times increased for most of the LDPC codes in comparison with the standard message passing.Simulations validate the effectiveness of the proposed schedules.

Related papers

Optimized Message Passing Schedules for LDPC Decoding

Predrag Radosavljevic, Alexandre de Baynast, Joseph R. Cavallaro

The major drawback of the LDPC codes versus the turbo-codes is their comparative low convergence speed: 25-30 iterations vs. 8-10 iterations for turbo-codes. Recently, Hocevar showed by simulations that the convergence rate of the LDPC decoder can be accelerated by exploiting a `turbo-scheduling' applied on the bit-node messages (rows of the parity check matrix). In this paper, we show analytically that the convergence rate for this type of scheduling is about two times increased for most of the regular LDPC codes. Second we prove that `turbo-scheduling' applied on the rows of the parity check matrix is identical belief propagation algorithm as standard message passing algorithm. Furthermore, we propose two new message passing schedules: 1) a turbo-scheduling is applied on the check-node messages (columns of the parity check matrix); and 2) a hybrid version of both previous schedules where the turbo-effect is applied on both check-nodes and bit-nodes. Frame error rate simulations validate the effectiveness of the proposed schedules

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Mar 22, 2006•68 citations

On Turbo-Schedules for LDPC Decoding

Alexandre de Baynast, Predrag Radosavljevic, Ashutosh Sabharwal +1 more

The convergence rate of LDPC decoding is comparatively slower than turbo code decoding: 25 LDPC iterations versus 8-10 iterations for turbo codes. Recently, Mansour proposed a â turbo-scheduleâ to improve the convergence rate of LDPC decoders. In this letter, we first extend the turbo-scheduling principle to the check messages. Second, we show analytically that the convergence rate of both turbo-schedules is about twice as fast as the standard message passing algorithm for most LDPC codes.

IEEE Communications Letters•May 1, 2006•4 citations

Optimized decoding schedule for irregular LDPC codes

Xuwei Chen, Hui Ling Yu, Youyun Xu

Recently, the concept of layered decoding schedule for Low-Density Parity-Check codes has been introduced. But the advantage of layered decoding schedule for irregular LDPC codes is not as obvious as regular LDPC codes. The major drawback of the layered irregular LDPC codes versus the layered regular LDPC codes is its comparative low convergence decoding speed. Simulation results show that different bit node degrees of irregular LDPC codes significantly contribute to the decoding performance. The decoding performance of bit nodes with different degrees is of great difference. Bit nodes with small degrees always converge slower than larger ones. In this paper, we propose an optimized decoding schedule for irregular LDPC codes to accelerate the decoding convergence rate. Meanwhile, for the irregular LDPC decoder, the faster decoding speed means a higher throughput and almost the same error performance.

IET International Communication Conference on Wireless Mobile and Computing (CCWMC)•Jan 1, 2009•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•158 citations

Convergence Analysis of Serial Message-Passing Schedules for LDPC Decoding

Eran Sharon, Simon N. Litsyn, Jacob Goldberger

Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, 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 when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1

•Apr 3, 2006•10 citations

Analysis of Complexity and Convergence Speed of Sequential Schedules for Decoding LDPC Codes

Sunghwan Kim, Min‐Ho Jang, Song‐Nam Hong +1 more

In this paper, a sequential message-passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes is analyzed. This decoding algorithm shows better bit error rate (BER) performance than the conventional message-passing decoding algorithm, especially for the small number of iterations. Analytical results tell us that as the number of partitioned subsets of check nodes increases, the BER performance becomes better. We also derive the recursive equations for mean values of messages at check and variable nodes by using density evolution with Gaussian approximation. Finally, the analytical results are conflrmed by the simulation results.

•Jan 1, 2006•2 citations
A major drawback of the low density parity-check codes (LDPC) versus the turbo-codes is their comparative low convergence speed: 30 iterations vs. 8-10 iterations for the turbo-codes.Recently, Hocevar showed by simulations that the convergence rate of the LDPC decoder can be accelerated by exploiting a 'turboscheduling' for the bit-node messages.In this paper, we extend this principle 1) for the check messages, 2) for both check and bit nodes messages alternatively (hybrid version).We compare the convergence speed of these schedules by performing the Density Evolution Analysis.Results show that that the convergence rate is about two times increased for most of the LDPC codes in comparison with the standard message passing.Simulations validate the effectiveness of the proposed schedules.
The major drawback of the LDPC codes versus the turbo-codes is their comparative low convergence speed: 25-30 iterations vs. 8-10 iterations for turbo-codes. Recently, Hocevar showed by simulations that the convergence rate of the LDPC decoder can be accelerated by exploiting a `turbo-scheduling' applied on the bit-node messages (rows of the parity check matrix). In this paper, we show analytically that the convergence rate for this type of scheduling is about two times increased for most of the regular LDPC codes. Second we prove that `turbo-scheduling' applied on the rows of the parity check matrix is identical belief propagation algorithm as standard message passing algorithm. Furthermore, we propose two new message passing schedules: 1) a turbo-scheduling is applied on the check-node messages (columns of the parity check matrix); and 2) a hybrid version of both previous schedules where the turbo-effect is applied on both check-nodes and bit-nodes. Frame error rate simulations validate the effectiveness of the proposed schedules
Recently, the concept of layered decoding schedule for Low-Density Parity-Check codes has been introduced. But the advantage of layered decoding schedule for irregular LDPC codes is not as obvious as regular LDPC codes. The major drawback of the layered irregular LDPC codes versus the layered regular LDPC codes is its comparative low convergence decoding speed. Simulation results show that different bit node degrees of irregular LDPC codes significantly contribute to the decoding performance. The decoding performance of bit nodes with different degrees is of great difference. Bit nodes with small degrees always converge slower than larger ones. In this paper, we propose an optimized decoding schedule for irregular LDPC codes to accelerate the decoding convergence rate. Meanwhile, for the irregular LDPC decoder, the faster decoding speed means a higher throughput and almost the same error performance.
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.
Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, 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 when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1
In this paper, a sequential message-passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes is analyzed. This decoding algorithm shows better bit error rate (BER) performance than the conventional message-passing decoding algorithm, especially for the small number of iterations. Analytical results tell us that as the number of partitioned subsets of check nodes increases, the BER performance becomes better. We also derive the recursive equations for mean values of messages at check and variable nodes by using density evolution with Gaussian approximation. Finally, the analytical results are conflrmed by the simulation results.