Cyclotomic fast Fourier transform

The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields.[1] This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over , this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient.[2]

Background

edit

The discrete Fourier transform over finite fields finds widespread application in the decoding of error-correcting codes such as BCH codes and Reed–Solomon codes. Generalized from the complex field, a discrete Fourier transform of a sequence   over a finite field GF(pm) is defined as

 

where   is the N-th primitive root of 1 in GF(pm). If we define the polynomial representation of   as

 

it is easy to see that   is simply  . That is, the discrete Fourier transform of a sequence converts it to a polynomial evaluation problem.

Written in matrix format,

 

Direct evaluation of DFT has an   complexity. Fast Fourier transforms are just efficient algorithms evaluating the above matrix-vector product.

Algorithm

edit

First, we define a linearized polynomial over GF(pm) as

 

  is called linearized because  , which comes from the fact that for elements   

Notice that   is invertible modulo   because   must divide the order   of the multiplicative group of the field  . So, the elements   can be partitioned into   cyclotomic cosets modulo  :

 
 
 
 

where  . Therefore, the input to the Fourier transform can be rewritten as

 

In this way, the polynomial representation is decomposed into a sum of linear polynomials, and hence   is given by

 .

Expanding   with the proper basis  , we have   where  , and by the property of the linearized polynomial  , we have

 

This equation can be rewritten in matrix form as  , where   is an   matrix over GF(p) that contains the elements  ,   is a block diagonal matrix, and   is a permutation matrix regrouping the elements in   according to the cyclotomic coset index.

Note that if the normal basis   is used to expand the field elements of  , the i-th block of   is given by:

 

which is a circulant matrix. It is well known that a circulant matrix-vector product can be efficiently computed by convolutions. Hence we successfully reduce the discrete Fourier transform into short convolutions.

Complexity

edit

When applied to a characteristic-2 field GF(2m), the matrix   is just a binary matrix. Only addition is used when calculating the matrix-vector product of   and  . It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by  , and the additive complexity is given by  .[2]

References

edit
  1. ^ S.V. Fedorenko and P.V. Trifonov, Fedorenko, S. V.; Trifonov, P. V.. (2003). "On Computing the Fast Fourier Transform over Finite Fields" (PDF). Proceedings of International Workshop on Algebraic and Combinatorial Coding Theory: 108–111.
  2. ^ a b Wu, Xuebin; Wang, Ying; Yan, Zhiyuan (2012). "On Algorithms and Complexities of Cyclotomic Fast Fourier Transforms Over Arbitrary Finite Fields". IEEE Transactions on Signal Processing. 60 (3): 1149–1158. doi:10.1109/tsp.2011.2178844.