Title: Novel FFT over Binary Finite Fields and Its Application to
Reed-Solomon Erasure Codes
Abstract: A fundamental issue in algebra is to reduce the computational complexities of arithmetic operations over polynomials. Many fast polynomial- related algorithms, such as encoding/decoding of Reed-Solomon codes, are based on fast Fourier trans-forms (FFT). However, it is algorithmically harder as the traditional fast Fourier transform (FFT) cannot be applied directly over characteristic-2 finite fields. To the best of our knowledge, no existing algorithm for characteristic-2 finite field FFT/polynomial multiplication has provably achieved O(h log2(h)) operations. In this talk, we present a new basis of polynomial over finite fields of characteristic-2 and then apply it to the encoding/decoding of Reed-Solomon erasure codes. The pro-posed polynomial basis allows that h-point polynomial evaluation can be computed in O(h log2(h)) finite field operations with small leading constant. As compared with the canonical polynomial basis, the proposed basis improves the arithmetic com-plexity of addition, multiplication, and the determination of polynomial degree from O(h log2(h) log2 log2(h)) to O(h log2(h)). Based on this basis, we then develop the encoding and erasure decoding algorithms for the (n = 2^r, k) Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the en-coding can be completed in O(n log2(k)) finite field operations, and the erasure de-coding in O(n log2(n)) finite field operations. To the best of our knowledge, this is the first approach sup- porting Reed-Solomon erasure codes over characteristic-2 finite fields while achieving a complexity of O(n log2(n)), in both additive and multiplica-tive complexities. As the complexity of leading factor is small, the algorithms are advantageous in practical applications.
This work was presented at the 55th Annual Symposium on Foundations
of Computer Science (FOCS 2014).