GENERALIZED MINIMUM-DISTANCE DECODING OF EUCLIDEAN-SPACE CODES AND LATTICES

It is shown that multistage generalized minimum-distance (GMD) decodin g of Euclidean-space codes and lattices can provide an excellent trade off between performance and complexity, We introduce a reliability met ric for Gaussian channels that is easily computed from an inner produc t, and prove that a multistage GMD decoder using this metric is a boun ded-distance decoder up to the true packing radius, The effective erro r coefficient of multistage GMD decoding is determined, Two simple mod ifications in the GMD decoding algorithm that drastically reduce this error coefficient are proposed, It is shown that with these modificati ons GMD decoding achieves the error coefficient of maximum-likelihood decoding for block codes and for generalized Construction A lattices. Multistage GMD decoding of the lattices D-4, E(8), K-12, BW16, and Lam bda(24) is investigated in detail, For K-12, BW16, and Lambda(24), the GMD decoders have considerably lower complexity than the best known m aximum-likelihood or bounded-distance decoding algorithms, and appear to be the most practically attractive decoders available, For high-dim ensional codes and lattices (greater than or equal to 64 dimensions) m aximum-likelihood decoding becomes infeasible, while GMD decoding algo rithms remain quite practical, As an example, we devise a multistage G MD 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 7 60. This decoder requires only about 400 real operations, in addition to algebraic errors-and-erasures decoding of certain BCH and Hamming c odes, It therefore appears to be practically feasible to implement alg ebraic multistage GMD decoders for high-dimensional sphere packings, a nd thus achieve high effective coding gains.