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

IEEE Communications Letters

On Turbo-Schedules for LDPC Decoding

Alexandre de Baynast, Predrag Radosavljevic, Ashutosh Sabharwal, Joseph R. Cavallaro

Published May 1, 2006• 4 citations
OpenAlex

Abstract

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.

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

Turbo-schedule for LDPC Decoding

Alexandre de Baynast, Predrag Radosavljevic, Joseph R. Cavallaro

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.

•Sep 28, 2005•0 citations

Fast Decoding Algorithm for Low-Density Parity-Check Codes

Dan Wang

SUMMARY A fast decoding algorithm for low-density parity-check codes is presented based on graph decomposition and two-way message passing schedule. Simulations show that the convergence speed of the proposed algorithm is about twice that of the conventional belief propagation algorithm. key words: LDPC code turbo-type two-way algorithm 1.

IEICE Transactions on Communications•Nov 1, 2005•1 citation

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

An efficient message-passing schedule for LDPC decoding

E. Sharon, Simon N. Litsyn, Jacob Goldberger

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.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 30, 2004•125 citations
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.
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
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.
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
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.