<< Chapter < Page | Chapter >> Page > |
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,\phantom{\rule{4pt}{0ex}}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 ( $\xb7$ 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.
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] .
To algebraically derive the general-radix FFT, we use the decomposition property of ${s}^{N}-1$ . Namely, if $N=KM$ then
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?