Basic HTML version of Foils prepared April 22 2000

Foil 17 Recursive Structure for DIT

From Parallel FFT and use in PDE Solvers Computational Science Class CPS615 -- Winter Semester 2000. by Geoffrey C. Fox
The recursive structure of the binary FFT algorithm is a complete binary tree of logN levels shown below for N=16
At each phase, one relates the FFT of M numbers to FFT of even and odd subsets fE fO of this set -- these are of size M/2
Diagram shows binary digit (XXXX) of relevant elements
e.g. XXX1 are all odd indices m; XX11 is set 4m-+3 where m- lies between 0 and 3

© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Mon Apr 24 2000