<< Chapter < Page Chapter >> Page >

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?

Got questions? Get instant answers now!

What is an index map for a radix-4 DIF algortihm?

Got questions? Get instant answers now!

What is an index map for a radix-3 DIT algorithm? ( N a multiple of 3)

Got questions? Get instant answers now!

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

Got questions? Get instant answers now!

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?

Got questions? Get instant answers now!

What do we do with N N 1 N 2 N 3 ?

Got questions? Get instant answers now!

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The dft, fft, and practical spectral analysis. OpenStax CNX. Feb 22, 2007 Download for free at http://cnx.org/content/col10281/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The dft, fft, and practical spectral analysis' conversation and receive update notifications?

Ask