0.2 Multidimensional index mapping  (Page 3/6)

The left 4-by-4 array is the mapped input data, the center array has the rows transformed, and the right array is the DFTarray. The row DFTs and the column DFTs are independent of each other. The twiddle factors (TF) which are the center $W$ in [link] , are the multiplications which take place on the center array of [link] .

This uncoupling feature reduces the amount of arithmetic required and allows the results of each row DFT to be writtenback over the input data locations, since that input row will not be needed again. This is called “in-place" calculationand it results in a large memory requirement savings.

An example of the type-two map used when the factors of $N$ are relatively prime is given for $N=15$ as

The residue reduction is again not explicitly needed. Although the factors 3 and 5 are relatively prime, use of the type-two mapsets only one of the terms in [link] to zero. The DFT in [link] becomes

which has the same form as [link] , including the existence of the twiddle factors (TF). Here the inner sum is five length-3DFTs, one for each value of $k_1$ . This is illustrated in [link] where the rectangles are the 5 by 3 data arrays and the system is called a ``mixed radix" FFT.

An alternate illustration is shown in [link] where the rectangles are the short length 3 and 5 DFTs.

The type-one map is illustrated next on the same length-15 example. This time the situation of [link] with the “and" condition is used in [link] using an index map of

and

The residue reduction is now necessary. Since the factors of $N$ are relatively prime and the type-one map is being used, both terms in [link] are zero, and [link] becomes

which is similar to [link] , except that now the type-one map gives a pure two-dimensional DFT calculation with no TFs, and thesums can be done in either order. Figures [link] and [link] also describe this case but now there are no Twiddle Factor multiplications in the center and the resulting system is called a ``prime factor algorithm" (PFA).

The purpose of index mapping is to improve the arithmetic efficiency. For example a direct calculation of a length-16 DFTrequires 16^2 or 256 real multiplications (recall, one complex multiplication requires 4 real multiplications and 2 real additions) and an uncoupled version requires 144. A direct calculation of a length-15 DFT requires225 multiplications but with a type-two map only 135 and with a type-one map, 120. Recall one complex multiplication requiresfour real multiplications and two real additions.

Algorithms of practical interest use short DFT's that require fewer than $N^2$ multiplications. For example, length-4 DFTs require no multiplications and, therefore, for the length-16DFT, only the TFs must be calculated. That calculation uses 16 multiplications, many fewer than the 256 or 144 required forthe direct or uncoupled calculation.