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 International Symposium on Information Theory (ISIT)

Error Rate Estimation of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels Using Cycle Enumeration

Hua Xiao, Amir H. Banihashemi

Published Jun 1, 2007• 4 citations
Publisher

Abstract

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

DOI
10.1109/isit.2007.4557138

Related papers

Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

Hua Xiao, Amir H. Banihashemi

The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.

IEEE Transactions on Communications•Jun 1, 2009•35 citations

Estimation of Bit and Frame Error Rates of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

IEEE Transactions on Communications•Dec 1, 2007•52 citations

Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

arXiv:cs/0612011•Canadian Workshop on Information Theory (CWIT)•Jun 1, 2007•12 citations

Error rate estimation of finite-length low-density parity-check codes decoded by soft-decision iterative algorithms

Hua Xiao, Amir H. Banihashemi

This paper describes a combinatorial approach to estimate the error rate performance of low-density parity-check (LDPC) codes decoded by (quantized) soft-decision iterative decoding algorithms. The method is based on efficient enumeration of input vectors with small distances to a reference vector whose elements are selected to be the most reliable values from the input alphabet. Several techniques, including modified cycle enumeration, are employed to reduce the complexity of the enumeration. The error rate estimate is derived by testing the input vectors of small distances and estimating the contribution of larger distance vectors. We demonstrate by a number of examples that the proposed method provides accurate estimates of error rate with computational complexity much lower than that of Monte Carlo simulations, especially at the error floor region.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•5 citations

Hard-Decision Performance of LDPC Codes on Binary Symmetric Channels with Small Crossover Probabilities

Hua Xiao, Amir H. Banihashemi

Upper and lower bounds are derived on the frame error rate (FER) of low-density parity-check (LDPC) codes decoded by hard-decision iterative algorithms over binary symmetric channels (BSC). The bounds, which are tight for sufficiently small crossover probabilities of the channel, provide a good estimate of FER in this region. The derivation of the bounds is based on the enumeration of low-weight error patterns at the input of the decoder and is much less complex than the conventional Monte Carlo simulation in the crossover probability range of interest. The proposed method can be applied to any LDPC code and for any decoding algorithm

Biennial Symposium on Communications•Jul 10, 2006•4 citations

Error Rate Estimation of Low-Density Parity-Check Codes Decoded by Quantized Soft-Decision Iterative Algorithms

Hua Xiao, Amir H. Banihashemi, Mehdi Karimi

This paper describes a combinatorial approach to estimate the error rate performance of low-density parity-check (LDPC) codes decoded by (quantized) soft-decision iterative decoding algorithms. The method is based on efficient enumeration of input vectors with small distances to a reference vector whose elements are selected to be the most reliable values from the input alphabet. Several techniques, including modified cycle enumeration, and the efficient derivation of problematic inputs for finer quantizers from those of coarser ones are employed to reduce the complexity of the enumeration. The error rate estimate is derived by testing the input vectors of small distances followed by estimating the contribution of larger distance vectors. We demonstrate by a number of examples that the proposed method provides accurate estimates of error rate with computational complexity much lower than that of Monte Carlo simulations, especially at the error floor region.

IEEE Transactions on Communications•Jan 8, 2013•24 citations
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |Ej| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |Ej|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. In this paper, we approximate J and |Ej| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.
The performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms can be accurately estimated if the weight J and the number |EJ| of the smallest error patterns that cannot be corrected by the decoder are known. To obtain J and |EJ|, one would need to perform the direct enumeration of error patterns with weight i les J. The complexity of enumeration increases exponentially with J, essentially as nJ, where n is the code block length. This limits the application of direct enumeration to codes with small n and J. In this letter, we approximate J and |EJ| by enumerating and testing the error patterns that are subsets of short cycles in the code's Tanner graph. This reduces the computational complexity by several orders of magnitude compared to direct enumeration, making it possible to estimate the error rates for almost any practical LDPC code. To obtain the error rate estimates, we propose an algorithm that progressively improves the estimates as larger cycles are enumerated. Through a number of examples, we demonstrate that the proposed method can accurately estimate both the bit error rate (BER) and the frame error rate (FER) of regular and irregular LDPC codes decoded by a variety of hard-decision iterative decoding algorithms.
A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.
A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.
This paper describes a combinatorial approach to estimate the error rate performance of low-density parity-check (LDPC) codes decoded by (quantized) soft-decision iterative decoding algorithms. The method is based on efficient enumeration of input vectors with small distances to a reference vector whose elements are selected to be the most reliable values from the input alphabet. Several techniques, including modified cycle enumeration, are employed to reduce the complexity of the enumeration. The error rate estimate is derived by testing the input vectors of small distances and estimating the contribution of larger distance vectors. We demonstrate by a number of examples that the proposed method provides accurate estimates of error rate with computational complexity much lower than that of Monte Carlo simulations, especially at the error floor region.
Upper and lower bounds are derived on the frame error rate (FER) of low-density parity-check (LDPC) codes decoded by hard-decision iterative algorithms over binary symmetric channels (BSC). The bounds, which are tight for sufficiently small crossover probabilities of the channel, provide a good estimate of FER in this region. The derivation of the bounds is based on the enumeration of low-weight error patterns at the input of the decoder and is much less complex than the conventional Monte Carlo simulation in the crossover probability range of interest. The proposed method can be applied to any LDPC code and for any decoding algorithm
This paper describes a combinatorial approach to estimate the error rate performance of low-density parity-check (LDPC) codes decoded by (quantized) soft-decision iterative decoding algorithms. The method is based on efficient enumeration of input vectors with small distances to a reference vector whose elements are selected to be the most reliable values from the input alphabet. Several techniques, including modified cycle enumeration, and the efficient derivation of problematic inputs for finer quantizers from those of coarser ones are employed to reduce the complexity of the enumeration. The error rate estimate is derived by testing the input vectors of small distances followed by estimating the contribution of larger distance vectors. We demonstrate by a number of examples that the proposed method provides accurate estimates of error rate with computational complexity much lower than that of Monte Carlo simulations, especially at the error floor region.