Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined by\min (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared with\min (2^{k},2^{n-k})forn \gg 1and a wide range of code ratesR = k/n. For example, forR \approx 0.5this number grows approximately as a square root of the number of codewords.
Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined by\min (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared with\min (2^{k},2^{n-k})forn \gg 1and a wide range of code ratesR = k/n. For example, forR \approx 0.5this number grows approximately as a square root of the number of codewords.
This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors.
A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated.
A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.
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 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.
Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.
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.
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.