Recently, high reliability is required in digital communications. Research on error correcting codes are actively conducted to achieve high reliable communications. In this study, a method to reduce average computational complexity of Generalized Minimum Distance (GMD) decoding is proposed. GMD decoding can be implemented by several times bounded distance decoding (BDD). The proposed method reduces the average number of BDDs. The effectiveness of reduction on average execution time of the proposed method is confirmed against a simple method by computer simulations.
Recently, high reliability is required in digital communications. Research on error correcting codes are actively conducted to achieve high reliable communications. In this study, a method to reduce average computational complexity of Generalized Minimum Distance (GMD) decoding is proposed. GMD decoding can be implemented by several times bounded distance decoding (BDD). The proposed method reduces the average number of BDDs. The effectiveness of reduction on average execution time of the proposed method is confirmed against a simple method by computer simulations.
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.
We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.
The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N/sub 0,eff/=N/sub 0/+N/sub BDD/. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N/sub BDD/ points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2/sup d-1/ less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2/sup [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 procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.
For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.
The error-correction capability and the performance of generalized minimum distance decod- ing based on threshold erasing is studied as a function of the number of decoding trials and of the allowable reliability values. Generalized Minimum Distance (GMD) decoding, as intro- duced by Forney (l), is a multitrial decoding algorithm that combines reliability information, represented by numbers in the closed interval (0,1), with algebraic decoding algorithms for error correction. In each trial, a fixed number of the most unreliable symbols in the received sequence is erased. If a cer- tain distance criterion is satisfied, Forney has shown that the transmitted codeword can be retrieved in at most (d/2) trials, where d is the Hamming distance of the code. In this work, we study a variation on Forney's scheme where, in each trial, symbols whose reliabilities are below a certain threshold are erased, and hence there is no need to sort the received symbols according to reliability values be- fore erasing as in Forney's GMD decoding. Furthermore, we consider limiting the allowable reliability values to the set R, = u~=mo/2'{1 - 2i/m}, where m = 1,2,3,. . .. This covers the simple cases of taking only hard decisions (m = l), allow- ing erasures (m = 2), or accommodating the full range (0,1) of reliability values as in Forney's GMD decoding (m + 00). Limiting the reliability values may be of importance since, in any digital implementation, the reliability values need to be quantized. Moreover, in some applications, e.g., GMD decod- ing of concatenated codes over discrete channels, the reliabil- ity values are discrete in nature (2). The maximum number of trials is kept as a parameter. Limiting the reliability values and the number of trials leads to the concept of reduced GMD decoding.
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.