# On a Statistical Algorithm to Decode Heavily Corrupted Linear Codes

- 2 Citations
- 649 Downloads

## Abstract

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.

## Keywords

Maximum Likelihood Method Asymptotic Estimate Linear Code Statistical Algorithm Information Word## Preview

Unable to display preview. Download preview PDF.

## References

- [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]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]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