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

Sian Jheng Lin, Tareq Y. Al-Naffouri, Yunghsiang S. Han

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


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.
Original languageEnglish (US)
Pages (from-to)5343-5358
Number of pages16
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Aug 15 2016


Dive into the research topics of 'FFT Algorithm for Binary Extension Finite Fields and Its Application to Reed–Solomon Codes'. Together they form a unique fingerprint.

Cite this