IEEE Transactions on Information Theory

Sort-and-match algorithm for soft-decision decoding

Ilya I. Dumer

Published Jan 1, 1999• 13 citations

Abstract

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/.

DOI: 10.1109/18.796373

Related papers

Soft-decision decoding using punctured codes

Ilya I. Dumer

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.

IEEE Transactions on Information TheoryJan 1, 200116 citations

Suboptimal Soft Decision Decoding of Linear Codes

Ilya I. Dumer

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.

IEEE International Symposium on Information Theory (ISIT)Aug 24, 20050 citations

Soft-Decision List Decoding with Linear Complexity for the First-Order Reed-Muller Codes

Ilya I. Dumer, Grigory A. Kabatiansky, Cédric Tavernier

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.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20072 citations

On the complexity of minimum distance decoding of long linear codes

Alexander Barg, Evgenii A. Krouk, Henk C. A. van Tilborg

We suggest a decoding algorithm of q-ary linear codes, which we call supercode decoding. It ensures the error probability that approaches the error probability of minimum-distance decoding as the length of the code grows. For n/spl rarr//spl infin/ the algorithm has the maximum-likelihood performance. The asymptotic complexity of supercode decoding is exponentially smaller than the complexity of all other methods known. The algorithm develops the ideas of covering-set decoding and split syndrome decoding.

IEEE Transactions on Information TheoryJul 1, 199943 citations

Soft-decision list decoding of Reed-Muller codes with linear complexity

Ilya I. Dumer, Grigory A. Kabatiansky, Cédric Tavernier

Let a binary Reed-Muller code RM(s;m) of length n be used on a memoryless channel with an input alphabet ±1 and a real-valued output ℝ. Given a received vector y in ℝn; we define its generalized distance T to any codeword c as the sum Σ|yj|taken over all positions j, in which vectors y, c have opposite signs. We then consider the list ℒTof codewords located within distance T from the received vector y and estimate the size LTof this list using the generalized Johnson bound. For any RM code RM(s,m) of fixed order s, the algorithm is proposed that performs list decoding beyond the error-correcting radius with linear complexity in length n and retrieves the code list ℒTwith complexity of order nsLTfor any decoding radius T within the generalized Johnson bound.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20111 citation

Decoding of linear block codes based on ordered statistics

M.P.C. Fossorier

This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.

Jan 1, 19940 citations