Multidimensional Index Maps for DIF and DIT algorithms

Decimation-in-time algorithm Radix-2 DIT: X k n N 1 0 x n W N n k n N 2 1 0 x 2 n W N 2 n k n N 2 1 0 x 2 n 1 W N ( 2 n + 1 ) k Formalization: Let n n 1 2 n 2 : n 1 0 1 : n 2 0 1 2 … N 2 1 X k n N 1 0 x n W N n k n 1 1 0 n 2 N 2 1 0 x n 1 2 n 2 W N ( n 1 + 2 n 2 ) k Also, let k N 2 k 1 k 2 : k 1 0 1 : k 2 0 1 2 … N 2 1 As long as there is a one-to-one correspondence between the original indices n k 0 1 2 … N 1 and the n, k generated by the index map, the computation is the same; only the order in which the sums are done is changed. Rewriting the DFT formula in terms of index map n n 1 2 n 2 , k N 2 k 1 k 2 : X k X N 2 k 1 k 2 n N 1 0 x n W N n ( N 2 k 2 + k 2 ) n 1 1 0 n 2 N 2 1 0 x n 1 2 n 2 W N ( n 1 + n 2 ) ( N 2 k 1 + k 2 n 1 1 0 n 2 N 2 1 0 x n 1 n 2 W N N 2 n 1 k 2 W N n 1 k 2 W N N n 2 k 1 W N 2 n 2 k 2 n 1 1 0 n 2 N 2 1 0 x n 1 n 2 W 2 n 1 k 2 W N n 1 k 2 1 W N 2 n 2 k 2 n 1 1 0 W 2 n 1 k 2 W N n 1 k 2 n 2 N 2 1 0 x n 1 n 2 W N 2 n 2 k 2 Key to FFT is choosing index map so that one of the cross-terms disappears!

What is an index map for a radix-4 DIT algorithm? What is an index map for a radix-4 DIF algortihm? What is an index map for a radix-3 DIT algorithm? (N a multiple of 3) For arbitrary composite N N 1 N 2 , we can define an index map n n 1 N 1 n 2 k N 2 k 1 k 2 n 1 0 1 2 … N 1 1 k 1 0 1 2 … N 1 1 n 2 0 1 2 … N 2 1 k 2 0 1 2 … N 2 1 X k X k 1 k 2 n 1 N 1 1 0 n 2 N 2 1 0 x n 1 n 2 W N N 2 n 1 k 1 W N n 1 k 2 W N N k 1 n 2 W N N 1 n 2 k 2 n 1 N 1 1 0 n 2 N 2 1 0 x n 1 n 2 W N 1 n 1 k 1 W N n 1 k 2 1 W N 2 n 2 k 2 DFT n 1 , N 1 W N n 1 k 2 DFT n 2 , N 2 x n 1 n 2 Computational cost in multipliesl "Common Factor Algorithm (CFA)" N 1 length- N 2 DFTs ⇒ N 1 N 2 2 N twiddle factors ⇒ N N 2 length- N 1 DFTs ⇒ N 2 N 1 2 Total N 1 N 2 2 N 1 N 2 N 2 N 1 2 N N 1 N 2 1 "Direct": N 2 N N 1 N 2 N 1 16 N 2 15 N 240 direct 240 2 57600 CFA 7680 Tremendous saving for any composite N

Pictorial Representations Emphasizes Multi-dimensional structure Emphasizes computer memory organization Easy to draw n n 1 5 n 2 , k 3 k 1 k 2 Can the composite CFAs be implemented in-place? What do we do with N N 1 N 2 N 3 ?