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

Globecom

Decoding the (23,12,7) Golay code using bit-error probability estimates

G. Dubney, I.S. Reed

Published Jan 1, 2005• 19 citations
Publisher

Abstract

The (23,12,7) Golay code is a perfect linear error-correcting code that can correct all patterns of three or fewer errors in 23 bit positions. A simple BCH decoding algorithm, given in E. Berlekamp (1968), can decode the (23,12,7) Golay code provided there are no more than two errors. The shift-search algorithm, developed by Reed et a. (1990), sequentially inverts the information bits until the third error is canceled. It then utilizes the BCH decoding algorithm to correct the remaining two errors. In this paper a simplified decoding algorithm, called the reliability-search algorithm, is proposed. This algorithm uses bit-error probability estimates to cancel the third error and then uses the BCH decoding algorithm to correct the remaining two errors. Simulation results show that this new algorithm significantly reduces the decoding complexity for correcting the third error while maintaining the same BER performance.

DOI
10.1109/glocom.2005.1577867

Related papers

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

Decoding the (47,24,11) quadratic residue code using bit-error probability estimates

G. Dubney, I.S. Reed, Trieu‐Kien Truong +1 more

A new algorithm is developed to facilitate faster decoding of the (47,24,11) quadratic residue (QR) code. This decoder, based on the idea first developed by Reed in a 1959 MIT Lincoln Laboratory Report, uses real channel data to estimate the individual bit-error probabilities in a received word. The algorithm then sequentially inverts the bits with the highest probability of error until one of the errors is canceled. The remaining errors are then corrected by the use of algebraic decoding techniques. This new algorithm, called the reliability-search algorithm, is a complete decoder that significantly reduces the decoding complexity in terms of CPU time while maintaining the same bit-error rate (BER) performance. In fact, this algorithm is an appropriate modification to the algorithm developed by Chase.

IEEE Transactions on Communications•Jul 1, 2009•12 citations

Decoding of the (24, 12, 8) extended Golay code up to four errors

Tsung-Chieh Lin, Trieu‐Kien Truong, Wen-Ku Su +2 more

A new decoder is proposed to decode the (24, 12, 8) binary extended Golay code up to four errors. It consists of the conventional hard decoder for correcting up to three errors, the detection algorithm for four errors and the soft decoding for four errors. For a weight-4 error in a received 24-bit word, Method 1 or 2 is developed to determine all six possible error patterns. The emblematic probability value of each error pattern is then defined as the product of four individual bit-error probabilities corresponding to the locations of the four errors. The most likely one among these six error patterns is obtained by choosing the maximum of the emblematic probability values of all possible error patterns. Finally, simulation results of this decoder in additive white Gaussian noise show that at least 93% and 99% of weight-4 error patterns that occur are corrected if the two Eb/N0 ratios are greater than 2 and 5 dB, respectively. Consequently, the proposed method can achieve a better percentage of successful decoding for four errors at variable signal-to-noise ratios than Lu et al.'s algorithm in software. However, the speed of the method is slower than Lu et al.'s algorithm.

IET Communications•Feb 4, 2009•11 citations

Fast decoding of the (23, 12, 7) Golay code with four‐error‐correcting capability

Shao‐I Chu, Hung‐Peng Lee, Hsin‐Chiu Chang

ABSTRACT In this paper, a fast and efficient decoding algorithm for correcting the (23, 12, 7) Golay code up to four errors is presented. The aim of this paper is to develop a fast syndrome‐group search method for finding the candidate codewords by utilizing the property that the syndromes of the weight‐4 error patterns are identical to that of the weight‐3 error pattern. When the set of the candidate codewords is constructed, the most likely one is determined by assessing the corresponding correlation metrics. The well‐known Chase‐II decoder, which needs to perform the hard‐decision decoder multiple times, acts as a comparison basis. Simulation results over the additive white Gaussian noise channel show that the decoding complexity of the proposed method is averagely reduced by at least 86% in terms of the decoding time. Furthermore, the successful decoding percentage of the new decoder in the case of four errors is always superior to Chase‐II decoder. At the signal‐to‐noise ratio of 0 dB, the proposed algorithm still can correct up to 97.40% weight‐4 error patterns. The overall bit error rate performance of the proposed decoder is close to that of Chase‐II decoder. It implies that the new decoder is beneficial to the practical implementation. Copyright © 2011 John Wiley & Sons, Ltd.

European Transactions on Telecommunications•Jul 12, 2011•5 citations

Decoding the extended binary Golay code by an iterative invert-one-bit scheme

Wen-Ku Su, Pei-Yu Shih, Tsung‐Ching Lin +1 more

In this paper, a new decoding algorithm of the extended binary Golay code is proposed. Based on the proposition developed in this paper, all probable patterns of occurred weight-4 error, which are always decoded to the same weight-3 error pattern, are determined from an iterative invert-one-bit scheme instead of the look-up table of weight-7 codewords. And the most possible one will be obtained by estimating the emblematic probability values of all probable patterns. The simulation result of this decoder in AWGN shows that more than 99% of four errors are corrected if Eb/N0 is greater than 5 dB.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•3 citations

Soft-decoding of the (23, 12, 7) Binary Golay Code

Wen-Ku Su, Pei-Yu Shih, Tsung‐Ching Lin +1 more

Abstract—Since the (23, 12, 7) binary Golay code is a perfect code, a weight-4 error occurred is always decoded as a weight-3 error pattern by a hard decoding method. In this paper, an efficient soft-decision decoder of the (23, 12, 7) binary Golay code up to the four errors is proposed. All probable patterns of occurred weight-4 error, which are always decoded to the same weight-3 error pattern, are determined from the look-up table of weight-7 codewords. And the most possible error pattern of weight-4 or weight-3 will be obtained by estimating the emblematic probability values of all probable patterns. The simulation result of this decoder in additive white Gaussian noise (AWGN) shows that at least 93 % and 99 % of weight-4 error patterns occurred are corrected if a bit-energy to noise-spectral-density ratios (E b/N 0) are greater than 3 dB and 6 dB, respectively, and at least 96 % of weight-3 error patterns occurred are corrected for any dB. I.

International MultiConference of Engineers and Computer Scientists•Mar 1, 2008•1 citation
The (23,12,7) Golay code is a perfect linear error-correcting code that can correct all patterns of three or fewer errors in 23 bit positions. A simple BCH decoding algorithm, given in E. Berlekamp (1968), can decode the (23,12,7) Golay code provided there are no more than two errors. The shift-search algorithm, developed by Reed et a. (1990), sequentially inverts the information bits until the third error is canceled. It then utilizes the BCH decoding algorithm to correct the remaining two errors. In this paper a simplified decoding algorithm, called the reliability-search algorithm, is proposed. This algorithm uses bit-error probability estimates to cancel the third error and then uses the BCH decoding algorithm to correct the remaining two errors. Simulation results show that this new algorithm significantly reduces the decoding complexity for correcting the third error while maintaining the same BER performance.
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.
A new algorithm is developed to facilitate faster decoding of the (47,24,11) quadratic residue (QR) code. This decoder, based on the idea first developed by Reed in a 1959 MIT Lincoln Laboratory Report, uses real channel data to estimate the individual bit-error probabilities in a received word. The algorithm then sequentially inverts the bits with the highest probability of error until one of the errors is canceled. The remaining errors are then corrected by the use of algebraic decoding techniques. This new algorithm, called the reliability-search algorithm, is a complete decoder that significantly reduces the decoding complexity in terms of CPU time while maintaining the same bit-error rate (BER) performance. In fact, this algorithm is an appropriate modification to the algorithm developed by Chase.
A new decoder is proposed to decode the (24, 12, 8) binary extended Golay code up to four errors. It consists of the conventional hard decoder for correcting up to three errors, the detection algorithm for four errors and the soft decoding for four errors. For a weight-4 error in a received 24-bit word, Method 1 or 2 is developed to determine all six possible error patterns. The emblematic probability value of each error pattern is then defined as the product of four individual bit-error probabilities corresponding to the locations of the four errors. The most likely one among these six error patterns is obtained by choosing the maximum of the emblematic probability values of all possible error patterns. Finally, simulation results of this decoder in additive white Gaussian noise show that at least 93% and 99% of weight-4 error patterns that occur are corrected if the two Eb/N0 ratios are greater than 2 and 5 dB, respectively. Consequently, the proposed method can achieve a better percentage of successful decoding for four errors at variable signal-to-noise ratios than Lu et al.'s algorithm in software. However, the speed of the method is slower than Lu et al.'s algorithm.
ABSTRACT In this paper, a fast and efficient decoding algorithm for correcting the (23, 12, 7) Golay code up to four errors is presented. The aim of this paper is to develop a fast syndrome‐group search method for finding the candidate codewords by utilizing the property that the syndromes of the weight‐4 error patterns are identical to that of the weight‐3 error pattern. When the set of the candidate codewords is constructed, the most likely one is determined by assessing the corresponding correlation metrics. The well‐known Chase‐II decoder, which needs to perform the hard‐decision decoder multiple times, acts as a comparison basis. Simulation results over the additive white Gaussian noise channel show that the decoding complexity of the proposed method is averagely reduced by at least 86% in terms of the decoding time. Furthermore, the successful decoding percentage of the new decoder in the case of four errors is always superior to Chase‐II decoder. At the signal‐to‐noise ratio of 0 dB, the proposed algorithm still can correct up to 97.40% weight‐4 error patterns. The overall bit error rate performance of the proposed decoder is close to that of Chase‐II decoder. It implies that the new decoder is beneficial to the practical implementation. Copyright © 2011 John Wiley & Sons, Ltd.
In this paper, a new decoding algorithm of the extended binary Golay code is proposed. Based on the proposition developed in this paper, all probable patterns of occurred weight-4 error, which are always decoded to the same weight-3 error pattern, are determined from an iterative invert-one-bit scheme instead of the look-up table of weight-7 codewords. And the most possible one will be obtained by estimating the emblematic probability values of all probable patterns. The simulation result of this decoder in AWGN shows that more than 99% of four errors are corrected if Eb/N0 is greater than 5 dB.
Abstract—Since the (23, 12, 7) binary Golay code is a perfect code, a weight-4 error occurred is always decoded as a weight-3 error pattern by a hard decoding method. In this paper, an efficient soft-decision decoder of the (23, 12, 7) binary Golay code up to the four errors is proposed. All probable patterns of occurred weight-4 error, which are always decoded to the same weight-3 error pattern, are determined from the look-up table of weight-7 codewords. And the most possible error pattern of weight-4 or weight-3 will be obtained by estimating the emblematic probability values of all probable patterns. The simulation result of this decoder in additive white Gaussian noise (AWGN) shows that at least 93 % and 99 % of weight-4 error patterns occurred are corrected if a bit-energy to noise-spectral-density ratios (E b/N 0) are greater than 3 dB and 6 dB, respectively, and at least 96 % of weight-3 error patterns occurred are corrected for any dB. I.