Bounded-distance decoding: algorithms, decision regions, and pseudo nearest neighbors

For a code C, bounded distance decoding algorithms perform as optimal algorithms within the balls B(c), centered at the codewords c∈C, with radius equal to half the minimum Euclidean distance of the code. Thus distinct bounded-distance algorithms vary in performance due to their different behavior outside the balls B(c). We investigate this issue by analyzing the decision regions of some known (e.g., GMD) and some new bounded-distance algorithms presented in this work. In particular, we show that there are three distinct types of nearest neighbors and classify them according to their influence on the decision region. Simulation results and computer-generated images of the decision regions are provided to illustrate the analytical results for block and lattice codes on additive white Gaussian noise (AWGN) channels