An Efficient Interpolation Based Erasure-Only Decoder for High-Rate Reed-Solomon Codes

Qian GUO; Haibin KAN

doi:10.1587/transfun.E95.A.978

An Efficient Interpolation Based Erasure-Only Decoder for High-Rate Reed-Solomon Codes

Qian GUO, Haibin KAN

Full Text Views

0

Share
Cite this

Summary :

In this paper, we derive a simple formula to generate a wide-sense systematic generator matrix(we call it quasi-systematic) B for a Reed-Solomon code. This formula can be utilized to construct an efficient interpolation based erasure-only decoder with time complexity O(n²) and space complexity O(n). Specifically, the decoding algorithm requires 3kr + r² - 2r field additions, kr + r² + r field negations, 2kr + r² - r + k field multiplications and kr + r field inversions. Compared to another interpolation based erasure-only decoding algorithm derived by D.J.J. Versfeld et al., our algorithm is much more efficient for high-rate Reed-Solomon codes.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E95-A No.5 pp.978-981

Publication Date: 2012/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E95.A.978

Type of Manuscript: LETTER

Category: Coding Theory

Cite this

Copy

Qian GUO, Haibin KAN, "An Efficient Interpolation Based Erasure-Only Decoder for High-Rate Reed-Solomon Codes" in IEICE TRANSACTIONS on Fundamentals, vol. E95-A, no. 5, pp. 978-981, May 2012, doi: 10.1587/transfun.E95.A.978.
Abstract: In this paper, we derive a simple formula to generate a wide-sense systematic generator matrix(we call it quasi-systematic) B for a Reed-Solomon code. This formula can be utilized to construct an efficient interpolation based erasure-only decoder with time complexity O(n²) and space complexity O(n). Specifically, the decoding algorithm requires 3kr + r² - 2r field additions, kr + r² + r field negations, 2kr + r² - r + k field multiplications and kr + r field inversions. Compared to another interpolation based erasure-only decoding algorithm derived by D.J.J. Versfeld et al., our algorithm is much more efficient for high-rate Reed-Solomon codes.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E95.A.978/_p

Copy

@ARTICLE{e95-a_5_978,
author={Qian GUO, Haibin KAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Interpolation Based Erasure-Only Decoder for High-Rate Reed-Solomon Codes},
year={2012},
volume={E95-A},
number={5},
pages={978-981},
abstract={In this paper, we derive a simple formula to generate a wide-sense systematic generator matrix(we call it quasi-systematic) B for a Reed-Solomon code. This formula can be utilized to construct an efficient interpolation based erasure-only decoder with time complexity O(n²) and space complexity O(n). Specifically, the decoding algorithm requires 3kr + r² - 2r field additions, kr + r² + r field negations, 2kr + r² - r + k field multiplications and kr + r field inversions. Compared to another interpolation based erasure-only decoding algorithm derived by D.J.J. Versfeld et al., our algorithm is much more efficient for high-rate Reed-Solomon codes.},
keywords={},
doi={10.1587/transfun.E95.A.978},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - An Efficient Interpolation Based Erasure-Only Decoder for High-Rate Reed-Solomon Codes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 978
EP - 981
AU - Qian GUO
AU - Haibin KAN
PY - 2012
DO - 10.1587/transfun.E95.A.978
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E95-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2012
AB - In this paper, we derive a simple formula to generate a wide-sense systematic generator matrix(we call it quasi-systematic) B for a Reed-Solomon code. This formula can be utilized to construct an efficient interpolation based erasure-only decoder with time complexity O(n²) and space complexity O(n). Specifically, the decoding algorithm requires 3kr + r² - 2r field additions, kr + r² + r field negations, 2kr + r² - r + k field multiplications and kr + r field inversions. Compared to another interpolation based erasure-only decoding algorithm derived by D.J.J. Versfeld et al., our algorithm is much more efficient for high-rate Reed-Solomon codes.
ER -