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

Matrix notation

We denote the $N\times N$ identity matrix with $I_N$ , and diagonal matrices with

The $N\times N$ stride permutation matrix is defined for $N=KM$ by the permutation

for $0\le i<K,0\le j<M$ . This definition shows that $L_M^N$ transposes a $K\times M$ matrix stored in row-major order. Alternatively, we can write

For example ( $·$ means 0),

$L_{N/2}^N$ is sometimes called the perfect shuffle.

Further, we use matrix operators; namely the direct sum

and the Kronecker or tensor product

In particular,

is block-diagonal.

We may also construct a larger matrix as a matrix of matrices, e.g.,

If an algorithm for a transform is given as a product of sparse matrices built from the constructs above, then an algorithm for the transpose orinverse of the transform can be readily derived using mathematical properties including

Permutation matrices are orthogonal, i.e., $P^T=P^{-1}$ . The transposition or inversion of diagonal matrices is obvious.

Radix-2 fft

The DFT decomposes $\mathcal{A}=\mathbb{C}\left[s\right]/(s^N-1)$ with basis $b=(1,s,\cdots ,s^{N-1})$ as shown in [link] . We assume $N=2M$ . Then

factors and we can apply the CRT in the following steps:

As bases in the smaller algebras $\mathbb{C}\left[s\right]/(s^M-1)$ and $\mathbb{C}\left[s\right]/(s^M+1)$ , we choose $c=d=(1,s,\cdots ,s^{M-1})$ . The derivation of an algorithm for ${DFT}_N$ based on [link] - [link] is now completely mechanical by reading off the matrix for each of the threedecomposition steps. The product of these matrices is equal to the ${DFT}_N$ .

First, we derive the base change matrix $B$ corresponding to [link] . To do so, we have to express the base elements $s^n\in b$ in the basis $c\cup d$ ; the coordinate vectors are the columns of $B$ . For $0\le n<M$ , $s^n$ is actually contained in $c$ and $d$ , so the first $M$ columns of $B$ are

where the entries $*$ are determined next. For the base elements $s^{M+n}$ , $0\le n<M$ , we have

which yields the final result

Next, we consider step [link] . $\mathbb{C}\left[s\right]/(s^M-1)$ is decomposed by ${DFT}_M$ and $\mathbb{C}\left[s\right]/(s^M+1)$ by ${DFT\text{-3}}_M$ in [link] .

Finally, the permutation in step [link] is the perfect shuffle $L_M^N$ , which interleaves the even and odd spectral components (even and odd exponents of $W_N$ ).

The final algorithm obtained is

To obtain a better known form, we use ${DFT\text{-3}}_M={DFT}_M{D}_M$ , with $D_M={diag}_{0\le i<M}\left(W_N^i\right)$ , which is evident from [link] . It yields

The last expression is the radix-2 decimation-in-frequency Cooley-Tukey FFT. The corresponding decimation-in-time version isobtained by transposition using [link] and the symmetry of the DFT:

The entries of the diagonal matrix $I_M\oplus D_M$ are commonly called twiddle factors .

The above method for deriving DFT algorithms is used extensively in [link] .

General-radix fft

To algebraically derive the general-radix FFT, we use the decomposition property of $s^N-1$ . Namely, if $N=KM$ then