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

International Symposium on Information Theory and its Applications

Decoding Multi-bit lnformation Blocks in the Golay Code

J.T. Coffey

Published Jan 1, 1994• 0 citations
OpenAlex

Abstract

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.

Related papers

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

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

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

Fast algorithms for decoding the (23, 12) binary Golay code with four-error-correcting capability

Eric Hsueh-Chan Lu, Hsiao-Peng Wuu, Y. C. CHENG +1 more

Two new algorithms for decoding the (23, 12) binary Golay code are developed with channel measurement information. For a white gaussian noise channel, each of the two algorithms achieves about 0·8 dB of decoding performance over a conventional hard-decision decoding. Furthermore, one of the algorithms requires a very small amount of computation for decoding a received block, and the other is very suitable for hardware implementation owing to its simple and regular operation. The hardware decoder, based on the latter algorithm, is designed with a pipeline such that it decodes one bit of a received block in a single system clock cycle

International Journal of Systems Science•Apr 1, 1995•11 citations

Soft decoding of the (23, 12, 7) Golay-code up to five errors

Y. Li, Lin Wang, T. K. Truong

A new decoder is proposed to decode the (23, 12, 7) binary Golay-code up to five errors. It is based on the algorithm that can correct up to four errors for the (24, 12, 8) extended Golay-code proposed by Lin et al., thereby achieving the soft decoding in the real sense for the Golay-code. For a weight-2 or weight-3 error pattern decoded by the hard decoder for correcting up to three errors, one can find the corresponding 21 weight-4 or weight-5 error patterns and choose the one with the maximum emblematic probability value, which is defined as the product of individual bit-error probabilities corresponding to the non-zero locations of the error pattern as the ultimate choice. Finally, simulation results of this decoder over additive white Gaussian noise (AWGN) channels show that the proposed method provides 0.9 dB coding gain than that of Lin et al.'s algorithm at bit-error rate of 10−5.

IET Communications•Oct 14, 2011•1 citation

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
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.
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.>
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.
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.
Two new algorithms for decoding the (23, 12) binary Golay code are developed with channel measurement information. For a white gaussian noise channel, each of the two algorithms achieves about 0·8 dB of decoding performance over a conventional hard-decision decoding. Furthermore, one of the algorithms requires a very small amount of computation for decoding a received block, and the other is very suitable for hardware implementation owing to its simple and regular operation. The hardware decoder, based on the latter algorithm, is designed with a pipeline such that it decodes one bit of a received block in a single system clock cycle
A new decoder is proposed to decode the (23, 12, 7) binary Golay-code up to five errors. It is based on the algorithm that can correct up to four errors for the (24, 12, 8) extended Golay-code proposed by Lin et al., thereby achieving the soft decoding in the real sense for the Golay-code. For a weight-2 or weight-3 error pattern decoded by the hard decoder for correcting up to three errors, one can find the corresponding 21 weight-4 or weight-5 error patterns and choose the one with the maximum emblematic probability value, which is defined as the product of individual bit-error probabilities corresponding to the non-zero locations of the error pattern as the ultimate choice. Finally, simulation results of this decoder over additive white Gaussian noise (AWGN) channels show that the proposed method provides 0.9 dB coding gain than that of Lin et al.'s algorithm at bit-error rate of 10−5.
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.>