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

被引：30

作者：

Lin, Sian-Jheng ^{[1
]}

Al-Naffouri, Tareq Y. ^{[2
]}

Han, Yunghsiang S. ^{[3
]}

Chung, Wei-Ho ^{[4
]}

机构：

[1] Univ Sci & Technol China, Sch Informat Sci & Technol, CAS Key Lab Electromagnet Space Informat, Hefei 230026, Peoples R China

[2] King Abdullah Univ Sci & Technol, Comp Elect Math Sci & Engn Div, Thuwal 23955, Saudi Arabia

[3] Natl Taiwan Univ Sci & Technol, Dept Elect Engn, Taipei 10607, Taiwan

[4] Acad Sinica, Res Ctr Informat Technol Innovat, Taipei 11529, Taiwan

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2016年 / 62卷 / 11期

关键词：

Fast Fourier transform; polynomial basis; finite field; Reed-Solomon code; INFORMATION DISPERSAL ALGORITHM; FINITE-FIELDS; POWER SPECTRA; EFFICIENT N; WALSH;

D O I：

10.1109/TIT.2016.2608892

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we present a fast Fourier transform 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 = 2(m), 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.

引用

页码：6284 / 6299

页数：16

共 28 条

[1]

Blahut R., 1983, THEORY PRACTICE ERRO, P336

[2] LINEAR FILTERING APPROACH TO COMPUTATION OF DISCRETE FOURIER TRANSFORM [J].