Suboptimal decoding of linear codes in "symmetric" memoryless channels is considered. For the q-ary codes of length n /spl rarr/ /spl infin/ and code rate R the number of decoding operations is upper bounded by the value q/sup n(c+o(1)), where o(1) /spl rarr/ 0 and c = min(R(1 - R), (1 - R)/2). The decoding error probability /spl epsi/ is upper bounded by the double error probability /spl epsi//sub e/ of maximum likelihood (ML) decoding, while /spl epsi/ /spl sim/ /spl epsi//sub e/, when n /spl rarr/ /spl infin/. For the channels with discrete (quantified) output the better estimate c = R(1 - R)/(1 + R) is obtained.
Suboptimal decoding of linear codes in "symmetric" memoryless channels is considered. For the q-ary codes of length n /spl rarr/ /spl infin/ and code rate R the number of decoding operations is upper bounded by the value q/sup n(c+o(1)), where o(1) /spl rarr/ 0 and c = min(R(1 - R), (1 - R)/2). The decoding error probability /spl epsi/ is upper bounded by the double error probability /spl epsi//sub e/ of maximum likelihood (ML) decoding, while /spl epsi/ /spl sim/ /spl epsi//sub e/, when n /spl rarr/ /spl infin/. For the channels with discrete (quantified) output the better estimate c = R(1 - R)/(1 + R) is obtained.
Let a q-ary linear (n, k) code C be used over a memoryless channel. We design a decoding algorithm /spl Psi//sub N/ that splits the received block into two halves in n different ways. First, about /spl radic/N error patterns are found on either half. Then the left- and right-hand lists are sorted out and matched to form codewords. Finally, the most probable codeword is chosen among at most n/spl radic/N codewords obtained in all n trials. The algorithm can be applied to any linear code C and has complexity order of n/sup 3//spl radic/N. For any N/spl ges/q/sup n-k/, the decoding error probability P/sub N/ exceeds at most 1+q/sup n-k//N times the probability P/sub /spl Psi//(C) of maximum-likelihood decoding. For code rates R/spl ges/1/2, the complexity order q/sup n-k/2/ grows as square root of general trellis complexity q/sup min{n-k,k}/. When used on quantized additive white Gaussian noise (AWGN) channels, the algorithm /spl Psi//sub N/ can provide maximum-likelihood decoding for most binary linear codes even when N has an exponential order of q/sup n-k/.
Let a q-ary linear (n,k)-code be used over a memoryless channel. We design a soft-decision decoding algorithm that tries to locate a few most probable error patterns on a shorter length s /spl isin/ [k,n]. First, we take s cyclically consecutive positions starting from any initial point. Then we cut the subinterval of length s into two parts and examine T most plausible error patterns on either part. To obtain codewords of a punctured (s,k)-code, we try to match the syndromes of both parts. Finally, the designed codewords of an (s,k)-code are re-encoded to find the most probable codeword on the full length n. For any long linear code, the decoding error probability of this algorithm can be made arbitrarily close to the probability of its maximum-likelihood (ML) decoding given sufficiently large T. By optimizing s, we prove that this near-ML decoding can be achieved by using only T/spl ap/q/sup (n-k)k/(n+k)/ error patterns. For most long linear codes, this optimization also gives about T re-encoded codewords. As a result, we obtain the lowest complexity order of q/sup (n-k)k/(n+k)/ known to date for near-ML decoding. For codes of rate 1/2, the new bound grows as a cubic root of the general trellis complexity q/sup min{n-k,k}/. For short blocks of length 63, the algorithm reduces the complexity of the trellis design by a few decimal orders.
Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.
An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.
For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.
Or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. F In the analysis of the decoding error probability, it is important to characterize the error exponent, since it indicates how fast the probability of decoding error converges to zero asymptotically. Over a symmetric memoryless channel, an error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, is given. Over a general discrete memoryless channel, the same analysis shows the expected error exponent of an ensemble of coset codes generated by a given linear code.