On the Complexity of Decoders for Goppa Codes.
Abstract
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 0(t sq) arithmetic operations. Their algorithms use the extended version of Euclid's algorithm for the greatest common division (GCD) of two polynomials and have the same order of complexity as Berlekamp's 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 0(t log sq t) arithmetic operations. Also, determining the syndrome, the error locations and the error or erasure values all require 0(n log n) arithmetic operations. Thus, for a fixed ratio of t/n, errors-only decoding as well as errors-and-erasures decoding of a Goppa code can be done in 0(n log sq n) arithmetic operations. It is also shown that long primitive binary BCH codes can be decoded in 0(n log n) arithmetic operations. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1976
- Accession Number
- ADA023440
Entities
People
- Dilip V. Sarwate
Organizations
- University of Illinois Urbana–Champaign