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

On the complete decoding of binary linear codes (Corresp.)

Michele Elia, G. Prati

Published Jul 1, 1985• 8 citations
Publisher

Abstract

Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.

DOI
10.1109/tit.1985.1057059

Related papers

To the Question of Almost Maximum-Likelihood Decoding

Mikhail Afanasev, Andrei A. Ovchinnikov

Evseev’s lemma claims that if we use the decoding by a standard array and use coset leaders having the weight not greater than Gilbert-Varshamov distance then the probability of error decoding will become not greater than the probability of error decoding of maximum-likelihood multiplied by two. However, the estimation of tightness of this bound is an open problem. In this work we perform the estimation of the accuracy of Evseev’s lemma on the example of several linear random codes by simulating them in a binary-symmetric channel.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)•Jun 1, 2020•1 citation

Optimal information bit decoding of linear block codes

Aaron B. Kiely, J.T. Coffey, Mark R. Bell

We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>

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

Linear block codes for error detection (Corresp.)

Tadao Kasami, Torleiv Kløve, Shu Lin

The probability of undetected error of linear block codes for use on a binary symmetric channel is investigated. Upper hounds are derived. Several classes of linear block codes are proved to have good error-detecting capability.

IEEE Transactions on Information Theory•Jan 1, 1983•37 citations

Decoding Multi-bit lnformation Blocks in the Golay Code

J.T. Coffey

Decoding rules for linear block codes used over binary symmetric channels with crossover probability p when the goal is to minimize the probability that sub-blocks of information bits are in error are considered, with application to the (24,12,8) Golay code. (The optimal rules to minimize the probability of individual bits being in error are known for all p.) The results require detailed knowledge of the weight enumerators of given sub codes, which can be calculated from knowledge of the orbit and coset structure of the code. It is interesting that in all cases examined, the rule in decoding a block given the coset received is to select the symbol that is optimal as p → 0 or the symbol that is optimal as p → 1/2, depending on p.

International Symposium on Information Theory and its Applications•Jan 1, 1994•0 citations

The Simplex Codes and Other Even-Weight Binary Linear Codes for Error Correction

Tor Helleseth, Torleiv Kløve, V.I. Levenshtein

The probability of correct decoding on the binary-symmetric channel is studied. In particular, a class of codes with the same lengths and dimensions as the linear simplex codes, but with larger probability of correct decoding for all parameters p, 0 < p < 1/2, is given.

IEEE Transactions on Information Theory•Oct 26, 2004•7 citations

On some properties of the undetected error probability of linear codes (Corresp.)

S. Leung-Yan-Cheong, Earl R. Barnes, Donna L. Friedman

A recent paper [1] discussed the2^{-p}bound (wherep = n- k) for the probability of undetected errorP(\epsilon)for an(n,k)block code used for error detection on a binary symmetric channel. This investigation is continued and extended and dual codes are studied. The dual and extension of a perfect code obey the2^{-p}bound, but this is not necessarily true for arbitrary codes that obey the bound. Double-error-correcting BCH codes are shown to obey the bound. Finally the problem of constructing uniformly good codes is examined.

IEEE Transactions on Information Theory•Jan 1, 1979•59 citations
Complete decoding of systematic linear block codes by standard arrays with coset leaders not necessarily of minimal weight gives, in several interesting cases on the binary symmetric channel with error probabilityp, a smaller symbol error probability than decoding using the coset leaders of minimum weight. The proposed choice of the coset leaders allows for the classes of uniformly packed and nearly perfect binary codes to achieve a lower information bit error probability, at least forpsufficiently near zero.
Evseev’s lemma claims that if we use the decoding by a standard array and use coset leaders having the weight not greater than Gilbert-Varshamov distance then the probability of error decoding will become not greater than the probability of error decoding of maximum-likelihood multiplied by two. However, the estimation of tightness of this bound is an open problem. In this work we perform the estimation of the accuracy of Evseev’s lemma on the example of several linear random codes by simulating them in a binary-symmetric channel.
We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>
Decoding rules for linear block codes used over binary symmetric channels with crossover probability p when the goal is to minimize the probability that sub-blocks of information bits are in error are considered, with application to the (24,12,8) Golay code. (The optimal rules to minimize the probability of individual bits being in error are known for all p.) The results require detailed knowledge of the weight enumerators of given sub codes, which can be calculated from knowledge of the orbit and coset structure of the code. It is interesting that in all cases examined, the rule in decoding a block given the coset received is to select the symbol that is optimal as p → 0 or the symbol that is optimal as p → 1/2, depending on p.
A recent paper [1] discussed the2^{-p}bound (wherep = n- k) for the probability of undetected errorP(\epsilon)for an(n,k)block code used for error detection on a binary symmetric channel. This investigation is continued and extended and dual codes are studied. The dual and extension of a perfect code obey the2^{-p}bound, but this is not necessarily true for arbitrary codes that obey the bound. Double-error-correcting BCH codes are shown to obey the bound. Finally the problem of constructing uniformly good codes is examined.