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

A simple taboo-based soft-decision decoding algorithm for expander codes

Alexander M. Chan, Frank R. Kschischang

Published Jul 1, 1998• 10 citations
Publisher

Abstract

We present a simple soft-decision decoding algorithm that modifies Sipser and Spielman's (see IEEE Trans, Inform. Theory, vol.42, p.1710-22, Nov. 1996) hard-decision sequential "bit-flipping" algorithm for decoding expander codes. The algorithm incorporates symbol reliability information and a simple "taboo" function that avoids repeated flipping of the same bit. The two algorithms have comparable simplicity, but simulations show that the soft-decision algorithm results in both improved performance and-because fewer decoding iterations are necessary-improved speed.

DOI
10.1109/4234.703905

Related papers

Soft-decision decoding algorithm hased on reliability for LDPC code

Guangxi Zhu

A hard-decision decoding algorithm based on parity-check sum for LDPC code was first described, and then a soft-decision decoding algorithm based on parity-check sum and symbol reliability was proposed. The soft-decision decoding algorithm incorporates received symbol reliability information and a simple taboo function that avoids repeated flipping of the same bit. A maximum votes queue algorithm for the numbers of which the parity-check functions were not satisfied was applied to quickly search the flipping bit. Approaches above all were used to improve the performance of the flipping-bit algorithm based on parity-check sum.

Information technology newsletter•Jan 1, 2004•0 citations

An Efficient Decoding Algorithm for Low-Density Parity-Check Codes

Yang Cao

We present a simple decoding algorithm that modifies soft bit-flipping algorithm for decoding LDPC codes. In our method, a new parameter is explored to distinguish the variables (symbols) belonging to the same number of unsatisfied constraints. A token is also assigned in the method to avoid repeated flipping of the same variable, rather than using a constant taboo length. Our scheme shows a similar computational load as the taboo-based algorithm, while having a similar decoding performance as the belief propagation algorithm.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 1, 2005•1 citation

An efficient bit-flipping decoding algorithm for LDPC codes

Tso-Cho Chen

In this paper, a new method for improving hard-decision bit-flipping (BF) decoding is proposed for low-density parity-check codes. The flipping criterion is derived theoretically from the soft-decision belief-propagation decoding algorithm. The proposed BF decoding algorithm is channel independent and is improved by introducing a more efficient method for computing the reliability of the parity checks. Extensive simulations are provided to demonstrate the efficiency of the proposed algorithm. Simulation results show that the proposed algorithm can achieve about 1.5dB coding gain improvement at BER = 5×10−6while reducing up to 48% iterations for decoding and maintaining low decoding complexity, compared with the conventional weighted BF algorithm.

Cross Strait Quad-Regional Radio Science and Wireless Technology Conference (CSQRWC)•Jul 1, 2012•6 citations

Algoritmos de decodificação abrupta para códigos LDGM

Fernando Pujaico Rivera

Since Gallager introduced Bit-Flipping (BF ) decoding with hard-decision for Low-Density Parity-Check Codes (LDP C), other two variants were proposed by Sipser and Spielman for expander codes.Later, a soft-decision version of BF decoding, known as Modified Weighted BF (MW BF ) decoding, was investigated.This thesis proposes modified versions of Sipser and Spielman algorithms.Simulation results for long systematic Low-Density Generator Matrix (LDGM) codes show a better performance of the proposed versions.Moreover, for moderate length systematic LDGM codes, simulation results show performance similar to that of MWBF decoding with the advantage of not requiring floating-point operations.

•Jun 3, 2011•0 citations

Channel-independent weighted bit-flipping decoding algorithm for low-density parity-check codes

T.-C. Chen

In this study, a new method for improving hard-decision bit-flipping (BF) decoding is proposed for low-density parity-check codes. The flipping criterion is derived theoretically from the soft-decision belief-propagation decoding algorithm. The proposed BF decoding algorithm is channel independent and is improved by introducing a more efficient method for computing the reliability of the parity checks. Extensive simulations are provided to demonstrate the efficiency of the proposed algorithm. Simulation results show that the proposed algorithm can achieve about 1.6 dB coding gain improvement at BER=10−5 while reducing up to 53% iterations for decoding and maintaining low-decoding complexity, compared with the conventional weighted BF algorithm.

IET Communications•Nov 27, 2012•10 citations

Generalized minimum distance iterative decoding of expander codes

Vitaly Skachek, Ron M. Roth

Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•27 citations
We present a simple soft-decision decoding algorithm that modifies Sipser and Spielman's (see IEEE Trans, Inform. Theory, vol.42, p.1710-22, Nov. 1996) hard-decision sequential "bit-flipping" algorithm for decoding expander codes. The algorithm incorporates symbol reliability information and a simple "taboo" function that avoids repeated flipping of the same bit. The two algorithms have comparable simplicity, but simulations show that the soft-decision algorithm results in both improved performance and-because fewer decoding iterations are necessary-improved speed.
A hard-decision decoding algorithm based on parity-check sum for LDPC code was first described, and then a soft-decision decoding algorithm based on parity-check sum and symbol reliability was proposed. The soft-decision decoding algorithm incorporates received symbol reliability information and a simple taboo function that avoids repeated flipping of the same bit. A maximum votes queue algorithm for the numbers of which the parity-check functions were not satisfied was applied to quickly search the flipping bit. Approaches above all were used to improve the performance of the flipping-bit algorithm based on parity-check sum.
We present a simple decoding algorithm that modifies soft bit-flipping algorithm for decoding LDPC codes. In our method, a new parameter is explored to distinguish the variables (symbols) belonging to the same number of unsatisfied constraints. A token is also assigned in the method to avoid repeated flipping of the same variable, rather than using a constant taboo length. Our scheme shows a similar computational load as the taboo-based algorithm, while having a similar decoding performance as the belief propagation algorithm.
In this paper, a new method for improving hard-decision bit-flipping (BF) decoding is proposed for low-density parity-check codes. The flipping criterion is derived theoretically from the soft-decision belief-propagation decoding algorithm. The proposed BF decoding algorithm is channel independent and is improved by introducing a more efficient method for computing the reliability of the parity checks. Extensive simulations are provided to demonstrate the efficiency of the proposed algorithm. Simulation results show that the proposed algorithm can achieve about 1.5dB coding gain improvement at BER = 5×10−6while reducing up to 48% iterations for decoding and maintaining low decoding complexity, compared with the conventional weighted BF algorithm.
Since Gallager introduced Bit-Flipping (BF ) decoding with hard-decision for Low-Density Parity-Check Codes (LDP C), other two variants were proposed by Sipser and Spielman for expander codes.Later, a soft-decision version of BF decoding, known as Modified Weighted BF (MW BF ) decoding, was investigated.This thesis proposes modified versions of Sipser and Spielman algorithms.Simulation results for long systematic Low-Density Generator Matrix (LDGM) codes show a better performance of the proposed versions.Moreover, for moderate length systematic LDGM codes, simulation results show performance similar to that of MWBF decoding with the advantage of not requiring floating-point operations.
In this study, a new method for improving hard-decision bit-flipping (BF) decoding is proposed for low-density parity-check codes. The flipping criterion is derived theoretically from the soft-decision belief-propagation decoding algorithm. The proposed BF decoding algorithm is channel independent and is improved by introducing a more efficient method for computing the reliability of the parity checks. Extensive simulations are provided to demonstrate the efficiency of the proposed algorithm. Simulation results show that the proposed algorithm can achieve about 1.6 dB coding gain improvement at BER=10−5 while reducing up to 53% iterations for decoding and maintaining low-decoding complexity, compared with the conventional weighted BF algorithm.
Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.