3.3 Multidimensional index maps

Multidimensional index maps for dif and dit algorithms

Decimation-in-time algorithm

Radix-2 DIT : $$X(k)=\sum_{n=0}^{N-1} x(n)W_N^{nk}=\sum_{n=0}^{\frac{N}{2}-1} x(2n)W_N^{2nk}+\sum_{n=0}^{\frac{N}{2}-1} x(2n+1)W_N^{(2n+1)k}$$ Formalization: Let $n=n_1+2n_2$ : $n_1$

0 1

0 1 2 N 2 1

0 1

0 1 2 N 2 1

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

0 1 2 N 1 1

0 1 2 N 2 1

0 1 2 N 2 1

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$