Connexions

You are here: Home » Content » Multidimensional Index Maps
Content Actions

Multidimensional Index Maps

Module by: Douglas L. Jones

Multidimensional Index Maps for DIF and DIT algorithms

Decimation-in-time algorithm

Radix-2 DIT: Xk=∑n=0N-1xn W N n k =∑n=0N2-1x2n W N 2 n k +∑n=0N2-1x2n+1 W N ( 2 n + 1 ) k 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 n 1 2 n 2 : n 1 =01 n 1 0 1 : n 2 =012…N2-1 n 2 0 1 2 … N 2 1 Xk=∑n=0N-1xn W N n k =∑ n 1 =01∑ n 2 =0N2-1x n 1 +2 n 2 W N ( n 1 + 2 n 2 ) k 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=N2 k 1 + k 2 k N 2 k 1 k 2 : k 1 =01 k 1 0 1 : k 2 =012…N2-1 k 2 0 1 2 … N 2 1
Note: As long as there is a one-to-one correspondence between the original indices nk=012…N-1 n k 0 1 2 … N 1 and the nn, kk 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 n n 1 2 n 2 , k=N2 k 1 + k 2 k N 2 k 1 k 2 :
Xk=XN2 k 1 + k 2 =∑n=0N-1xn W N n ( N 2 k 2 + k 2 ) =∑ n 1 =01∑ n 2 =0N2-1x n 1 +2 n 2 W N ( n 1 + n 2 ) ( N 2 k 1 + k 2 =∑ n 1 =01∑ n 2 =0N2-1x 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 =01∑ n 2 =0N2-1x 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 =01 W 2 n 1 k 2 W N n 1 k 2 ∑ n 2 =0N21x n 1 n 2 W N 2 n 2 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 (1)
Note: Key to FFT is choosing index map so that one of the cross-terms disappears!
Problem 1
What is an index map for a radix-4 DIT algorithm?
Problem 2
What is an index map for a radix-4 DIF algortihm?
Problem 3
What is an index map for a radix-3 DIT algorithm? (NN a multiple of 3)
For arbitrary composite N= N 1 N 2 N N 1 N 2 , we can define an index map n= n 1 + N 1 n 2 n n 1 N 1 n 2 k= N 2 k 1 + k 2 k N 2 k 1 k 2 n 1 =012… N 1 -1 n 1 0 1 2 … N 1 1 k 1 =012… N 1 -1 k 1 0 1 2 … N 1 1 n 2 =012… N 2 -1 n 2 0 1 2 … N 2 1 k 2 =012… N 2 -1 k 2 0 1 2 … N 2 1
Xk=X k 1 k 2 =∑ n 1 =0 N 1 -1∑ n 2 =0 N 2 -1x 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 =0 N 1 -1∑ n 2 =0 N 2 -1x 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 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 (2)
    Computational cost in multipliesl "Common Factor Algorithm (CFA)"
  • N 1 N 1 length- N 2 N 2 DFTs ⇒ N 1 N 2 2 N 1 N 2 2
  • N N twiddle factors ⇒ N N
  • N 2 N 2 length- N 1 N 1 DFTs ⇒ N 2 N 1 2 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 N 1 N 2 2 N 1 N 2 N 2 N 1 2 N N 1 N 2 1
"Direct": N2=N N 1 N 2 N 2 N N 1 N 2
Example 1 
N 1 =16 N 1 16 N 2 =15 N 2 15 N=240 N 240 direct=2402=57600 direct 240 2 57600 CFA=7680 CFA 7680 Tremendous saving for any composite NN
Pictorial Representations
Emphasizes Multi-dimensional structureimage1.png
Subfigure 1.1
Emphasizes computer memory organizationimage2.png
Subfigure 1.2
Easy to drawimage3.png
Subfigure 1.3
Figure 1: n= n 1 +5 n 2 n n 1 5 n 2 , k=3 k 1 + k 2 k 3 k 1 k 2
Problem 4
Can the composite CFAs be implemented in-place?
Problem 5
What do we do with N= N 1 N 2 N 3 N N 1 N 2 N 3 ?

Comments, questions, feedback, criticisms?

Send feedback