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

Reliability-based syndrome decoding of LDPC codes

Guangwen Li, Guangzeng Feng

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

Aiming at bridge gap between maximum likelihood decoding (MLD) and belief propagation (BP) decoding for short or medium LDPC codes, we present one modified ordered statistics decoding (OSD) reprocessing method, which is serially concatenated with standard BP. Meanwhile, two novel points in implementation are addressed. For one thing, the new definition of bit reliability proposed enhances error-correcting performance via centralizing more decoding errors of standard BP within the scope of order-p OSD where p ≤ 2. For another, one way of reducing computational complexity is put forward in selecting optimal error pattern among all candidates. Simulation results demonstrate our approach could achieve good tradeoff between reprocessing performance and computational complexity. Techniques on further improvement are also discussed briefly. Reliability-based syndrome decoding of LDPC codes 1 I.

Related papers

Generalized reliability-based syndrome decoding for LDPC codes

Guangwen Li, Guangzeng Feng

Aiming at bridging the gap between the maximum likelihood decoding (MLD) and the suboptimal iterative decodings for short or medium length LDPC codes, we present a generalized ordered statistic decoding (OSD) in the form of syndrome decoding, to cascade with the belief propagation (BP) or enhanced min-sum decoding. The OSD is invoked only when the decoding failures are obtained for the preceded iterative decoding method. With respect to the existing OSD which is based on the accumulated log-likelihood ratio (LLR) metric, we extend the accumulative metric to the situation where the BP decoding is in the probability domain. Moreover, after generalizing the accumulative metric to the context of the normalized or offset min-sum decoding, the OSD shows appealing tradeoff between performance and complexity. In the OSD implementation, when deciding the true error pattern among many candidates, an alternative proposed proves to be effective to reduce the number of real additions without performance loss. Simulation results demonstrate that the cascade connection of enhanced min-sum and OSD decodings outperforms the BP alone significantly, in terms of either performance or complexity.

arXiv:0710.5230•Oct 27, 2007•0 citations

Generalised reliability‐based syndrome decoding of LDPC codes

Guangwen Li, Guangzeng Feng

Abstract Aimed at bridging the gap between the maximum likelihood and the suboptimal decoding schemes for short or medium LDPC codes, a generalised ordered statistic decoding (OSD), in the form of syndrome decoding, is presented in the paper. The OSD is invoked once when a nonzero decoding syndrome is returned for the preceded belief propagation (BP) or min‐sum (MS) variants. With respect to the OSD with an accumulative reliability metric for the BP in the logarithmic likelihood ratio (LLR) domain, we extend the metric to the BP in the probability domain. Furthermore, the OSD with the metric specific for the MS variants, shows an appealing trade‐off between performance and complexity. Meanwhile, when determining the optimal error pattern estimation, an alternative designed to reduce the number of the required real additions proves to be effective. Copyright © 2008 John Wiley & Sons, Ltd.

European Transactions on Telecommunications•Aug 5, 2008•4 citations

Efficient Near Maximum-Likelihood Reliability-Based Decoding for Short LDPC Codes

Weiyang Zhang, Chentao Yue, Yonghui Li +1 more

In this paper, we propose an efficient decoding algorithm for short low-density parity check (LDPC) codes by carefully combining the belief propagation (BP) decoding and ordered statistics decoding (OSD) algorithms. Specifically, a modified BP (mBP) algorithm is applied for a certain number of iterations prior to OSD to enhance the reliability of the received message, where an offset parameter is utilized in mBP to control the weight of the extrinsic information in message passing. By carefully selecting the offset parameter and the number of mBP iterations, the number of errors in the most reliable positions (MRPs) in OSD can be reduced by mBP, thereby significantly improving the overall decoding performance of error rate and complexity. Simulation results show that the proposed algorithm can approach the maximum-likelihood decoding (MLD) for short LDPC codes with only a slight increase in complexity compared to BP and a significant decrease compared to OSD. Specifically, the order- (m -1) decoding of the proposed algorithm can achieve the performance of the order-m OSD.

arXiv:2306.00443•International Conference on Communications•Jun 9, 2024•8 citations

Iterative reliability based decoding of LDPC codes

M.P.C. Fossorier

In this work, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between BP decoding which remains suboptimum, and maximum likelihood decoding (MLD) which is too complex to be implemented for the codes considered. A stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is also proposed for this combined decoding approach. Simulations results for several Gallager LDPC codes and different set cyclic (DSC) codes of hundreds of information bits are given and elaborated.

IEEE International Symposium on Information Theory (ISIT)•Nov 13, 2002•4 citations

Fast Reliability-based Algorithm of Finding Minimum-weight Codewords for LDPC Codes

Guangwen Li, Guangzeng Feng

Despite the NP hardness of acquiring minimum distance $d_m$ for linear codes theoretically, in this paper we propose one experimental method of finding minimum-weight codewords, the weight of which is equal to $d_m$ for LDPC codes. One existing syndrome decoding method, called serial belief propagation (BP) with ordered statistic decoding (OSD), is adapted to serve our purpose. We hold the conjecture that among many candidate error patterns in OSD reprocessing, modulo 2 addition of the lightest error pattern with one of the left error patterns may generate a light codeword. When the decoding syndrome changes to all-zero state, the lightest error pattern reduces to all-zero, the lightest non-zero error pattern is a valid codeword to update lightest codeword list. Given sufficient codewords sending, the survived lightest codewords are likely to be the target. Compared with existing techniques, our method demonstrates its efficiency in the simulation of several interested LDPC codes.

arXiv:0710.1589•Oct 8, 2007•0 citations

Effective BP-ORBGRAND Scheme for Short LDPC Codes

Qing Yuan, Lingjun Kong, Tengda Yang +2 more

Low-density parity-check (LDPC) codes have been widely used in practice due to their excellent error correction capabilities. However, the error correction performance of traditional decoding algorithms for LDPC codes is limited under short block lengths. To address this problem, this paper proposes an effective scheme that contains two stages for decoding short LDPC codes. In the first stage, the traditional belief propagation (BP) iterative algorithm is used to decode an LDPC code. The decoding process terminates if a codeword is obtained in this stage. Otherwise, the second stage decoding is invoked, in which the ordered reliability bits guessing random additive noise decoding (ORBGRAND) algorithm is applied. The accumulated log-likelihood ratios in the first stage are used to order the test error patterns in the ORBGRAND algorithm. Simulation results indicate that the proposed BP-ORBGRAND scheme can outperform the traditional BP iterative algorithm with relatively low additional complexity. Compared with the decoding scheme that concatenates the BP algorithm and the order statistics decoding (OSD) algorithm, the proposed decoding scheme has similar performance and the operations involved can be efficiently implemented in the hardware platform. All these indicate that the proposed scheme is desirable for practical purposes.

IEEE Access•Jan 1, 2026•0 citations
Aiming at bridge gap between maximum likelihood decoding (MLD) and belief propagation (BP) decoding for short or medium LDPC codes, we present one modified ordered statistics decoding (OSD) reprocessing method, which is serially concatenated with standard BP. Meanwhile, two novel points in implementation are addressed. For one thing, the new definition of bit reliability proposed enhances error-correcting performance via centralizing more decoding errors of standard BP within the scope of order-p OSD where p ≤ 2. For another, one way of reducing computational complexity is put forward in selecting optimal error pattern among all candidates. Simulation results demonstrate our approach could achieve good tradeoff between reprocessing performance and computational complexity. Techniques on further improvement are also discussed briefly. Reliability-based syndrome decoding of LDPC codes 1 I.
Aiming at bridging the gap between the maximum likelihood decoding (MLD) and the suboptimal iterative decodings for short or medium length LDPC codes, we present a generalized ordered statistic decoding (OSD) in the form of syndrome decoding, to cascade with the belief propagation (BP) or enhanced min-sum decoding. The OSD is invoked only when the decoding failures are obtained for the preceded iterative decoding method. With respect to the existing OSD which is based on the accumulated log-likelihood ratio (LLR) metric, we extend the accumulative metric to the situation where the BP decoding is in the probability domain. Moreover, after generalizing the accumulative metric to the context of the normalized or offset min-sum decoding, the OSD shows appealing tradeoff between performance and complexity. In the OSD implementation, when deciding the true error pattern among many candidates, an alternative proposed proves to be effective to reduce the number of real additions without performance loss. Simulation results demonstrate that the cascade connection of enhanced min-sum and OSD decodings outperforms the BP alone significantly, in terms of either performance or complexity.
Abstract Aimed at bridging the gap between the maximum likelihood and the suboptimal decoding schemes for short or medium LDPC codes, a generalised ordered statistic decoding (OSD), in the form of syndrome decoding, is presented in the paper. The OSD is invoked once when a nonzero decoding syndrome is returned for the preceded belief propagation (BP) or min‐sum (MS) variants. With respect to the OSD with an accumulative reliability metric for the BP in the logarithmic likelihood ratio (LLR) domain, we extend the metric to the BP in the probability domain. Furthermore, the OSD with the metric specific for the MS variants, shows an appealing trade‐off between performance and complexity. Meanwhile, when determining the optimal error pattern estimation, an alternative designed to reduce the number of the required real additions proves to be effective. Copyright © 2008 John Wiley & Sons, Ltd.
In this paper, we propose an efficient decoding algorithm for short low-density parity check (LDPC) codes by carefully combining the belief propagation (BP) decoding and ordered statistics decoding (OSD) algorithms. Specifically, a modified BP (mBP) algorithm is applied for a certain number of iterations prior to OSD to enhance the reliability of the received message, where an offset parameter is utilized in mBP to control the weight of the extrinsic information in message passing. By carefully selecting the offset parameter and the number of mBP iterations, the number of errors in the most reliable positions (MRPs) in OSD can be reduced by mBP, thereby significantly improving the overall decoding performance of error rate and complexity. Simulation results show that the proposed algorithm can approach the maximum-likelihood decoding (MLD) for short LDPC codes with only a slight increase in complexity compared to BP and a significant decrease compared to OSD. Specifically, the order- (m -1) decoding of the proposed algorithm can achieve the performance of the order-m OSD.
In this work, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between BP decoding which remains suboptimum, and maximum likelihood decoding (MLD) which is too complex to be implemented for the codes considered. A stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is also proposed for this combined decoding approach. Simulations results for several Gallager LDPC codes and different set cyclic (DSC) codes of hundreds of information bits are given and elaborated.
Despite the NP hardness of acquiring minimum distance dmd_mdm​ for linear codes theoretically, in this paper we propose one experimental method of finding minimum-weight codewords, the weight of which is equal to dmd_mdm​ for LDPC codes. One existing syndrome decoding method, called serial belief propagation (BP) with ordered statistic decoding (OSD), is adapted to serve our purpose. We hold the conjecture that among many candidate error patterns in OSD reprocessing, modulo 2 addition of the lightest error pattern with one of the left error patterns may generate a light codeword. When the decoding syndrome changes to all-zero state, the lightest error pattern reduces to all-zero, the lightest non-zero error pattern is a valid codeword to update lightest codeword list. Given sufficient codewords sending, the survived lightest codewords are likely to be the target. Compared with existing techniques, our method demonstrates its efficiency in the simulation of several interested LDPC codes.
Low-density parity-check (LDPC) codes have been widely used in practice due to their excellent error correction capabilities. However, the error correction performance of traditional decoding algorithms for LDPC codes is limited under short block lengths. To address this problem, this paper proposes an effective scheme that contains two stages for decoding short LDPC codes. In the first stage, the traditional belief propagation (BP) iterative algorithm is used to decode an LDPC code. The decoding process terminates if a codeword is obtained in this stage. Otherwise, the second stage decoding is invoked, in which the ordered reliability bits guessing random additive noise decoding (ORBGRAND) algorithm is applied. The accumulated log-likelihood ratios in the first stage are used to order the test error patterns in the ORBGRAND algorithm. Simulation results indicate that the proposed BP-ORBGRAND scheme can outperform the traditional BP iterative algorithm with relatively low additional complexity. Compared with the decoding scheme that concatenates the BP algorithm and the order statistics decoding (OSD) algorithm, the proposed decoding scheme has similar performance and the operations involved can be efficiently implemented in the hardware platform. All these indicate that the proposed scheme is desirable for practical purposes.