IEEE Transactions on Information Theory

More efficient soft decoding of the Golay codes

Alexander Vardy, Yair Be'ery

Published May 1, 1991• 59 citations

Abstract

An algorithm for maximum-likelihood soft-decision decoding of the binary (24,12,8) Golay code is presented. The algorithm involves projecting the codewords of the binary Golay code onto the codewords of the (6,3,4) code over GF(4)-the hexacode. The complexity of the proposed algorithm is at most 651 real operations. Along similar lines, the tetracode may be employed for decoding the ternary (12,6,6) Golay code with only 530 real operations. The proposed algorithm also implies a reduction in the number of computations required for decoding the Leech lattice.>

DOI: 10.1109/18.79928

Related papers

Efficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code

Ofer Amrani, Yair Be'ery

Two soft-decision decoding algorithms for the (6, 3, 4) quaternary code hexacode are presented. Both algorithms realize half the minimum Euclidean distance of the code. The proposed algorithms are most practical. In using them, bounded-distance decoding of the Golay code and the Leech lattice are performed with at most 187 and 519 real-number operations respectively. Compare this to 651, respectively 3595, operations required by the best known maximum likelihood decoders (Vardy and Be'ery, 1991, 1993), and 431, respectively 1007, operations required by the bounded-distance decoders (Amrani et al., 1994). We present some simulation results for the proposed Leech lattice decoders revealing near-optimal performance. A comparison to known trellis codes is also provided.

IEEE Transactions on CommunicationsMay 1, 199614 citations

Maximum likelihood soft decoding of binary block codes and decoders for the Golay codes

Jakov Snyders, Yair Be'ery

Maximum-likelihood soft-decision decoding of linear block codes is addressed. A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code.>

IEEE Transactions on Information TheoryJan 1, 1989112 citations

Efficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code

Ofer Amrani, Yair Be'ery

Two soft-decision algorithms for decoding the (6,3,4) quaternary code, the hexacode, are presented. Both algorithms have the same guaranteed error correction radius as that of maximum-likelihood decoding. In using them, bounded-distance decoding of the Golay code and the Leech lattice are performed in at most 187 and 519 real operations respectively. We present some simulation results for the Leech lattice decoder revealing near-optimal performance. A comparison to known trellis codes is also provided.>

IEEE International Symposium on Information Theory (ISIT)Dec 17, 20026 citations

A low-complexity soft-decision decoding architecture for the binary extended Golay code

Patrick Adde, Raphaël Le Bidan

The (24, 12, 8) extended binary Golay code is a well-known rate-1/2 short block-length linear error-correcting code with remarkable properties. This paper investigates the design of an efficient low-complexity soft-decision decoding architecture for this code. A dedicated algorithm is introduced that takes advantage of the code's properties to simplify the decoding process. Simulation results show that the proposed algorithm achieves close to maximum-likelihood performance with low computational cost. The decoder architecture is described, and VLSI synthesis results are presented.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)Dec 1, 201212 citations

On maximum likelihood soft decoding of some binary self-dual codes

Moshe Ran, Jakov Snyders

Efficient algorithms are derived for maximum likelihood (ML) soft-decision decoding of some binary self-dual codes. A family of easily decodable self-dual codes is derived by modifying a known F/sub 24/, which has a weight distribution resembling that of the (24, 12, 8) Golay code G/sub 24/. The ML decoding of F/sub 24/ is accomplished by only 227 real additions, compared to 651 required for G/sub 24/, yet the error rates of the two decoders are similar for moderate noise conditions.>

IEEE Transactions on CommunicationsMar 1, 199313 citations

Even more efficient bounded-distance decoding of the hexacode, the Golay code, and the Leech lattice

Alexander Vardy

We present a new bounded-distance decoding algorithm for the hexacode, which requires at most 34 real operations in the worst case, as compared to 57 such operations in the best previously known decoder. The new algorithm is then employed for bounded-distance decoding of the Leech lattice and the Golay code. The error-correction radius of the resulting decoders is equal to that of a maximum-likelihood decoder. The resulting decoding complexity is at most 331 real operations for the Leech lattice and at most 121 operations for the Golay code. For all the three codes-the hexacode, the Golay code, and the Leech lattice-the proposed decoders are considerably more efficient than any decoder presently known.>

IEEE Transactions on Information TheoryJan 1, 199537 citations