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 Transactions on Information Theory

An Algorithm for Calculating the Exact Bit Error Probability of a Binary Linear Code Over the Binary Symmetric Channel

Tadashi Wadayama

Published Feb 1, 2004• 4 citations
Publisher

Abstract

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.

DOI
10.1109/tit.2003.822617

Related papers

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

Analysis of Lower Bound for the Error Probability of Linear Block Codes over the BSC Channel

Xu Ba

A lower bound on the error rate of linear binary block codes(under maximum likelihood decoding) over BSC channels is proposed.According to the principle of the maximum likelihood(ML) decoding algorithm,the decoding error probability is firstly converted into the joint probability of the error events,and the judge rule of the redundant error events is deduced based on the optimization rule of the improved Dawson-Sankoff bound.Moreover,the calculation expression about lower bound of the error probability solely depends on the Hamming weight enumerator function of the code and the crossover probability of the channel.The simulation results applying to various LDPC codes show that the new lower bound outperforms those generic lower bounds and the sphere packing bound.Its computational complexity is also lower.

Journal of National University of Defense Technology•Jan 1, 2011•0 citations

A lower bound on the probability of decoding error over a BSC channel

Osnat Keren, Simon N. Litsyn

For a code C of length n and size |C, we estimate the error probability of the maximum likelihood decoding. In this paper we address this problem for the binary symmetric channel (BSC) defined by its transition probability p. We discuss the case when we know the distance distribution of the code. We also assume that the code is regular in the sense that the distribution of the distances from a codeword to other codewords does not depend on the choice of the initial codeword.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 11, 2002•7 citations

Estimates of the bit error probabilities for linear block codes and symmetric binary-input memoryless channels

Vladimir B. Balakirsky

A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.

IEEE Information Theory Workshop (ITW)•Aug 27, 2003•1 citation

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

Using Linear Programming to Decode Binary Linear Codes

J. Feldman, Martin J. Wainwright, David Ron Karger

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.

IEEE Transactions on Information Theory•Feb 28, 2005•547 citations
An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.
A lower bound on the error rate of linear binary block codes(under maximum likelihood decoding) over BSC channels is proposed.According to the principle of the maximum likelihood(ML) decoding algorithm,the decoding error probability is firstly converted into the joint probability of the error events,and the judge rule of the redundant error events is deduced based on the optimization rule of the improved Dawson-Sankoff bound.Moreover,the calculation expression about lower bound of the error probability solely depends on the Hamming weight enumerator function of the code and the crossover probability of the channel.The simulation results applying to various LDPC codes show that the new lower bound outperforms those generic lower bounds and the sphere packing bound.Its computational complexity is also lower.
A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.
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.
A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.