On a Class of Byte-Error-Correcting Codes from Algebraic Curves and Their Fast Decoding Algorithm (Special Section on information Theory and Its Applications)

概要

論文の詳細を見る
In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization of the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to ⌊(m + b - 0)/2b⌋ byte-errors for the byte length b, where m + b - θ+ 1≧dG 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 - 0)/2b⌋.0ur byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for random-errors in regard to the number of correcting byte-errors in several cases.
1996-09-25