Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

On the complexity of minimum distance decoding of long linear codes

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

Published Jul 1, 1999• 43 citations
Publisher

Abstract

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.

DOI
10.1109/18.771141

Related papers

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, 2005•0 citations

Suboptimum decoding of decomposable block codes

T. Takata, Y. Yamashita, Toru Fujiwara +2 more

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length.>

IEEE Transactions on Information Theory•Jan 1, 1994•22 citations

Sort-and-match algorithm for soft-decision decoding

Ilya I. Dumer

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

IEEE Transactions on Information Theory•Jan 1, 1999•13 citations

Generalized minimum distance decoding

G. David Forney

We introduce a new distance measure which permits likelihood information to be used in algebraic minimum distance decoding techniques. We give an efficient decoding algorithm, and develop exponential bounds on the probability of not decoding correctly. In one application, this technique yields the same probability of error as maximum likelihood decoding.

IEEE Transactions on Information Theory•Apr 1, 1966•565 citations

A new approach to the general minimum distance decoding problem: The zero-neighbors algorithm

Lev B. Levitin, Carlos R. P. Hartmann

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.

IEEE Transactions on Information Theory•May 1, 1985•34 citations

Using Linear Programming to Decode Binary Linear Codes

J. Feldman, Martin J. Wainwright, David Ron Karger

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.

IEEE Transactions on Information Theory•Feb 28, 2005•573 citations
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.
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.
To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length.>
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/.
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.
A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.