On a Statistical Algorithm to Decode Heavily Corrupted Linear Codes

  • I. N. Kovalenko
  • M. N. Savchuk
Part of the International Series in Operations Research & Management Science book series (ISOR, volume 19)


As is well known, decoding general linear codes is an NP-hard problem [1]. Thus, the design of decoding algorithms that have a lower complexity in special cases compared to that of decoding by the maximum likelihood method is of major interest. Levitin and Hartmann [3] present a decoding algorithm having the complexity of order 2 F(ρ)n where F(ρ) is a function of the code rate ρ with F(ρ) < 1 for ρ > 0.1887 and F(ρ) = 1 for ρ ≤ 0.1887. If codes are heavily corrupted (with means that the probability of the distortion of a symbol is not considered as a small variable for large n), the complexity of decoding by this method equals 2 n and coincides with the complexity of the maximum likelihood method. In [2], it is shown that there exists an algorithm to decode heavily corrupted codes with complexity of order.


Maximum Likelihood Method Asymptotic Estimate Linear Code Statistical Algorithm Information Word 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    Berlekamp, E. R., McEliece, R. J., and van Tilborg, H. C. A. On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory IT-24(5), 384–386, May 1987.Google Scholar
  2. [2]
    Kovalenko, I. N. On a subexponential algorithm of decoding heavily corrupted linear codes. Dokl. AN USSR A(10), 16–18, 1998 (Ukrainian and Russian).MathSciNetGoogle Scholar
  3. [3]
    Levitin, L. B., and Hartmann, C. R. P. A new approach to the general minimum distance decoding problem: the zero-neighbors algorithm. IEEE Trans. Inform. Theory IT-31(3), 378–384, May 1985.MathSciNetCrossRefGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • I. N. Kovalenko
  • M. N. Savchuk

There are no affiliations available

Personalised recommendations