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

Discrete Dynamics in Nature and Society

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

Jia Liu, Mingyu Zhang, Chaoyong Wang, Rongjun Chen, Xiaofeng An, Yufei Wang

Published Jan 29, 2020• 0 citations
Publisher

Abstract

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.

DOI
10.1155/2020/1469090

Related papers

Performance analysis of systematic linear codes over AWGN channels

Jia Liu

In this paper, amended truncated union bounds on the bit error probability of systematic linear codes over additive white Gaussian noise (AWGN) channels are proposed. The proposed bounds are based on Gallager's first bounding technique (GFBT), where the “good” region is defined by a suboptimal list decoding algorithm. The proposed bounds require only the knowledge of partial input output weight enumerating function (IOWEF) with truncated information weight, which can also be adapted to the codes when the IOWEF is not available and difficult to calculate but the weight spectrum is known. The proposed amended truncated union bounds improve the conventional union bounds and the recently proposed Ma bounds but have a similar complexity since they involve only the Q-function.

IEEE International Conference on RFID Technology and Applications (RFID-TA)•Sep 1, 2016•2 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

Improvement of Gallager Upper Bound and its Variations for Discrete Channels

Kostis Xenoulis, N. Kalouptsidis

A new tight upper bound on the maximum-likelihood (ML) word and bit-error decoding probabilities for specific codes over discrete channels is presented. It constitutes an enhanced version of the Gallager upper bound and its variations resulting from the Duman-Salehi second bounding technique. An efficient technique is developed that, in the case of symmetric channels, overcomes the difficulties associated with the direct computation of the proposed bound. Surprisingly, apart from the distance and input-output weight enumerating functions (IOWEFs), the bound depends also on the coset weight distribution of the code.

IEEE Transactions on Information Theory•Aug 24, 2009•1 citation

Bounds on Error-Correction Coding Performance

Martin Tomlinson, Cen Jung Tjhai, Marcel Ambroze +2 more

The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Signals and communication technology•Jan 1, 2017•2 citations

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

Xiao Ma, Jia Liu, Shancheng Zhao

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.

arXiv:1610.06712•Oct 21, 2016•0 citations

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

T. Wadayama

An efficient algorithm for calculating the i-th bit error probability of a binary linear code over the binary symmetric channel (BSC) are presented. It is proved that the exact i-th bit error probability of maximum likelihood (ML) decoding, bounded distance decoding, symbolwise maximum a posteriori probability (MAP) decoding and symbolwise MAP decoding with erasure can be obtained with time complexity O(n2/sup n-k/), where n, k denote length and dimension of the target code.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•0 citations
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.
In this paper, amended truncated union bounds on the bit error probability of systematic linear codes over additive white Gaussian noise (AWGN) channels are proposed. The proposed bounds are based on Gallager's first bounding technique (GFBT), where the “good” region is defined by a suboptimal list decoding algorithm. The proposed bounds require only the knowledge of partial input output weight enumerating function (IOWEF) with truncated information weight, which can also be adapted to the codes when the IOWEF is not available and difficult to calculate but the weight spectrum is known. The proposed amended truncated union bounds improve the conventional union bounds and the recently proposed Ma bounds but have a similar complexity since they involve only the Q-function.
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.
A new tight upper bound on the maximum-likelihood (ML) word and bit-error decoding probabilities for specific codes over discrete channels is presented. It constitutes an enhanced version of the Gallager upper bound and its variations resulting from the Duman-Salehi second bounding technique. An efficient technique is developed that, in the case of symmetric channels, overcomes the difficulties associated with the direct computation of the proposed bound. Surprisingly, apart from the distance and input-output weight enumerating functions (IOWEFs), the bound depends also on the coset weight distribution of the code.
The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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.