Geometrical and performance analysis of GMD and chase decoding algorithms

The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N-o,N-eff = N-o + N-BDD where N-BDD denotes the numb er of additional, non-codeword, neighbors that are generated during the (su boptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original Generalized Minimum Distance (GMD) and Chase decoding algorithms, After careful examination of the decision regions of t hese algorithms, we derive an approximated probability ratio between the er ror contribution of a noncodeword neighbor (one of N-BDD points) and a code word nearest neighbor, For Chase Algorithm 1 it is shown that the contribut ion to error probability of a noncodeword nearest neighbor is a factor of 2 (d-1) less than the contribution of a codeword, while for Chase Algorithm 2 the factor is 2([d/2]-1), d being the minimum Hamming distance of the code . For Chase Algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented, This proce dure can also be used for specifically identifying the error patterns assoc iated with Chase Algorithm 3 and GMD. Utilizing the probability ratio, we p ropose an improved approximated upper bound on the probability of error bas ed on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.