On a Class of Byte-Error-Correcting Codes from Algebraic Curves and Their Fast Decoding Algorithm

Masazumi KURIHARA, Shojiro SAKATA, Kingo KOBAYASHI

Summary :

In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization on the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to (m + b -θ)/2b byte-errors for the byte length b, where m + b -θ + 1d_G for the Goppa designed distance d_G. This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O (bt(t + q - 1)) with time complexity O (t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O (bt(b + q - 1)) with time complexity O (b(b + q - 1)) and space complexity O (t), where t(m + b -θ)/2b. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for randomerrors in regard to the number of correcting byte-errors in several cases.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.9 pp.1298-1304
• Publication Date: 1996/09/25
• Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
• Category: Coding Theory

Authors

Masazumi KURIHARA
Shojiro SAKATA
Kingo KOBAYASHI

Keyword

byte-error-correcting codes,  algebraic-geometric codes,  fast parallel decoding algorithm,  a set of byte-error locator polynomials,  error-evaluator polynomials