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

Masazumi KURIHARA; Shojiro SAKATA; Kingo KOBAYASHI

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

Masazumi KURIHARA, Shojiro SAKATA, Kingo KOBAYASHI

Full Text Views

0

Cite this

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

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category: Coding Theory

Cite this

Copy

Masazumi KURIHARA, Shojiro SAKATA, Kingo KOBAYASHI, "On a Class of Byte-Error-Correcting Codes from Algebraic Curves and Their Fast Decoding Algorithm" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 9, pp. 1298-1304, September 1996, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_9_1298/_p

Copy

@ARTICLE{e79-a_9_1298,
author={Masazumi KURIHARA, Shojiro SAKATA, Kingo KOBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On a Class of Byte-Error-Correcting Codes from Algebraic Curves and Their Fast Decoding Algorithm},
year={1996},
volume={E79-A},
number={9},
pages={1298-1304},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - On a Class of Byte-Error-Correcting Codes from Algebraic Curves and Their Fast Decoding Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1298
EP - 1304
AU - Masazumi KURIHARA
AU - Shojiro SAKATA
AU - Kingo KOBAYASHI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1996
AB - 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.
ER -