A universal decoding algorithm for lattice codes

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.

Martin Bossert, F. Hergert

Kenny Barrese

J. Conway, Neil J.A. Sloane

Two kinds of algorithms are considered.1)If *** is a binary code of lengthn, a "soft decision" decoding algorithm for *** changes an arbitrary point ofR^{n}into a nearest codeword (nearest in Euclidean distance).2)Similarly, a decoding algorithm for a lattice\LambdainR^{n}changes an arbitrary point ofR^{n}into a closest lattice point. Some general methods are given for constructing such algorithms, ami are used to obtain new and faster decoding algorithms for the Gosset latticeE_{8}, the Golay code the Leech lattice.

M.A.O. da Costa e Silva, Reginaldo Palazzo

A multistage decoding algorithm is given for lattices obtained from a multilevel code formula. The algorithm is shown to have the same effective error-correcting radius as maximum-likelihood decoding, so that the performance loss is essentially determined by the increase in the effective error coefficient, for which an expression is given. The code formula generalizes some previous multilevel constructions to constructions of known single-level binary lattices with many levels, and then to decoders for them with the proposed algorithm. The trade-off between complexity reduction and performance loss is evaluated for several known lattices and two new ones, indicating that the approach is effective provided the binary codes involved in the code formula are not too short. All codes used in our constructions are binary Reed-Muller codes.>

P. Heijnen, Henk C. A. van Tilborg