Cyclotomic fast Fourier transform explained

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

GF( 2 ^{m)} , 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

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

\{f _{i\}} ^{N -1} ^{0} over a finite field GF(p^m) is defined asF _{j=\sum} ^{N -1} ^{i =0} f ^{ij} _{i\alpha} , 0 \le j\le N -1 ,

where

\alpha is the N-th primitive root of 1 in GF(p^m). If we define the polynomial representation of \{f _{i\}} ^{N -1} ^{0} asf(x) = f _{0+f} _{1x+f} ^{2+ … + f} ^{N -1} x ^{N-1} = \sum ^{N -1} _{0} f ^{i,} _{ix}

it is easy to see that

F _{j} is simply f(\alpha ^{j)} . That is, the discrete Fourier transform of a sequence converts it to a polynomial evaluation problem.

Written in matrix format,

F = \left[\begin{matrix}F _{0\\F} _{1\ \vdots} \ F _{N-1} \end{matrix}\right] = \left[\begin{matrix} \alpha ^{0&\alpha} ^{0} & … & \alpha ^{0\\ \alpha} ^{0} & \alpha ^{1} & … &\alpha ^{N-1} \\ \vdots &\vdots & \ddots & \vdots \\ \alpha ^{0} & \alpha ^{N-1} & … & \alpha ^{(N-1)(N-1)} \end{matrix}\right] \left[\begin{matrix}f _{0\\f} _{1\\\vdots\\f} _{N-1} \end{matrix}\right] = l{F} f .

Direct evaluation of DFT has an

O(N ^{2)} complexity. Fast Fourier transforms are just efficient algorithms evaluating the above matrix-vector product.

Algorithm

First, we define a linearized polynomial over GF(p^m) as

L(x) = \sum _{i} l _{i} x ^{p ^{i}} , l _{i} \in GF (p ^{m).} L(x) is called linearized because L(x _{1+x} _{2)} = L(x _{1)} + L(x _{2)} , which comes from the fact that for elements x _{1,x} _{2} \in GF (p ^{m),} (x _{1+x} ^{p.} ^{2}

Notice that

p is invertible modulo N because N must divide the order p ^{m-1} of the multiplicative group of the field GF (p ^{m)} . So, the elements \{ 0 , 1 , 2 , \ldots, N -1 \} can be partitioned into l +1 cyclotomic cosets modulo N : \{ 0 \}, \{k _{1,} pk _{1,} p ^{2 k} _{1 ,} \ldots, p ^{m _{1-1}} k _{1\},} \ldots, \{k _{l,} pk _{l,} p ^{2 k} _{l,} \ldots, p ^{m _{l-1}} k _{l\},} where k ^{m _{i}} _{i = p} k _{i} \pmod{N} . Therefore, the input to the Fourier transform can be rewritten as f(x) = \sum ^{l} _{i =0} L ^{k _{i}} _{i(x} ), L _{i(y)} = \sum ^{m _{i-1}} _{t =0} y ^{p ^{t}} f _{p ^{tk} _{i\bmod{N}} }.

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

F _{j} is given by F ^{jk _{i}} _{i(\alpha} ) . Expanding \alpha ^{jk _{i}} \in GF (p ^{m _{i}} ) with the proper basis \{\beta _{i,0} , \beta _{i,1} , \ldots, \beta _{i,m _{i-1}} \} , we have \alpha ^{jk _{i}} = \sum ^{m _{i-1}} _{s =0} a _{ijs} \beta _{i,s} where a _{ijs} \in GF (p) , and by the property of the linearized polynomial L _{i(x)} , we haveF _{j=\sum} ^{m _{i-1}} ^{s =0} a _{ijs} \left(\sum ^{m _{i-1}} _{t =0} \beta ^{p ^{t}} _{i,s} f _{p ^{t} k _{i\bmod{N}} }\right)

This equation can be rewritten in matrix form as

F = AL\Pif , where A is an N x N matrix over GF(p) that contains the elements a _{ijs} , L is a block diagonal matrix, and \Pi is a permutation matrix regrouping the elements in f according to the cyclotomic coset index. \{\gamma ^{p ^{0}} _{i} , \gamma ^{p ^{1}} _{i} , … , \gamma ^{p ^{m _{i-1}}} _{i} \} is used to expand the field elements of GF (p ^{m _{i}} ) , the i-th block of L is given by: L _{i= \begin{bmatrix}} \gamma ^{p ^{0}} _{i} &\gamma ^{p ^{1}} _{i} & … &\gamma ^{p ^{m _{i-1}}} _{i} \\ \gamma ^{p ^{1}} _{i} &\gamma ^{p ^{2}} _{i} & … &\gamma ^{p ^{0}} _{i} \\ \vdots & \vdots & \ddots & \vdots\\ \gamma ^{p ^{m _{i-1}}} _{i} &\gamma ^{p ^{0}} _{i} & … &\gamma ^{p ^{m _{i-2}}} _{i} \\ \end{bmatrix} 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(2^m), the matrix

A is just a binary matrix. Only addition is used when calculating the matrix-vector product of A and L\Pif . It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by O(n( log ^{log _{2 (3)/(2)}} _{2 n)} ) , and the additive complexity is given by O(n ^{2 /( log} _{2} n) ^{log _{2 (8)/(3)}} ) .^[2]

Notes and References

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