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

Adaptive Mixed Scheduling for Correcting Errors in Trapping Sets of LDPC Codes

Saejoon Kim, Seunghyuk Lee, Jun Heo, C.S. Rim

Published Jul 1, 2010• 1 citation
Publisher

Abstract

Trapping sets of low-density parity-check codes are the problematic substructures that contribute to the error floor behavior under iterative decoding. Adoption of mixed scheduling for belief propagation decoding has shown to be very effective in solving some of the trapping sets. In this letter, we propose an adaptive mixed scheduling scheme that provides significantly improved code performance compared to existing mixed scheduling schemes.

DOI
10.1109/lcomm.2010.07.092417

Related papers

Improving LDPC Decoders via Informed Dynamic Scheduling

Andres I. Vila Casado, Miguel Griot, Richard D. Wesel

Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The message-passing schedule of the BP algorithm significantly affects the performance of the LDPC decoder. The authors recently presented a novel message-passing schedule, called Informed Dynamic Scheduling (IDS), that selects the message-passing schedule according to the observed rate of change of the messages. IDS yields a lower error-rate performance than traditional message-passing schedules (such as flooding and LBP) because it solves traditional trapping-set errors. However, for short-blocklength LDPC codes, IDS algorithms present non-trapping-set errors in the error floor region. This paper presents a careful analysis of those errors and proposes mixed scheduling strategies, combining LBP with IDS, that solve these non-trapping-set errors. Also, we will show that some lower-complexity techniques, such as mixed scheduling, perform close to the best IDS strategies for larger-blocklength codes.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•31 citations

Trapping Set Error Correction through Adaptive Informed Dynamic Scheduling Decoding of LDPC Codes

Saejoon Kim

Recent studies indicate that sequential scheduling of iterative decoding of low-density parity-check codes can provide improved code performance in comparison with the conventional flooding in terms of decoding success rate and convergence speed. In particular, a class of sequential scheduling schemes known as informed dynamic scheduling (IDS) has shown to outperform other sequential scheduling schemes from its capability to correct trapping set errors. In this letter, we present an adaptive IDS scheme which combines and outperforms previously proposed sequential scheduling schemes.

IEEE Communications Letters•Jul 1, 2012•8 citations

Augmented decoders for LDPC codes

Alex Rigby, JC Olivier, Hermanus Carel Myburgh +2 more

The performance of a belief propagation decoder for low-density parity-check codes is limited by the presence of trapping sets in the code’s graph. This leads to an error floor at higher signal-to-noise ratios. We propose the use of an augmented decoder which operates by iteratively decoding on a set of graphs which have a subset of repeated check nodes. We compare the augmented decoder to other modified belief propagation decoders that have been presented in the literature. We show that for all the codes considered, the augmented decoder yields the best frame error rate in the error floor region.

EURASIP Journal on Wireless Communications and Networking•Aug 2, 2018•3 citations

Two-staged informed dynamic scheduling for sequential belief propagation decoding of LDPC codes

Saejoon Kim, Karam Ko, Jun Heo +1 more

Recent studies have shown that sequential belief propagation decoding of low-density parity-check codes can increase the decoding convergence speed while simultaneously improving the asymptotic performance compared to the conventional flooding scheme. Two of the practical sequential decoding schemes known are the ones by Casado et al. [1] in which informed dynamic scheduling is used for scheduling the sequential updates of the messages. In this letter, we propose a two-staged informed dynamic scheduling that unifies and outperforms the two schemes of [1].

IEEE Communications Letters•Mar 1, 2009•10 citations

An efficient scheduling scheme for layered belief propagation decoding of regular LDPC codes

Hua Li, Hong Wei Ding, Linhua Zheng +3 more

Schedule plays an important role in layered belief propagation (BP) decoding of low-density parity-check (LDPC) codes. It affects the error-rate performance as well as convergence rate of the decoder. In this paper, an efficient scheduling scheme is proposed to arrange the updating order of check nodes for layered BP decoder of regular LDPC codes. This scheme selects check node one at a time based on the reliability of the variable nodes. Specifically each time the check node with maximum number of low-reliability neighbors is selected. For simplicity, we introduce the updating state instead of the real-time messages to represent variable-node reliability. Simulation results on regular LDPC codes prove that the proposed scheduling scheme can obtain efficient schedules with fast convergence and good error-rate performance.

International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)•Oct 1, 2016•6 citations

Belief-propagation with information correction: improved near maximum-likelihood decoding of low-density parity-check codes

Nedeljko Varnica, M.P.C. Fossorier

We propose an improved belief-propagation (BP) decoder for low-density parity-check (LDPC) codes based on channel information correction. We show that our algorithm achieves sizeable performance gains (in waterfall and error floor regions) compared to the standard BP decoder. We verify by examples that the proposed decoder almost achieves the maximum-likelihood decoding performance for short LDPC codes

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•18 citations
Trapping sets of low-density parity-check codes are the problematic substructures that contribute to the error floor behavior under iterative decoding. Adoption of mixed scheduling for belief propagation decoding has shown to be very effective in solving some of the trapping sets. In this letter, we propose an adaptive mixed scheduling scheme that provides significantly improved code performance compared to existing mixed scheduling schemes.
Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The message-passing schedule of the BP algorithm significantly affects the performance of the LDPC decoder. The authors recently presented a novel message-passing schedule, called Informed Dynamic Scheduling (IDS), that selects the message-passing schedule according to the observed rate of change of the messages. IDS yields a lower error-rate performance than traditional message-passing schedules (such as flooding and LBP) because it solves traditional trapping-set errors. However, for short-blocklength LDPC codes, IDS algorithms present non-trapping-set errors in the error floor region. This paper presents a careful analysis of those errors and proposes mixed scheduling strategies, combining LBP with IDS, that solve these non-trapping-set errors. Also, we will show that some lower-complexity techniques, such as mixed scheduling, perform close to the best IDS strategies for larger-blocklength codes.
Recent studies indicate that sequential scheduling of iterative decoding of low-density parity-check codes can provide improved code performance in comparison with the conventional flooding in terms of decoding success rate and convergence speed. In particular, a class of sequential scheduling schemes known as informed dynamic scheduling (IDS) has shown to outperform other sequential scheduling schemes from its capability to correct trapping set errors. In this letter, we present an adaptive IDS scheme which combines and outperforms previously proposed sequential scheduling schemes.
The performance of a belief propagation decoder for low-density parity-check codes is limited by the presence of trapping sets in the code’s graph. This leads to an error floor at higher signal-to-noise ratios. We propose the use of an augmented decoder which operates by iteratively decoding on a set of graphs which have a subset of repeated check nodes. We compare the augmented decoder to other modified belief propagation decoders that have been presented in the literature. We show that for all the codes considered, the augmented decoder yields the best frame error rate in the error floor region.
Recent studies have shown that sequential belief propagation decoding of low-density parity-check codes can increase the decoding convergence speed while simultaneously improving the asymptotic performance compared to the conventional flooding scheme. Two of the practical sequential decoding schemes known are the ones by Casado et al. [1] in which informed dynamic scheduling is used for scheduling the sequential updates of the messages. In this letter, we propose a two-staged informed dynamic scheduling that unifies and outperforms the two schemes of [1].
Schedule plays an important role in layered belief propagation (BP) decoding of low-density parity-check (LDPC) codes. It affects the error-rate performance as well as convergence rate of the decoder. In this paper, an efficient scheduling scheme is proposed to arrange the updating order of check nodes for layered BP decoder of regular LDPC codes. This scheme selects check node one at a time based on the reliability of the variable nodes. Specifically each time the check node with maximum number of low-reliability neighbors is selected. For simplicity, we introduce the updating state instead of the real-time messages to represent variable-node reliability. Simulation results on regular LDPC codes prove that the proposed scheduling scheme can obtain efficient schedules with fast convergence and good error-rate performance.