For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On a Class of Byte-Error-Correcting Codes from Algebraic Curves and Their Fast Decoding Algorithm
Masazumi KURIHARA Shojiro SAKATA Kingo KOBAYASHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/09/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
byte-error-correcting codes, algebraic-geometric codes, fast parallel decoding algorithm, a set of byte-error locator polynomials, error-evaluator polynomials,
Full Text: PDF(585.8KB)>>
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 -θ + 1dG for the Goppa designed distance dG. 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.