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

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

Jinzhe Pan

Published Jan 1, 2022• 0 citations
Publisher

Abstract

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.

DOI
10.14711/thesis-991013106352003412

Related papers

Lower Bounds on the Error Probability of Block Codes Based on Improvements on de Caen's Inequality

A. Cohen, Neri Merhav

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.

IEEE Transactions on Information Theory•Feb 1, 2004•40 citations

A New Importance Sampling Algorithm for Fast Simulation of Linear Block Codes over BSCs

Jinzhe Pan, Wai Ho Mow

In this paper, we propose an Importance Sampling (IS) scheme for fast simulation of linear block codes over binary symmetric channels (BSCs). By re-formulating the IS problem into the one-dimensional Hamming weight space, we propose a novel IS estimator and derive the optimal IS distribution which will minimize the variance of the estimator. Consequently, a corresponding iterative algorithm is proposed. The effectiveness of the proposed IS algorithm compared to the state-of-the-art IS algorithm is demonstrated in the word error rate simulation of both LDPC and Polar codes.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•4 citations

Sub-optimal importance sampling for fast simulation of linear block codes over BSC channels

Gianmarco Romano, Antonio Drago, Domenico Ciuonzo

Estimation of very low word-error probability of hard-decoded linear block codes can be performed through Monte-Carlo simulation. The computational complexity of the standard method however increases as the probability of error to be estimated decreases. In this paper we propose a general algorithm for fast estimation of probability of error of linear block codes on BSC channels based on the importance sampling and the cross-entropy method for rare-events that can be employed for any hard-decision decoder. When optimal decoding is used the algorithm reduces to a single simulation run that can estimate, with a given accuracy, performances for a whole range of sufficiently high signal-to-noise ratios.

International Symposium on Wireless Communication Systems•Nov 1, 2011•6 citations

On Approximation, Bounding & Exact Calculation of Block Error Probability for Random Codes

Ralf R. Müller

This paper presents a method to calculate the exact block error probability of random codes under maximum-likelihood decoding. The proposed method is applicable to a variety of channels. Particular focus is on both spherical and Gaussian random codes in additive white Gaussian noise as well as binary random codes on the binary symmetric channel. While for spherical random codes Shannon, in 1959, argued with solid angles in $N$-dimensional space, we project the problem into two dimensions and apply standard trigonometry. This simplifies the derivation and also allows for the analysis of Gaussian random codes which turn out to perform better for short blocklengths and high rates. For spherical random codes, we show how to efficiently evaluate the error probability with high precision. The difference to Shannon's sphere packing bound turns out to be small, as the Voronoi regions harden doubly-exponential in the blocklength. We show that, whenever the code contains more than three codewords, the sphere packing bound can be tightened by a new bound, that requires exactly the same effort to compute. Furthermore, we propose a very tight approximation to simplify computation of both exact error probability and the two bounds. For the binary symmetric channel, we derive an upper and a lower bound on the block error probability. The two only differ from the exact error probability, as for discrete alphabets there is a small, but nonzero probability to guess for the correct codeword, if several codewords have equal distance to the received word.

arXiv:2003.06807•Mar 15, 2020•2 citations

On the computation of the probability of undetected error for linear block codes on the Gilbert channel

B. Wong

An important measure of the performance of error detecting codes is the probability of undetected error. Extensive study on the subject has yielded results which allow for the computation of the probability of undetected error for many codes on the binary symmetric channel (BSC). However, little is known about code performance in more complicated channel models. The Gilbert channel is a two-state, three-parameter model with memory which simulates the effects of burst noise. In this thesis, we investigate methods to compute the probability of undetected error of binary linear block codes on this channel. We examine an approach to approximate code performance based on the P(m,n) distribution which is the probability of m errors in a block of n bits and the weight distribution of the code. For the Gilbert channel, P(m,n) can in principle be calculated from the channel parameters. In practice however, existing methodologies suffer from rather excessive computational requirements, particularly when n is larger than one thousand or so. We have developed an efficient method to calculate P(m,n) for reasonable channel parameters. This allows the probability of undetected error for many codes to be readily estimated. For certain channel and code parameters, the approximation method described above may not be sufficiently accurate. Exact analytical results are difficult to obtain, however; because unlike the BSC, the probability of a particular error pattern on the Gilbert channel depends not just on the number of 1's in the pattern. Nevertheless, by appropriately exploiting certain symmetries present on the Gilbert channel, we can acquire some useful results. We have derived the probability of undetected error for the single parity check code. We have also obtained a formula for summing over a cyclic class of vectors and shown that reciprocal generator polynomials generate cyclic codes which have the same probability of undetected error on the Gilbert channel. The Monte Carlo simulation technique is often used when exact analysis is difficult. In a simulation study of CRC codes, we are able to observe several interesting qualitative results with just a reasonable amount of computational effort. We find that as on the BSC, on the Gilbert channel the probability of undetected error does not always increase with worsening channel conditions. Also, the CRC-CCITT code appears to maintain its superiority in terms of error detection performance over the CRC-ANSI code on the Gilbert channel, and perhaps most significantly, for some ranges of channel parameters, the probability of undetected error estimated using BSC results with the effective bit error rate can be quite inaccurate.

•Jan 1, 2010•2 citations

Minimum-Variance Importance Sampling Estimator for Fast Simulation of Linear Block Codes over Binary Erasure Channels

Jinzhe Pan, Wai Ho Mow

In this paper, the problem of efficiently evaluating the error performance of linear block codes over binary erasure channels (BECs) is considered. We propose a novel importance sampling (IS) estimator by deriving the optimal IS distribution of the erasure pattern size. Consequently, a corresponding iterative algorithm for fast simulation purpose is proposed. The effectiveness of the proposed IS algorithm compared to Monte Carlo simulation is demonstrated in estimating the block erasure rate of low-density parity-check codes, and IS gains of almost ten orders of magnitude is achieved.

World Conference on Computing and Communication Technologies (WCCCT)•Jan 1, 2021•1 citation
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.
New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.
In this paper, we propose an Importance Sampling (IS) scheme for fast simulation of linear block codes over binary symmetric channels (BSCs). By re-formulating the IS problem into the one-dimensional Hamming weight space, we propose a novel IS estimator and derive the optimal IS distribution which will minimize the variance of the estimator. Consequently, a corresponding iterative algorithm is proposed. The effectiveness of the proposed IS algorithm compared to the state-of-the-art IS algorithm is demonstrated in the word error rate simulation of both LDPC and Polar codes.
Estimation of very low word-error probability of hard-decoded linear block codes can be performed through Monte-Carlo simulation. The computational complexity of the standard method however increases as the probability of error to be estimated decreases. In this paper we propose a general algorithm for fast estimation of probability of error of linear block codes on BSC channels based on the importance sampling and the cross-entropy method for rare-events that can be employed for any hard-decision decoder. When optimal decoding is used the algorithm reduces to a single simulation run that can estimate, with a given accuracy, performances for a whole range of sufficiently high signal-to-noise ratios.
This paper presents a method to calculate the exact block error probability of random codes under maximum-likelihood decoding. The proposed method is applicable to a variety of channels. Particular focus is on both spherical and Gaussian random codes in additive white Gaussian noise as well as binary random codes on the binary symmetric channel. While for spherical random codes Shannon, in 1959, argued with solid angles in NNN-dimensional space, we project the problem into two dimensions and apply standard trigonometry. This simplifies the derivation and also allows for the analysis of Gaussian random codes which turn out to perform better for short blocklengths and high rates. For spherical random codes, we show how to efficiently evaluate the error probability with high precision. The difference to Shannon's sphere packing bound turns out to be small, as the Voronoi regions harden doubly-exponential in the blocklength. We show that, whenever the code contains more than three codewords, the sphere packing bound can be tightened by a new bound, that requires exactly the same effort to compute. Furthermore, we propose a very tight approximation to simplify computation of both exact error probability and the two bounds. For the binary symmetric channel, we derive an upper and a lower bound on the block error probability. The two only differ from the exact error probability, as for discrete alphabets there is a small, but nonzero probability to guess for the correct codeword, if several codewords have equal distance to the received word.
An important measure of the performance of error detecting codes is the probability of undetected error. Extensive study on the subject has yielded results which allow for the computation of the probability of undetected error for many codes on the binary symmetric channel (BSC). However, little is known about code performance in more complicated channel models. The Gilbert channel is a two-state, three-parameter model with memory which simulates the effects of burst noise. In this thesis, we investigate methods to compute the probability of undetected error of binary linear block codes on this channel. We examine an approach to approximate code performance based on the P(m,n) distribution which is the probability of m errors in a block of n bits and the weight distribution of the code. For the Gilbert channel, P(m,n) can in principle be calculated from the channel parameters. In practice however, existing methodologies suffer from rather excessive computational requirements, particularly when n is larger than one thousand or so. We have developed an efficient method to calculate P(m,n) for reasonable channel parameters. This allows the probability of undetected error for many codes to be readily estimated. For certain channel and code parameters, the approximation method described above may not be sufficiently accurate. Exact analytical results are difficult to obtain, however; because unlike the BSC, the probability of a particular error pattern on the Gilbert channel depends not just on the number of 1's in the pattern. Nevertheless, by appropriately exploiting certain symmetries present on the Gilbert channel, we can acquire some useful results. We have derived the probability of undetected error for the single parity check code. We have also obtained a formula for summing over a cyclic class of vectors and shown that reciprocal generator polynomials generate cyclic codes which have the same probability of undetected error on the Gilbert channel. The Monte Carlo simulation technique is often used when exact analysis is difficult. In a simulation study of CRC codes, we are able to observe several interesting qualitative results with just a reasonable amount of computational effort. We find that as on the BSC, on the Gilbert channel the probability of undetected error does not always increase with worsening channel conditions. Also, the CRC-CCITT code appears to maintain its superiority in terms of error detection performance over the CRC-ANSI code on the Gilbert channel, and perhaps most significantly, for some ranges of channel parameters, the probability of undetected error estimated using BSC results with the effective bit error rate can be quite inaccurate.
In this paper, the problem of efficiently evaluating the error performance of linear block codes over binary erasure channels (BECs) is considered. We propose a novel importance sampling (IS) estimator by deriving the optimal IS distribution of the erasure pattern size. Consequently, a corresponding iterative algorithm for fast simulation purpose is proposed. The effectiveness of the proposed IS algorithm compared to Monte Carlo simulation is demonstrated in estimating the block erasure rate of low-density parity-check codes, and IS gains of almost ten orders of magnitude is achieved.