Cyclotomic fast Fourier transform

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.