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

arXiv:1610.06712

A New Simulation Approach to Performance Evaluation of Binary Linear Codes in the Extremely Low Error Rate Region

Xiao Ma, Jia Liu, Shancheng Zhao

Published Oct 21, 2016• 0 citations
arXivHTMLPDF

Abstract

In this paper, the sphere bound (SB) is revisited within a general bounding framework based on nested Gallager regions. The equivalence is revealed between the SB proposed by Herzberg and Poltyrev and the SB proposed by Kasami et al., whereas the latter was rarely cited in the literatures. Interestingly and importantly, the derivation of the SB based on nested Gallager regions suggests us a new simulation approach to performance evaluation of binary linear codes over additive white Gaussian noise (AWGN) channels. In order for the performance evaluation, the proposed approach decouples the geometrical structure of the code from the noise statistics. The former specifies the conditional error probabilities, which are independent of signal-to-noise ratios (SNRs) and can be simulated and estimated efficiently, while the latter determines the probabilities of those conditions, which involve SNRs and can be calculated numerically. Numerical results show that the proposed simulation approach matches well with the traditional simulation approach in the high error rate region but is able to evaluate efficiently the performance in the extremely low error rate region.

DOI
10.48550/arxiv.1610.06712

Related papers

Sphere bound revisited: A new simulation approach to performance evaluation of binary linear codes over AWGN channels

Shancheng Zhao, Jia Liu, Xiao Ma

In this paper, the sphere bound (SB) is revisited within a general bounding framework based on nested Gallager regions. We show that the SB proposed by Herzberg et al. is equivalent to the SB proposed by Kasami et al.. Interestingly, this general framework provides a new way to evaluate the performance of binary linear codes over additive white Gaussian noise (AWGN) channels. This simulation approach relies on only the geometry structure of the code itself. Therefore, simulation results can be used to evaluate not only the performance over AWGN channels but also that over other symmetrical real channels. Numerical results obtained with the new performance evaluation approach are presented.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•4 citations

On Parameterized Gallager's First Bounds for Binary Linear Codes over AWGN Channels

Xiao Ma, Jia Liu, Baoming Bai

In this paper, nested Gallager regions with a single parameter is introduced to exploit Gallager's first bounding technique (GFBT). We present a necessary and sufficient condition on the optimal parameter. We also present a sufficient condition (with a simple geometrical explanation) under which the optimal parameter does not depend on the signal-to-noise ratio (SNR). With this general framework, three existing upper bounds are revisited, including the tangential bound (TB) of Berlekamp, the sphere bound (SB) of Herzberg and Poltyrev, and the tangential-sphere bound (TSB) of Poltyrev. This paper also reveals that the SB of Herzberg and Poltyrev is equivalent to the SB of Kasami et al., which was rarely cited in literature.

arXiv:1202.0592•Feb 3, 2012•0 citations

A New Upper Bound on the ML DecodingError Probability of Linear Binary Block Codes in AWGN Interference

Shahram Yousefi, Amir Keyvan Khandani

Performance evaluation of maximum-likelihood (ML) soft-decision-decoded binary block codes is usually carried out using bounding techniques. Many tight upper bounds on the error probability of binary codes are based on the so-called Gallager's first bounding technique (GFBT). The tangential sphere bound (TSB) of Poltyrev which has been believed for many years to offer the tightest bound developed for binary block codes is an example. Within the framework of the TSB and GFBT, we apply a new method referred to as the "added-hyper-plane" (AHP) technique, to the decomposition of the error probability. This results in a bound developed upon the application of two stages of the GFBT with two different Gallager regions culminating in a tightened upper bound beyond the TSB. The proposed bound is simple and only requires the spectrum of the binary code.

IEEE Transactions on Information Theory•Nov 30, 2004•45 citations

Upper Bound on the Bit Error Probability of Systematic Binary Linear Codes via Their Weight Spectra

Jia Liu, Mingyu Zhang, Chaoyong Wang +3 more

In this paper, upper bound on the probability of maximum a posteriori (MAP) decoding error for systematic binary linear codes over additive white Gaussian noise (AWGN) channels is proposed. The proposed bound on the bit error probability is derived with the framework of Gallager’s first bounding technique (GFBT), where the Gallager region is defined to be an irregular high-dimensional geometry by using a list decoding algorithm. The proposed bound on the bit error probability requires only the knowledge of weight spectra, which is helpful when the input-output weight enumerating function (IOWEF) is not available. Numerical results show that the proposed bound on the bit error probability matches well with the maximum-likelihood (ML) decoding simulation approach especially in the high signal-to-noise ratio (SNR) region, which is better than the recently proposed Ma bound.

Discrete Dynamics in Nature and Society•Jan 29, 2020•0 citations

New performance evaluation methods for block codes over memoryless channels with efficiency analysis

Jinzhe Pan

With the development of communication technology, modern communication networks need to achieve ultra-high reliability to meet practical demands. Forward error correction coding has been widely used in real-world communication systems for providing reliable data transmission over noisy channels. In this thesis, we investigate the efficient performance evaluation methods for block codes over memoryless channels. Performance bounds are powerful tools to provide insights on the error performance of the coded systems. In many practical scenarios where performance bounds are not applicable (e.g., due to the unavailability of the relevant coding parameters under a given decoder), the Monte Carlo simulation is still popular despite its inefficiency, especially in the low error probability regime. As a variance-reduction technique, importance sampling (IS) can significantly reduce the sample size needed for reliable estimation. We firstly examine the problem of efficient performance evaluation of linear block codes over binary symmetric channels (BSCs). Contrary to the conventional wisdom, we prove that for BSCs, all bounds based on Gallager’s first bounding technique, including the famous union bound, are not asymptotically tight for all possible choices of the Gallager region. By proposing the so-called input demodulated-output weight enumerating function (IDWEF) of a code, asymptotically tight maximum-likelihood decoding upper and lower bounds for BSCs are derived. For the cases that coding parameters are absent or suboptimal decoders are applied, we propose an efficient IS estimator by deriving the optimal IS distribution of the Hamming weight of the error vector. In addition, the asymptotic percentage saving of the proposed IS estimator over the state-of-the-art IS estimator is characterized in terms of the sample size. Its accuracy in predicting the efficiency of the proposed IS estimator is verified by extensive computer simulation. We further examine the IS estimator design and efficiency analysis problems for the additive white generalized Gaussian noise (AWGGN) channel. The generalized Gaussian distribution is an effective model to describe real-world systems with impulsive noise. It can be specialized to the Laplace and Gaussian distributions depending on the choices of the decay rates of the heavy tail. By deriving the optimal IS distribution on the one-dimensional space mapped from the observation space, we present a general framework for designing IS estimators for linear block codes over a memoryless continuous channel. We apply the framework to the AWGGN channel and propose a noise-magnitude-domain IS (NM-IS) estimator. As an efficiency measure, the asymptotic IS gain of the proposed estimator is derived in a multiple integral as the signal-to-noise ratio (SNR) tends to infinity. Specifically, we reduce the gains of both Laplace and Gaussian noise cases to a one-dimensional integral. In addition, by limiting the use of the union bound to an L1-norm sphere with an optimized radius, we derive the sphere bound for the additive white Laplace noise channel. Simulation results show the efficiency of the proposed IS estimator in terms of the sample size and verify the accuracy of the prediction of the derived IS gain. Besides, we specialize the proposed framework to further improve the efficiency of the IS simulation based on the side information of the modulation. For the AWGGN channel with binary phase-shift keying (BPSK) modulation, we propose an enhanced NM-IS estimator, which outperforms the NM-IS estimator in efficiency. For the additive white Gaussian noise channel with M-PSK modulation, we propose an angular domain IS estimator and provide its efficiency analysis in terms of the asymptotic IS gain. Furthermore, in the performance evaluation of communication systems, it is often seen that researchers are more interested in the required SNR at a target error probability Pe than the other way around. The conventional solution to this Pe-targeted SNR estimation problem involves interpolation of simulated error probabilities at multiple handpicked SNRs for estimating the required SNR at the target error probability. We propose a Pe-targeted iterative IS estimator that solves the problem algorithmically. The proposed method can achieve the same efficiency (in terms of sample size) as estimating the error probability at the required SNR and allow the confidence interval of the SNR estimate to be obtained.

•Jan 1, 2022•0 citations

Gallager bounds for linear codes in binary-input output-symmetric memoryless channels

Alfonso García Martínez, Albert Guillén i Fàbregas, Giuseppe Caire

This paper presents a general methodology to extend Gallager bounds on the maximum-likelihood decoding error probability to arbitrary binary-input output-symmetric memoryless channels. Based on the log-likelihood ratios, a new space is constructed in which the signals naturally lie on a sphere, and for which geometric analysis is straightforward. In particular, we focus on Poltyrev's tangential-sphere bound, and we illustrate its connections with the Engdahl-Zigangirov bound. Approximations to these bounds are shown to be very tight.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•0 citations
In this paper, the sphere bound (SB) is revisited within a general bounding framework based on nested Gallager regions. The equivalence is revealed between the SB proposed by Herzberg and Poltyrev and the SB proposed by Kasami et al., whereas the latter was rarely cited in the literatures. Interestingly and importantly, the derivation of the SB based on nested Gallager regions suggests us a new simulation approach to performance evaluation of binary linear codes over additive white Gaussian noise (AWGN) channels. In order for the performance evaluation, the proposed approach decouples the geometrical structure of the code from the noise statistics. The former specifies the conditional error probabilities, which are independent of signal-to-noise ratios (SNRs) and can be simulated and estimated efficiently, while the latter determines the probabilities of those conditions, which involve SNRs and can be calculated numerically. Numerical results show that the proposed simulation approach matches well with the traditional simulation approach in the high error rate region but is able to evaluate efficiently the performance in the extremely low error rate region.
In this paper, the sphere bound (SB) is revisited within a general bounding framework based on nested Gallager regions. We show that the SB proposed by Herzberg et al. is equivalent to the SB proposed by Kasami et al.. Interestingly, this general framework provides a new way to evaluate the performance of binary linear codes over additive white Gaussian noise (AWGN) channels. This simulation approach relies on only the geometry structure of the code itself. Therefore, simulation results can be used to evaluate not only the performance over AWGN channels but also that over other symmetrical real channels. Numerical results obtained with the new performance evaluation approach are presented.
In this paper, nested Gallager regions with a single parameter is introduced to exploit Gallager's first bounding technique (GFBT). We present a necessary and sufficient condition on the optimal parameter. We also present a sufficient condition (with a simple geometrical explanation) under which the optimal parameter does not depend on the signal-to-noise ratio (SNR). With this general framework, three existing upper bounds are revisited, including the tangential bound (TB) of Berlekamp, the sphere bound (SB) of Herzberg and Poltyrev, and the tangential-sphere bound (TSB) of Poltyrev. This paper also reveals that the SB of Herzberg and Poltyrev is equivalent to the SB of Kasami et al., which was rarely cited in literature.
Performance evaluation of maximum-likelihood (ML) soft-decision-decoded binary block codes is usually carried out using bounding techniques. Many tight upper bounds on the error probability of binary codes are based on the so-called Gallager's first bounding technique (GFBT). The tangential sphere bound (TSB) of Poltyrev which has been believed for many years to offer the tightest bound developed for binary block codes is an example. Within the framework of the TSB and GFBT, we apply a new method referred to as the "added-hyper-plane" (AHP) technique, to the decomposition of the error probability. This results in a bound developed upon the application of two stages of the GFBT with two different Gallager regions culminating in a tightened upper bound beyond the TSB. The proposed bound is simple and only requires the spectrum of the binary code.
In this paper, upper bound on the probability of maximum a posteriori (MAP) decoding error for systematic binary linear codes over additive white Gaussian noise (AWGN) channels is proposed. The proposed bound on the bit error probability is derived with the framework of Gallager’s first bounding technique (GFBT), where the Gallager region is defined to be an irregular high-dimensional geometry by using a list decoding algorithm. The proposed bound on the bit error probability requires only the knowledge of weight spectra, which is helpful when the input-output weight enumerating function (IOWEF) is not available. Numerical results show that the proposed bound on the bit error probability matches well with the maximum-likelihood (ML) decoding simulation approach especially in the high signal-to-noise ratio (SNR) region, which is better than the recently proposed Ma bound.
With the development of communication technology, modern communication networks need to achieve ultra-high reliability to meet practical demands. Forward error correction coding has been widely used in real-world communication systems for providing reliable data transmission over noisy channels. In this thesis, we investigate the efficient performance evaluation methods for block codes over memoryless channels. Performance bounds are powerful tools to provide insights on the error performance of the coded systems. In many practical scenarios where performance bounds are not applicable (e.g., due to the unavailability of the relevant coding parameters under a given decoder), the Monte Carlo simulation is still popular despite its inefficiency, especially in the low error probability regime. As a variance-reduction technique, importance sampling (IS) can significantly reduce the sample size needed for reliable estimation. We firstly examine the problem of efficient performance evaluation of linear block codes over binary symmetric channels (BSCs). Contrary to the conventional wisdom, we prove that for BSCs, all bounds based on Gallager’s first bounding technique, including the famous union bound, are not asymptotically tight for all possible choices of the Gallager region. By proposing the so-called input demodulated-output weight enumerating function (IDWEF) of a code, asymptotically tight maximum-likelihood decoding upper and lower bounds for BSCs are derived. For the cases that coding parameters are absent or suboptimal decoders are applied, we propose an efficient IS estimator by deriving the optimal IS distribution of the Hamming weight of the error vector. In addition, the asymptotic percentage saving of the proposed IS estimator over the state-of-the-art IS estimator is characterized in terms of the sample size. Its accuracy in predicting the efficiency of the proposed IS estimator is verified by extensive computer simulation. We further examine the IS estimator design and efficiency analysis problems for the additive white generalized Gaussian noise (AWGGN) channel. The generalized Gaussian distribution is an effective model to describe real-world systems with impulsive noise. It can be specialized to the Laplace and Gaussian distributions depending on the choices of the decay rates of the heavy tail. By deriving the optimal IS distribution on the one-dimensional space mapped from the observation space, we present a general framework for designing IS estimators for linear block codes over a memoryless continuous channel. We apply the framework to the AWGGN channel and propose a noise-magnitude-domain IS (NM-IS) estimator. As an efficiency measure, the asymptotic IS gain of the proposed estimator is derived in a multiple integral as the signal-to-noise ratio (SNR) tends to infinity. Specifically, we reduce the gains of both Laplace and Gaussian noise cases to a one-dimensional integral. In addition, by limiting the use of the union bound to an L1-norm sphere with an optimized radius, we derive the sphere bound for the additive white Laplace noise channel. Simulation results show the efficiency of the proposed IS estimator in terms of the sample size and verify the accuracy of the prediction of the derived IS gain. Besides, we specialize the proposed framework to further improve the efficiency of the IS simulation based on the side information of the modulation. For the AWGGN channel with binary phase-shift keying (BPSK) modulation, we propose an enhanced NM-IS estimator, which outperforms the NM-IS estimator in efficiency. For the additive white Gaussian noise channel with M-PSK modulation, we propose an angular domain IS estimator and provide its efficiency analysis in terms of the asymptotic IS gain. Furthermore, in the performance evaluation of communication systems, it is often seen that researchers are more interested in the required SNR at a target error probability Pe than the other way around. The conventional solution to this Pe-targeted SNR estimation problem involves interpolation of simulated error probabilities at multiple handpicked SNRs for estimating the required SNR at the target error probability. We propose a Pe-targeted iterative IS estimator that solves the problem algorithmically. The proposed method can achieve the same efficiency (in terms of sample size) as estimating the error probability at the required SNR and allow the confidence interval of the SNR estimate to be obtained.
This paper presents a general methodology to extend Gallager bounds on the maximum-likelihood decoding error probability to arbitrary binary-input output-symmetric memoryless channels. Based on the log-likelihood ratios, a new space is constructed in which the signals naturally lie on a sphere, and for which geometric analysis is straightforward. In particular, we focus on Poltyrev's tangential-sphere bound, and we illustrate its connections with the Engdahl-Zigangirov bound. Approximations to these bounds are shown to be very tight.