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

International Conference on Communications

Bit error rate analysis on iterative two-stage decoding of two dimensional codes by importance sampling

Toshiyuki Yamane, Y. Katayama

Published Mar 30, 2004• 7 citations
Publisher

Abstract

We present a bit error rate analysis for iterative two-stage hard decision decoding of product codes and proposed a concatenated codes suitable for optical communication. Our method is based on an importance sampling technique characterized by recursive calculation of cumulative binomial probabilities and direct biasing of error patterns. We can accelerate the Monte Carlo simulations by several orders of magnitude such as 10/sup 8/ and estimate the coding gains at the BERs as low as 10/sup -15/ required in optical communications. We apply the method for comparative BER analysis of product codes and proposed concatenated codes and show that product codes of small minimum distance have error floors at low BERs while the proposed concatenated codes of large minimum distance do not.

DOI
10.1109/icc.2003.1204002

Related papers

Iterative Decoding of LDPC-Based Product Codes and FPGA-Based Performance Evaluation

Weigang Chen, Wenting Zhao, Hui Li +3 more

Low-density parity-check (LDPC) codes have the potential for applications in future high throughput optical communications due to their significant error correction capability and the parallel decoding. However, they are not able to satisfy the very low bit error rate (BER) requirement due to the error floor phenomenon. In this paper, we propose a low-complexity iterative decoding scheme for product codes consisting of very high rate outer codes and LDPC codes. The outer codes aim at eliminating the residual error floor of LDPC codes with quite low implementation costs. Furthermore, considering the long simulation time of computer simulation for evaluating very low BER, the hardware platform is built to accelerate the evaluation of the proposed iterative decoding methods. Simultaneously, the fixed-point effects of the decoding algorithms are also be evaluated. The experimental results show that the iterative decoding of the product codes can achieve a quite low bit error rate. The evaluation using field programmable gate array (FPGA) also proves that product codes with LDPC codes and high-rate algebraic codes can achieve a good trade-off between complexity and throughput.

Electronics•Jan 8, 2020•6 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

Importance sampling for LDPC codes and turbo-coded CDMA

Bo Xia

Low-density parity-check (LDPC) codes have shown capacity-approaching performance with soft iterative decoding algorithms. Simulating LDPC codes at very low error rates normally takes an unacceptably long time. We consider importance sampling (IS) schemes for the error rate estimation of LDPC codes, with the goal of dramatically reducing the necessary simulation time. In IS simulations, the sample distribution is biased to emphasize the occurrence of error events and efficiency can be achieved with properly biased sample distributions. For LDPC codes, we propose an IS scheme that overcomes a difficulty in traditional IS designs that require codebook information. This scheme is capable of estimating both codeword and bit error rates. As an example, IS gains on the order of 105 are observed at a bit error rate (BER) of 10-15 for a (96, 48) code. We also present an importance sampling scheme for the decoding of loop-free multiple-layer trees. This scheme is asymptotically efficient in that, for an arbitrary tree and a given estimation precision, the required number of simulations is inversely proportional to the noise standard deviation. The motivation of this study is to shed light on an asymptotically efficient IS design for LDPC code simulations. For an example depth-3 regular tree, we show that only 2400 simulation runs are needed to achieve a 10% estimation precision at a BER of 10-75. Similar promising results are also shown for a length-9 rate-1/3 regular code after being converted to a decoding tree. Finally, we consider a convolutionally coded CDMA system with iterative multiuser detection and decoding. In contrast to previous work in this area, a differential encoder is inserted to effect an interleaver gain. We view the CDMA channel as a periodically time-varying ISI channel. The receiver jointly decodes the differential encoders and the CDMA channel with a combined trellis, and shares soft output information with the convolutional decoders in an iterative (turbo) fashion. Dramatic gains over conventional convolutionally coded systems are demonstrated via simulation. We also show that there exists an optimal code rate under a bandwidth constraint. The performance and optimal code rates are also demonstrated via density evolution analysis.

•Jan 1, 2004•0 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

Performance Analysis of Iteratively Decoded 3- Dimensional Product Codes

Thomas Mittelholzer

The bit-error-rate (BER) performance of 3-dimensional (3D) product codes under iterative bounded-distance decoding of the component codes is considered and a framework for analyzing the BER-performance is presented. The performance analysis of iterative decoding is based on a graphical model of the underlying 3D product code, which is a tripartite 3-uniform hypergraph. The BER performance for 3D product codes shows a threshold behavior. The thresholds can be approximated by an exit-chart-like technique from the parameters of the component codes. In the case of a symmetric product code, for which all three component codes are based on the same lineart-error correcting code, asymptotically for large code lengths, the BER-threshold is determined by the threshold for the appearance of ak-core withk=t+ 1 in the graphical model.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•0 citations

Evaluation of the Low Frame Error Rate Performance of LDPC Codes Using Importance Sampling

Lara Dolecek, Zhengya Zhang, Martin J. Wainwright +2 more

We present an importance sampling method for the evaluation of the low frame error rate (FER) performance of LDPC codes under iterative decoding. It relies on a combinatorial characterization of absorbing sets, which are the dominant cause of decoder failure in the low FER region. The biased density in the importance sampling scheme is a mean-shifted version of the original Gaussian density, which is suitably centered between a codeword and a dominant absorbing set. This choice of biased density yields an unbiased estimator for the FER with a variance lower by several orders of magnitude than the standard Monte Carlo estimator. Using this importance sampling scheme in software, we obtain good agreement with the experimental results obtained from a fast hardware emulator of the decoder.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•48 citations
We present a bit error rate analysis for iterative two-stage hard decision decoding of product codes and proposed a concatenated codes suitable for optical communication. Our method is based on an importance sampling technique characterized by recursive calculation of cumulative binomial probabilities and direct biasing of error patterns. We can accelerate the Monte Carlo simulations by several orders of magnitude such as 10/sup 8/ and estimate the coding gains at the BERs as low as 10/sup -15/ required in optical communications. We apply the method for comparative BER analysis of product codes and proposed concatenated codes and show that product codes of small minimum distance have error floors at low BERs while the proposed concatenated codes of large minimum distance do not.
Low-density parity-check (LDPC) codes have the potential for applications in future high throughput optical communications due to their significant error correction capability and the parallel decoding. However, they are not able to satisfy the very low bit error rate (BER) requirement due to the error floor phenomenon. In this paper, we propose a low-complexity iterative decoding scheme for product codes consisting of very high rate outer codes and LDPC codes. The outer codes aim at eliminating the residual error floor of LDPC codes with quite low implementation costs. Furthermore, considering the long simulation time of computer simulation for evaluating very low BER, the hardware platform is built to accelerate the evaluation of the proposed iterative decoding methods. Simultaneously, the fixed-point effects of the decoding algorithms are also be evaluated. The experimental results show that the iterative decoding of the product codes can achieve a quite low bit error rate. The evaluation using field programmable gate array (FPGA) also proves that product codes with LDPC codes and high-rate algebraic codes can achieve a good trade-off between complexity and throughput.
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.
Low-density parity-check (LDPC) codes have shown capacity-approaching performance with soft iterative decoding algorithms. Simulating LDPC codes at very low error rates normally takes an unacceptably long time. We consider importance sampling (IS) schemes for the error rate estimation of LDPC codes, with the goal of dramatically reducing the necessary simulation time. In IS simulations, the sample distribution is biased to emphasize the occurrence of error events and efficiency can be achieved with properly biased sample distributions. For LDPC codes, we propose an IS scheme that overcomes a difficulty in traditional IS designs that require codebook information. This scheme is capable of estimating both codeword and bit error rates. As an example, IS gains on the order of 105 are observed at a bit error rate (BER) of 10-15 for a (96, 48) code. We also present an importance sampling scheme for the decoding of loop-free multiple-layer trees. This scheme is asymptotically efficient in that, for an arbitrary tree and a given estimation precision, the required number of simulations is inversely proportional to the noise standard deviation. The motivation of this study is to shed light on an asymptotically efficient IS design for LDPC code simulations. For an example depth-3 regular tree, we show that only 2400 simulation runs are needed to achieve a 10% estimation precision at a BER of 10-75. Similar promising results are also shown for a length-9 rate-1/3 regular code after being converted to a decoding tree. Finally, we consider a convolutionally coded CDMA system with iterative multiuser detection and decoding. In contrast to previous work in this area, a differential encoder is inserted to effect an interleaver gain. We view the CDMA channel as a periodically time-varying ISI channel. The receiver jointly decodes the differential encoders and the CDMA channel with a combined trellis, and shares soft output information with the convolutional decoders in an iterative (turbo) fashion. Dramatic gains over conventional convolutionally coded systems are demonstrated via simulation. We also show that there exists an optimal code rate under a bandwidth constraint. The performance and optimal code rates are also demonstrated via density evolution analysis.
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.
The bit-error-rate (BER) performance of 3-dimensional (3D) product codes under iterative bounded-distance decoding of the component codes is considered and a framework for analyzing the BER-performance is presented. The performance analysis of iterative decoding is based on a graphical model of the underlying 3D product code, which is a tripartite 3-uniform hypergraph. The BER performance for 3D product codes shows a threshold behavior. The thresholds can be approximated by an exit-chart-like technique from the parameters of the component codes. In the case of a symmetric product code, for which all three component codes are based on the same lineart-error correcting code, asymptotically for large code lengths, the BER-threshold is determined by the threshold for the appearance of ak-core withk=t+ 1 in the graphical model.
We present an importance sampling method for the evaluation of the low frame error rate (FER) performance of LDPC codes under iterative decoding. It relies on a combinatorial characterization of absorbing sets, which are the dominant cause of decoder failure in the low FER region. The biased density in the importance sampling scheme is a mean-shifted version of the original Gaussian density, which is suitably centered between a codeword and a dominant absorbing set. This choice of biased density yields an unbiased estimator for the FER with a variance lower by several orders of magnitude than the standard Monte Carlo estimator. Using this importance sampling scheme in software, we obtain good agreement with the experimental results obtained from a fast hardware emulator of the decoder.