On the complexity of decoding Goppa codes (Corresp.)
D.V. Sarwate · IEEE Transactions on Information Theory · 1977
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.