TY - JOUR

T1 - FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed–Solomon Codes

AU - Lin, Sian Jheng

AU - Al-Naffouri, Tareq Y.

AU - Han, Yunghsiang S.

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This work was supported in part by the CAS Pioneer Hundred Talents Program and in part by the National Science of Council of Taiwan under Grant NSC 102-2221-E-011-006-MY3 and Grant NSC 101-2221-E -011-069-MY3.

PY - 2016/8/15

Y1 - 2016/8/15

N2 - Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg(n)), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequency-domain decoding algorithms for (n = 2(m), k) systematic Reed-Solomon (RS) codes over F-2m, m is an element of Z(+), with n-k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k)lg(2)(n-k)), improving upon the best currently available decoding complexity O(n lg(2)(n) lg lg(n)), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (2(16), 2(15)) RS code over F-216.

AB - Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg(n)), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequency-domain decoding algorithms for (n = 2(m), k) systematic Reed-Solomon (RS) codes over F-2m, m is an element of Z(+), with n-k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k)lg(2)(n-k)), improving upon the best currently available decoding complexity O(n lg(2)(n) lg lg(n)), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (2(16), 2(15)) RS code over F-216.

UR - http://hdl.handle.net/10754/622547

UR - http://ieeexplore.ieee.org/document/7543456/

UR - http://www.scopus.com/inward/record.url?scp=84988592717&partnerID=8YFLogxK

U2 - 10.1109/TIT.2016.2600417

DO - 10.1109/TIT.2016.2600417

M3 - Article

SN - 0018-9448

VL - 62

SP - 5343

EP - 5358

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 10

ER -