IEEE Transactions on Communications

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

Ofer Amrani, Yair Be'ery

Published May 1, 1996• 14 citations

Abstract

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.

DOI: 10.1109/26.494294

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

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

The Leech lattice and the Golay code: bounded-distance decoding and multilevel constructions

Ofer Amrani, Yair Be'ery, Alexander Vardy +2 more

Multilevel constructions of the binary Golay code and the Leech lattice are described. Both constructions are based upon the projection of the Golay code and the Leech lattice onto the (6,3,4) hexacode over GF(4). However, unlike the previously reported constructions, the new multilevel constructions make the three levels independent by way of using a different set of coset representatives for one of the quaternary coordinates. Based upon the multilevel structure of the Golay code and the Leech lattice, efficient bounded-distance decoding algorithms are devised. The bounded-distance decoder for the binary Golay code requires at most 431 operations. As compared to 651 operations for the best known maximum-likelihood decoder. Efficient bounded-distance decoding of the Leech lattice is achieved by means of partitioning it into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. The complexity of the resulting decoder is only 953 real operations on the average and 1007 operations in the worst case, as compared to about 3600 operations for the best known in maximum-likelihood decoder. It is shown that the proposed algorithms decode correctly at least up to the guaranteed error-correction radius of the maximum-likelihood decoder. Thus, the loss in coding-gain is due primarily to an increase in the effective error-coefficient, which is calculated exactly for both algorithms. Furthermore, the performance of the Leech lattice decoder on the AWGN channel is evaluated experimentally by means of a comprehensive computer simulation. The results show a loss in coding-gain of less than 0.1 dB relative to the maximum-likelihood decoder for BER ranging from 10/sup -1/ to 10/sup -7/.>

IEEE Transactions on Information TheoryJul 1, 199451 citations

Reduced Complexity Bounded-distance Decoding of the Leech Lattice

Ofer Amrani, Yair Be'ery, Alexander Vardy

A new efficient algorithm for bounded-distance decoding of the Leech lattice is presented. The algorithm decodes correctly at least up to the guaranteed error-correction radius of the Leech lattice. The proposed decoder is based on projecting the points of the Leech lattice onto the codewords of the (6, 3, 4) quarternary code, the hexacode H/sub 6/. Projection on the hexacode induces partition of the Leech lattice into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. This enables bounded-distance decoding of the Leech lattice with only 1127 real operations in the worst case, as compared to about 3600 operations for the maximum-likelihood decoding of [9]. The proposed algorithm is at least 30% more efficient than Forney's algorithm [5] in terms of computational complexity, while the coding gain loss is no more than 0.05 dB (over BER ranging from 10/sup -1/ to 10/sup -6/ ).

IEEE International Symposium on Information Theory (ISIT)Aug 24, 20050 citations

More efficient soft decoding of the Golay codes

Alexander Vardy, Yair Be'ery

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

IEEE Transactions on Information TheoryMay 1, 199159 citations

A bounded-distance decoding algorithm for the Leech lattice, with generalizations

G. David Forney

An algorithm is given that decodes the Leech lattice with not much more than twice the complexity of soft-decision decoding of the Golay code. The algorithm has the same effective minimum distance as maximum-likelihood decoding and increases the effective error coefficient by less than a factor or two. The algorithm can be recognized as a member of the class of multistage algorithms that are applicable to hierarchical constructions. It is readily generalized to lattices that can be expressed in terms of binary code formulas, and in particular to construction B lattices.>

IEEE Transactions on Information TheoryJul 1, 198963 citations