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

Optimal information bit decoding of linear block codes

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

Published Jan 1, 1995• 11 citations
Publisher

Abstract

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.>

DOI
10.1109/18.370113

Related papers

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

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

Michele Elia, G. Prati

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.

IEEE Transactions on Information Theory•Jul 1, 1985•8 citations

Optimal information bit encoding of linear block codes

Houshou Chen, J.T. Coffey

This paper examines the problem of finding an optimal generator matrix of a linear block code C over a binary symmetric channel in the quiet region (i.e., crossover probability p/spl rarr/0) when the goal is to minimize the probability of an information bit error. We present an infinite class of cyclic codes whose optimal generator matrices are nonseparable. The problem is linked to whether the minimum weight codewords form a basis of C.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•0 citations

Implementing gradient descent decoding

Robert A. Liebler

Abstract Given a linear block code on a BSC channel, and arbitrary pre-determined information about the coset of each possible received sequence, a method is given for construction of a new kind of parity check matrix that carries the given information. This pre-determined coset data is easily reconstructed by a simple decoder. When this coset information is related to coset leader weight, there is simple iterative gradient descent algorithm that is optimal, provably accurate and potentially of low complexity. An explicit gradient function construction is given for an code for which pseudo-codewords obstruct LDPC decoding convergence. 1 Introduction Many communication channels accept as input binary strings and return output strings of the same length that have been altered and whose terms can be interpreted as "the probability that 1 was sent in this position. " This paper is restricted to the binary symmetric channel (BSC) for which the output is also binary although the basic ideas seem to apply more generally. The task of a decoding algorithm is to reconstruct sent message(s) from the channel output. There are several critical attributes of a decoding algorithm. The design complexity is a measure of the effort required to design and implement an instance of the algorithm. The implementation cost is a measure of the (time and space) resources required to decode messages once the algorithm is implemented. The apparent accuracy of an algorithm is a measure of its ability to actually identify a nearest codeword to a given message in practice. The proven accuracy is a measure of the algorithm's proven ability to correctly move from message to nearest codeword without failure of any kind. A decoding algorithm is optimal if it correctly identifies the most likely channel error for each channel output for which there is a unique such error.

The Michigan Mathematical Journal•May 1, 2009•10 citations

On decoding rules to minimize the probability of information bit errors

Bruce L. Montgomery, B. V. K. Vijaya Kumar

Decoding rules to minimize the probability of information bit errors in binary linear block codes are investigated. A novel decoding rule is proposed and compared to a recently proposed rule (see M. Elia and G. Prati, 1985) and to the standard rule, with respect to both the information bit error rate and the information word error rate. It is concluded that the proposed rule not only can be implemented much more efficiently that the standard rule, but also is superior with respect to either error rate. Some particular codes have been presented to show that the authors' rule can coincide or can differ from Elia and Prati's rule when applied to a given code.>

IEEE Transactions on Information Theory•Jul 1, 1988•2 citations

Optimal generator matrices of binary cyclic codes over the binary symmetric channel

Houshou Chen

This paper considers the optimal generator matrices of a binary cyclic code over a binary symmetric channel with crossover probability p rarr 0 when the goal is to minimize the probability of an information bit error. A given code has many encoder realizations and the information bit error probability is a function of this realization. We derive some sufficient conditions for a binary cyclic code to have systematic optimal generator matrices under bounded distance decoding and determine many binary cyclic codes satisfying these properties.

Asia-Pacific Conference on Communications (APCC)•Oct 1, 2007•0 citations
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.
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.
Abstract Given a linear block code on a BSC channel, and arbitrary pre-determined information about the coset of each possible received sequence, a method is given for construction of a new kind of parity check matrix that carries the given information. This pre-determined coset data is easily reconstructed by a simple decoder. When this coset information is related to coset leader weight, there is simple iterative gradient descent algorithm that is optimal, provably accurate and potentially of low complexity. An explicit gradient function construction is given for an code for which pseudo-codewords obstruct LDPC decoding convergence. 1 Introduction Many communication channels accept as input binary strings and return output strings of the same length that have been altered and whose terms can be interpreted as "the probability that 1 was sent in this position. " This paper is restricted to the binary symmetric channel (BSC) for which the output is also binary although the basic ideas seem to apply more generally. The task of a decoding algorithm is to reconstruct sent message(s) from the channel output. There are several critical attributes of a decoding algorithm. The design complexity is a measure of the effort required to design and implement an instance of the algorithm. The implementation cost is a measure of the (time and space) resources required to decode messages once the algorithm is implemented. The apparent accuracy of an algorithm is a measure of its ability to actually identify a nearest codeword to a given message in practice. The proven accuracy is a measure of the algorithm's proven ability to correctly move from message to nearest codeword without failure of any kind. A decoding algorithm is optimal if it correctly identifies the most likely channel error for each channel output for which there is a unique such error.
Decoding rules to minimize the probability of information bit errors in binary linear block codes are investigated. A novel decoding rule is proposed and compared to a recently proposed rule (see M. Elia and G. Prati, 1985) and to the standard rule, with respect to both the information bit error rate and the information word error rate. It is concluded that the proposed rule not only can be implemented much more efficiently that the standard rule, but also is superior with respect to either error rate. Some particular codes have been presented to show that the authors' rule can coincide or can differ from Elia and Prati's rule when applied to a given code.>
This paper considers the optimal generator matrices of a binary cyclic code over a binary symmetric channel with crossover probability p rarr 0 when the goal is to minimize the probability of an information bit error. A given code has many encoder realizations and the information bit error probability is a function of this realization. We derive some sufficient conditions for a binary cyclic code to have systematic optimal generator matrices under bounded distance decoding and determine many binary cyclic codes satisfying these properties.