0.2 Multidimensional index mapping  (Page 5/6)

If a radix-2 FFT is used, the unscrambler is a bit-reversed counter. If a radix-4 FFT is used, the unscrambler is a base-4reversed counter, and similarly for radix-8 and others. However, if for the radix-4 FFT, the short length-4 DFTs (butterflies) have theiroutputs in bit-revered order, the output of the total radix-4 FFT will be in bit-reversed order, not base-4 reversed order. Thismeans any radix- $2^n$ FFT can use the same radix-2 bit-reversed counter as an unscrambler if the proper butterflies are used.

Efficiencies resulting from index mapping with the dft

In this section the reductions in arithmetic in the DFT that result from the index mapping alone will be examined. Inpractical algorithms several methods are always combined, but it is helpful in understanding the effects of a particular method tostudy it alone.

The most general form of an uncoupled two-dimensional DFT is given by

where the inner sum calculates $N_2$ length- $N_1$ DFT's and, if for a type-two map, the effects of the TFs. If the number of arithmeticoperations for a length-N DFT is denoted by $F\left(N\right)$ , the number of operations for this inner sum is $F=N_{2}F\left(N_1\right)$ . The outer sum which gives $N_1$ length- $N_2$ DFT's requires $N_{1}F\left(N_2\right)$ operations. The total number of arithmetic operations is then

The first question to be considered is for a fixed length $N$ , what is the optimal relation of $N_1$ and $N_2$ in the sense of minimizing the required amount of arithmetic. To answer thisquestion, $N1$ and $N_2$ are temporarily assumed to be real variables rather than integers. If the short length- $N_i$ DFT's in [link] and any TF multiplications are assumed to require $N_i^2$ operations, i.e. $F\left(N_i\right)=N_i^2$ , "Efficiencies Resulting from Index Mapping with the DFT" becomes

To find the minimum of $F$ over $N_1$ , the derivative of $F$ with respect to $N_1$ is set to zero (temporarily assuming the variables to be continuous) and the result requires $N_1=N_2$ .

This result is also easily seen from the symmetry of $N_1$ and $N_2$ in $N=N_1{N}_2$ . If a more general model of the arithmetic complexity of the short DFT's is used, the same result is obtained,but a closer examination must be made to assure that $N_1=N_2$ is a global minimum.

If only the effects of the index mapping are to be considered, then the $F\left(N\right)=N^2$ model is used and [link] states that the two factors should be equal. If there are M factors, a similar reasoning shows that all $M$ factors should be equal. For the sequence of length

there are now $M$ length-R DFT's and, since the factors are all equal, the index map must be type two. This means there must betwiddle factors.

In order to simplify the analysis, only the number of multiplications will be considered. If the number of multiplicationsfor a length-R DFT is $F\left(R\right)$ , then the formula for operation counts in [link] generalizes to

for $N_i=R$

This is a very important formula which was derived by Cooley and Tukey in their famous paper [link] on the FFT. It states that for a given R which is called the radix, the number ofmultiplications (and additions) is proportional to $NlnN$ . It also shows the relation to the value of the radix, $R$ .