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 International Symposium on Information Theory (ISIT)

The Error Probability of Generalized Perfect Codes

Gonzalo Vazquez-Vilar, Albert Guillén i Fàbregas, Sergio Verdú

Published Jun 1, 2018• 0 citations
Publisher

Abstract

We introduce a definition of perfect and quasi-perfect codes for symmetric channels parametrized by an auxiliary output distribution. This new definition generalizes previous definitions and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to attain the meta-converse lower bound.

DOI
10.1109/isit.2018.8437752

Related papers

Generalized Perfect Codes for Symmetric Classical-Quantum Channels

Andreu Blasco Coll, Gonzalo Vazquez-Vilar, J.R. Fonollosa

We define a new family of codes for symmetric classical-quantum channels and establish their optimality. To this end, we extend the classical notion of generalized perfect and quasi-perfect codes to channels defined over some finite dimensional complex Hilbert output space. The resulting optimality conditions depend on the channel considered and on an auxiliary state defined on the output space of the channel. For certain$N$-qubit classical-quantum channels, we show that codes based on a generalization of Bell states are quasi-perfect and, therefore, they feature the smallest error probability among all codes of the same blocklength and cardinality.

arXiv:2007.07958•IEEE Transactions on Information Theory•Apr 28, 2022•4 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

New upper bounds on error exponents

Simon N. Litsyn

We derive new upper bounds on the error exponents for the maximum-likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the best earlier known bounds by Shannon-Gallager-Berlekamp (1967) and McEliece-Omura (1977). For the probability of undetected error the new bounds are better than the bounds by Levenshtein (1978, 1989) and the bound by Abdel-Ghaffar (see ibid., vol.43, p.1489-502, 1997). Moreover, we further extend the range of rates where the undetected error exponent is known to be exact. The new bounds are based on an analysis of possible distance distributions of the codes along with some inequalities relating the distance distributions to the error probabilities.

IEEE Transactions on Information Theory•Mar 1, 1999•65 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

Good error-detection codes satisfying the expurgated bound

Takeshi Hashimoto

A q-ary (n, k) linear code is said to be proper if, as an error-detection code, the probability of undetectable error P/sub ud/ satisfies P/sub ud//spl les/q/sup -(n-k)/ for completely symmetric channels. We show that a proper code, as an error-correction code, satisfies the expurgated bound on the decoding error probability for a class of channels with the associated Bhattacharyya distance being completely symmetric. Known results on the undetectable error probability then immediately imply that the expurgated exponent is satisfied exactly by, for example, all the binary perfect codes, binary first-order Reed-Muller codes, binary (extended) Hamming code, binary 2-error correcting primitive BCH code, and all the maximum distance separable (MDS) codes, and asymptotically by some class of the binary t-error-correcting primitive BCH codes.>

IEEE Transactions on Information Theory•Jan 1, 1995•5 citations

New lower bounds on the error probability of a given block code

A. Cohen, Neri Merhav

A novel technique for deriving lower bounds on the error probability when communicating one of M signals over a communication channel is proposed. At the basis of the technique stands an improvement on a recent lower bound on the probability of a union of events by de Caen (1997). The new bound includes a function which can be optimized in order to achieve the tightest results. By applying this bound to the problem of lower bounding the error probability, while suggesting an appropriate optimization function, in the spirit of the relevant channel model and type of the code, new bounds on the error probability can be derived. In this paper we apply the new bound to the problem of lower bounding the error probability of binary linear codes over the binary symmetric channel (BSC). The resulting bound improves on the latest bound appearing in the current literature, by Keren and Litsyn (2000).

IEEE Convention of Electrical and Electronics Engineers in Israel•Jun 26, 2003•2 citations
We introduce a definition of perfect and quasi-perfect codes for symmetric channels parametrized by an auxiliary output distribution. This new definition generalizes previous definitions and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to attain the meta-converse lower bound.
We define a new family of codes for symmetric classical-quantum channels and establish their optimality. To this end, we extend the classical notion of generalized perfect and quasi-perfect codes to channels defined over some finite dimensional complex Hilbert output space. The resulting optimality conditions depend on the channel considered and on an auxiliary state defined on the output space of the channel. For certainNNN-qubit classical-quantum channels, we show that codes based on a generalization of Bell states are quasi-perfect and, therefore, they feature the smallest error probability among all codes of the same blocklength and cardinality.
We derive new upper bounds on the error exponents for the maximum-likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the best earlier known bounds by Shannon-Gallager-Berlekamp (1967) and McEliece-Omura (1977). For the probability of undetected error the new bounds are better than the bounds by Levenshtein (1978, 1989) and the bound by Abdel-Ghaffar (see ibid., vol.43, p.1489-502, 1997). Moreover, we further extend the range of rates where the undetected error exponent is known to be exact. The new bounds are based on an analysis of possible distance distributions of the codes along with some inequalities relating the distance distributions to the error probabilities.
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.
A q-ary (n, k) linear code is said to be proper if, as an error-detection code, the probability of undetectable error P/sub ud/ satisfies P/sub ud//spl les/q/sup -(n-k)/ for completely symmetric channels. We show that a proper code, as an error-correction code, satisfies the expurgated bound on the decoding error probability for a class of channels with the associated Bhattacharyya distance being completely symmetric. Known results on the undetectable error probability then immediately imply that the expurgated exponent is satisfied exactly by, for example, all the binary perfect codes, binary first-order Reed-Muller codes, binary (extended) Hamming code, binary 2-error correcting primitive BCH code, and all the maximum distance separable (MDS) codes, and asymptotically by some class of the binary t-error-correcting primitive BCH codes.>
A novel technique for deriving lower bounds on the error probability when communicating one of M signals over a communication channel is proposed. At the basis of the technique stands an improvement on a recent lower bound on the probability of a union of events by de Caen (1997). The new bound includes a function which can be optimized in order to achieve the tightest results. By applying this bound to the problem of lower bounding the error probability, while suggesting an appropriate optimization function, in the spirit of the relevant channel model and type of the code, new bounds on the error probability can be derived. In this paper we apply the new bound to the problem of lower bounding the error probability of binary linear codes over the binary symmetric channel (BSC). The resulting bound improves on the latest bound appearing in the current literature, by Keren and Litsyn (2000).