Novel Polynomial Basis with Fast Fourier Transform and Its Application to Reed-Solomon Erasure Codes

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

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

In this paper, we present a fast Fourier transform (FFT) algorithm over extension binary fields, where the polynomial is represented in a non-standard basis. The proposed Fourier-like transform requires O(h lg(h)) field operations, where h is the number of evaluation points. Based on the proposed Fourier-like algorithm, we then develop the encoding/ decoding algorithms for (n = 2m; k) Reed-Solomon erasure codes. The proposed encoding/erasure decoding algorithm requires O(n lg(n)), in both additive and multiplicative complexities. As the complexity leading factor is small, the proposed algorithms are advantageous in practical applications. Finally, the approaches to convert the basis between the monomial basis and the new basis are proposed.
Original languageEnglish (US)
Pages (from-to)6284-6299
Number of pages16
JournalIEEE Transactions on Information Theory
Volume62
Issue number11
DOIs
StatePublished - Sep 13 2016

Fingerprint Dive into the research topics of 'Novel Polynomial Basis with Fast Fourier Transform and Its Application to Reed-Solomon Erasure Codes'. Together they form a unique fingerprint.

Cite this