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

Masazumi KURIHARA  Shojiro SAKATA  Kingo KOBAYASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.9   pp.1298-1304
Publication Date: 1996/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
Keyword: 
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)>>
Buy this Article



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 -θ + 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.