On a Statistical Algorithm to Decode Heavily Corrupted Linear Codes
- 649 Downloads
As is well known, decoding general linear codes is an NP-hard problem . 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  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 , it is shown that there exists an algorithm to decode heavily corrupted codes with complexity of order.
KeywordsMaximum Likelihood Method Asymptotic Estimate Linear Code Statistical Algorithm Information Word
Unable to display preview. Download preview PDF.
- 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