0.7 Dft and fft: an algebraic view  (Page 3/5)

As bases, we choose $b=(1,x),c=\left(1\right),d=\left(1\right)$ . $\Delta \left(1\right)=(1,1)$ with the same coordinate vector in $c\cup d=(1,1)$ . Further, because of $x\equiv 1\text{mod}(x-1)$ and $x\equiv -1\text{mod}(x+1)$ , $\Delta \left(x\right)=(x,x)\equiv (1,-1)$ with the same coordinate vector. Thus, $\Delta$ in matrix form is the so-called butterfly matrix, which is a DFT of size 2: ${DFT}_2=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$ .

Polynomial transforms

Assume $P\left(s\right)\in \mathbb{C}\left[s\right]$ has pairwise distinct zeros $\alpha =({\alpha }_0,\cdots ,{\alpha }_{N-1})$ . Then the CRT can be used to completelydecompose $\mathbb{C}\left[s\right]/P\left(s\right)$ into its spectrum :

If we choose a basis $b=(P_0\left(s\right),\cdots ,P_{N-1}\left(s\right))$ in $\mathbb{C}\left[s\right]/P\left(s\right)$ and bases $b_i=\left(1\right)$ in each $\mathbb{C}\left[s\right]/(s-{\alpha }_i)$ , then $\Delta$ , as a linear mapping, is represented by a matrix. The matrix is obtained by mappingevery basis element $P_n$ , $0\le n<N$ , and collecting the results in the columns of the matrix. The result is

and is called the polynomial transform for $\mathcal{A}=\mathbb{C}\left[s\right]/P\left(s\right)$ with basis $b$ .

If, in general, we choose $b_i=\left({\beta }_i\right)$ as spectral basis, then the matrix corresponding to the decomposition [link] is the scaled polynomial transform

where ${diag}_{0\le n<N}\left({\gamma }_n\right)$ denotes a diagonal matrix with diagonal entries ${\gamma }_n$ .

We jointly refer to polynomial transforms, scaled or not, as Fourier transforms.

Dft as a polynomial transform

We show that the ${DFT}_N$ is a polynomial transform for $\mathcal{A}=\mathbb{C}\left[s\right]/(s^N-1)$ with basis $b=(1,s,\cdots ,s^{N-1})$ . Namely,

which means that $\Delta$ takes the form

The associated polynomial transform hence becomes

This interpretation of the DFT has been known at least since [link] , [link] and clarifies the connection between the evaluation points in [link] and the circular convolution in [link] .

In [link] , DFTs of types 1–4 are defined, with type 1 being the standard DFT. In the algebraic framework, type 3 is obtainedby choosing $\mathcal{A}=\mathbb{C}\left[s\right]/(s^N+1)$ as algebra with the same basis as before:

The DFTs of type 2 and 4 are scaled polynomial transforms [link] .

Algebraic derivation of the cooley-tukey fft

Knowing the polynomial algebra underlying the DFT enables us to derive the Cooley-Tukey FFT algebraically . This means that instead of manipulating the DFT definition, we manipulate the polynomial algebra $\mathbb{C}\left[s\right]/(s^N-1)$ . The basic idea is intuitive. We showed that the DFT is the matrix representation of the complete decomposition [link] . The Cooley-Tukey FFT is now derived by performing this decomposition in steps as shown in [link] . Each step yields a sparse matrix; hence, the ${DFT}_N$ is factorized into a product of sparse matrices, which will be the matrix representation ofthe Cooley-Tukey FFT.

This stepwise decomposition can be formulated generically for polynomial transforms [link] , [link] . Here, we consider only the DFT.

We first introduce the matrix notation we will use and in particular the Kronecker product formalism that became mainstream for FFTsin [link] , [link] .

Then we first derive the radix-2 FFT using a factorization of $s^N-1$ . Subsequently, we obtain the general-radix FFT using a decomposition of $s^N-1$ .