IEE Proceedings I Communications Speech and Vision

Two-level decoding of (32, 16, 8) quadratic residue code

Jing Shun Yuan, C.S. Chen, Shang‐Chih Ma

Published Jan 1, 1993• 9 citations

Abstract

The Pless construction of the (24, 12, 8) extended Golay code can be modified to construct the (32, 16, 8) extended QR code. Some structural similarities are discovered between the (32, 16, 8) QR code and the (24, 12, 8) Golay code. A simple decoder is developed based on the two-level structure of the (32, 16, 8) QR code. In addition to correcting all three or less bit errors, the proposed algorithm is able to correct some four-bit error patterns. Recently, soft-logic decoding of block codes has found increasing practical applications. The two-level structure renders an extension of Vardy and Be‘ery’s fast algorithm to the (32, 16, 8) QR code. The Vardy-Be‘ery’s algorithm is, so far, the most efficient scheme for the Golay code in the literature, with direct application impact. Its extension to the (32, 16, 8) code is also computationally efficient, as analysed in detail.

DOI: 10.1049/ip-i-2.1993.0059

Related papers

On Decoding of the (89, 45, 17) Quadratic Residue Code

Lin Wang, Yong Li, Trieu‐Kien Truong +1 more

In this paper, Three decoding methods of the (89, 45, 17) binary quadratic residue (QR) code to be presented are hard, soft and linear programming decoding algorithms. Firstly, a new hybrid algebraic decoding algorithm for the (89, 45, 17) QR code is proposed. It uses the Laplace formula to obtain the primary unknown syndromes, as done in Lin et al.'s algorithm when the number of errors v is less than or equal to 5, whereas Gaussian elimination is adopted to compute the unknown syndromes when v ≥ 6. Secondly, an appropriate modification to the algorithm developed by Chase is also given in this paper. Therefore, combining the proposed algebraic decoding algorithm with the modified Chase-II algorithm, called a new soft-decision decoding algorithm, becomes a complete soft decoding of QR codes. Thirdly, in order to further improve the error-correcting performance of the code, linear programming (LP) is utilized to decode the (89, 45, 17) QR code. Simulation results show that the proposed algebraic decoding algorithm reduces the decoding time when compared with Lin et al.'s hard decoding algorithm, and thus significantly reduces the decoding complexity of soft decoding while maintaining the same bit error rate (BER) performance. Moreover, the LP-based decoding improves the error-rate performance almost without increasing the decoding complexity, when compared with the new soft-decision decoding algorithm. It provides a coding gain of 0.2 dB at BER = 2 × 10-6.

IEEE Transactions on CommunicationsJan 8, 201311 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 CommunicationsFeb 4, 200911 citations

On the pless-construction and ML decoding of the (48, 24, 12) quadratic residue code

Morteza Esmaeili, Thomas Aaron Gulliver, Amir Keyvan Khandani

We present a method for maximum likelihood decoding of the (48,24,12) quadratic residue code. This method is based on projecting the code onto a subcode with an acyclic Tanner graph, and representing the set of coset leaders by a trellis diagram. This results in a two level coset decoding which can be considered a systematic generalization of the Wagner rule. We show that unlike the (24,12,8) Golay code, the (48,24,12) code does not have a Pless-construction which has been an open question in the literature. It is determined that the highest minimum distance of a (48,24) binary code having a Pless (1986) construction is 10, and up to equivalence there are three such codes.

IEEE Transactions on Information TheoryMay 29, 20034 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 CommunicationsOct 14, 20111 citation

Convolutional encoding of self-dual codes

G. Solomon

There exist almost complete convolutional encodings of self-dual codes, i.e., block codes of rate 1/2 with weights w, w = 0 mod 4. The codes are of length 8m with the convolutional portion of length 8m-2 and the nonsystematic information of length 4m-1. The last two bits are parity checks on the two (4m-1) length parity sequences. The final information bit complements one of the extended parity sequences of length 4m. Solomon and van Tilborg have developed algorithms to generate these for the Quadratic Residue (QR) Codes of lengths 48 and beyond. For these codes and reasonable constraint lengths, there are sequential decodings for both hard and soft decisions. There are also possible Viterbi-type decodings that may be simple, as in a convolutional encoding/decoding of the extended Golay Code. In addition, the previously found constraint length K = 9 for the QR (48, 24;12) Code is lowered here to K = 8.

Feb 15, 19942 citations

On soft-decoding of the (24, 12, 8) Golay code

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

In this paper, an efficient soft-decision decoder of the (24, 12, 8) binary Golay code for the four errors, composed of two stages: a conventional hard decoder up to three errors and the soft decoding for 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 lookup 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 additive white Gaussian noise (AWGN) shows that at least 92% and 99% of weight-4 error patterns occurred are corrected if a bit-energy to noise-spectral-density ratios (Eb/N0) are greater than 2 dB and 5 dB, respectively.

IEEE Region 10 Conference (TENCON)Oct 1, 20074 citations