On the Complexity of Decoders for Goppa Codes.
ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB
Pagination or Media Count:
Sugiyama et al. have shown that, for a t-error-correcting Goppa code of block length n, the key equation for errors-only decoding as well as for errors-and-erasures decoding can be solved in 0t sq arithmetic operations. Their algorithms use the extended version of Euclids algorithm for the greatest common division GCD of two polynomials and have the same order of complexity as Berlekamps algorithm for BCH codes. It is shown here that if a more efficient algorithm for computing polynomial GCDs is used, then the key equation can be solved in 0t log sq t arithmetic operations. Also, determining the syndrome, the error locations and the error or erasure values all require 0n log n arithmetic operations. Thus, for a fixed ratio of tn, errors-only decoding as well as errors-and-erasures decoding of a Goppa code can be done in 0n log sq n arithmetic operations. It is also shown that long primitive binary BCH codes can be decoded in 0n log n arithmetic operations. Author
- Computer Programming and Software