On the complexity of decoding Goppa codes (Corresp.)
- 1 July 1977
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 23 (4) , 515-516
- https://doi.org/10.1109/tit.1977.1055732
Abstract
It is shown that i) erasures-and-errors decoding of Goppa codes can be done usingO(n \log^{2} n)arithmetic operations, ii) long primitive binary Bose-Chaudhuri-Hocquenghem (BCH) codes can be decoded usingO(n \log n)arithmetic operations, and iii) Justesen's asymptotically good codes can be decoded usingO(n^{2})bit operations. These results are based on the application of efficient computational techniques to the decoding algorithms recently discovered by Sugiyama, Kasahara, Hirasawa, and Namekawa.Keywords
This publication has 10 references indexed in Scilit:
- An erasures-and-errors decoding algorithm for Goppa codes (Corresp.)IEEE Transactions on Information Theory, 1976
- On the complexity of decoding Reed-Solomon codes (Corresp.)IEEE Transactions on Information Theory, 1976
- The algebraic decoding of Goppa codesIEEE Transactions on Information Theory, 1975
- A method for solving key equation for decoding goppa codesInformation and Control, 1975
- Decoding Goppa codes with a BCH decoder (Corresp.)IEEE Transactions on Information Theory, 1975
- Goppa codesIEEE Transactions on Information Theory, 1973
- Fast computation of GCDsPublished by Association for Computing Machinery (ACM) ,1973
- Good self dual codes existDiscrete Mathematics, 1972
- Class of constructive asymptotically good algebraic codesIEEE Transactions on Information Theory, 1972
- Long primitive binary BCH codes have distanced leq 2n ln R^{-1}/log n cdotsIEEE Transactions on Information Theory, 1972