Generalized minimum distance decoding algorithms for group codes in metric spaces

Steven S. Pietrobon, Robert Huijie Deng, A. Lafanechere +1 more

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.

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

A new bounded-distance (BD) decoding algorithm is presented for binary linear (n, k, d) block codes on additive white Gaussian noise channels. The algorithm is based on the generalized minimum distance (GMD) decoding algorithm of Forney (1989) using the acceptance criterion of Taipale and Pursley (GMD/TP) proposed in 1991. It is shown that the GMD/TP decoding algorithm is a BD decoding algorithm with effective error coefficient (/sup n//sub d/). It is also shown that the decision regions of GMD/TP are good inner approximations of those of full GMD decoding, and therefore full GMD decoding is BD and has an effective error coefficient that is well approximated by (/sup n//sub d/). Moreover, by adding a d-erasure-correction step to GMD decoding, the effective error coefficient can be reduced to A/sub d/, the number of minimum-weight codewords, which is the same as the effective error coefficient of maximum-likelihood decoding. The decoding algorithm is mainly based on algebraic errors-and-erasures decoding and therefore has polynomial rather than exponential complexity.

Diego Ruano

George C. Clark, J. Bibb Cain

Yuansheng Tang, Toru Fujiwara, Tadao Kasami

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.