THE LEECH LATTICE AND GOLAY CODE - BOUNDED-DISTANCE DECODING AND MULTILEVEL CONSTRUCTIONS

Multilevel constructions of the binary Golay code and the Leech lattic e are described. Both constructions are based upon the projection of t he Golay code and the Leech lattice onto the (6,3,4) hexacode over GF( 4). However, unlike the previously reported constructions, the new mul tilevel constructions make the three levels independent by way of usin g a different set of coset representatives for one of the quaternary c oordinates. 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 requir es 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 Q24, beyond the conventional partition into two H24 cosets. The complexity of the resulting decoder is only 953 real operations o n the average and 1007 operations in the worst case, as compared to ab out 3600 operations for the best known 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 decod er. Thus, the loss in coding-gain is due primarily to an increase in t he effective error-coefficient, which is calculated exactly for both a lgorithms. Furthermore, the performance of the Leech lattice decoder o n the AWGN channel is evaluated experimentally by means of a comprehen sive computer simulation. The results show a loss in coding-gain of le ss than 0.1 dB relative to the maximum-likelihood decoder for BER rang ing from 10(-1) to 10(-7).