Cyclotomic fast Fourier transform

The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields.  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. 

Background 
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 

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 

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 . 

References 

Category:Discrete transforms
Category:FFT algorithms