IEEE International Symposium on Information Theory (ISIT)

Efficient decoding of the Gosset, Coxeter-Todd and the Barnes-Wall lattices

Moshe Ran, Jakov Snyders

Published Nov 27, 2002• 9 citations

Abstract

Low complexity maximum-likelihood and bounded-distance soft decoding algorithms are presented for several block and lattice codes. The bounded-distance algorithms are based upon multilevel constructions of the codes. To demonstrate the approach, maximum-likelihood and bounded-distance decoders are devised for several well known codes and sphere packings in 8, 12 and 16 dimensions.

DOI: 10.1109/isit.1998.708678

Related papers

Generalised minimum distance decoding of Reed-Muller codes and Barnes-Wall lattices

Chunxiang Wang, Ba-Zhong Shen, Kenneth K. Tzeng

Low complexity soft decision decoding algorithms for Reed-Muller codes and Barnes-Wall lattices are presented. These algorithms are constructed based on the usage of generalised minimum distance (GMD) decoding recursively. Evaluation of the algorithms on AWGN channel through computer simulation indicates a slight degradation in performance, compared to maximum likelihood decoding, but with considerable reduction in complexity.

IEEE International Symposium on Information Theory (ISIT)Nov 19, 20024 citations

A Bounded-Distance Decoding Algorithm for Lattices Obtained from a Generalized Code Formula

M.A.O. da Costa e SiIva, Reginaldo Palazzo Júnior

A multistage decoding algorithm is given for lattices obtained from a generalized code formula. The corresponding multilevel construction is based on a chain of two-way lattice partitions and a family of binary linear block codes, whereas the multistage algorithm involves the use of a maximum-likelihood (ML) decoding algorithm for each two-way lattice partitions as well as a soft-decision ML decoding algorithm for each binary linear block code. The algorithm is shown to have the same effective error-correcting radius as ML decoding. Several known lattices and two new ones were then constructed by the generalized code formula. The trade-off between complexity reduction and performance loss achieved by the proposed algorithm is presented.

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

clidean-Space e inimurn-Distance Decodi

G. David Forney

It is shown that multistage generalized minimum- distance (GMD) decoding of Euclidean-space codes and lattices can provide an excellent tradeoff between performance and com- plexity. We introduce a reliability metric for Gaussian channels that is easily computed from an inner product, and prove that a multistage GMD decoder using this metric is a bounded- distance decoder up to the true packing radius. The effective error coefficient of multistage GMD decoding is determined. Two simple modifications in the GMD decoding algorithm that drastically reduce this error coefficient are proposed. It is shown that with these modifications GMD decoding achieves the error coefficient of maximum-likelihood decoding for block codes and for generalized Construction A lattices. Multistage GMD decod- ing of the lattices Dg, Ea, K12, BW16, and A24 is investigated in detail. For 1<12,BW~, and A24, the GMD decoders have considerably lower complexity than the best known maximum- likelihood or bounded-distance decoding algorithms, and appear to be the most practically attractive decoders available. For high-dimensional codes and lattices (2 64 dimensions) maximum- likelihood decoding becomes infeasible, while GMD decoding algorithms remain quite practical. As an example, we devise a multistage GMD decoder for a 128-dimensional sphere packing with a nominal coding gain of 8.98 dB that attains an effective error coefficient of 1 365 760. This decoder requires only about 400 real operations, in addition to algebraic errors-and-erasures decoding of certain BCH and Hamming codes. It therefore ap- pears to be practically feasible to implement algebraic multistage GMD decoders for high-dimensional sphere packings, and thus achieve high effective coding gains.

Jan 1, 19960 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 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

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

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