Cooley-Tukey Decimation in Time Algorithm
Explore the Cooley-Tukey decimation-in-time algorithm for computing the Discrete Fourier Transform efficiently. Understand how the algorithm splits the DFT computation into smaller parts and realize the benefits in terms of reduced number of multiplications. Dive into signal flowgraph notation for a graphical representation of DSP operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Cooley-Tukey decimation-in-time algorithm N = 2 Consider the DFT algorithm for an integer power of 2, N 1 x[n]WNnk= k=0 N 1 x[n]e j2 nk / N; WN=e j2 / N X[k]= k=0 Create separate sums for even and odd values of n: even n odd n nk nk = + [ ] [ W ] [ W ] X k x n x n N N Lettingfor n even and for n odd, we obtain n =2r n =2r+1 N /2 ( ) 1 r=0 ( ) 1 N /2 ( )k x[2r +1]WN2r+1 x[2r]WN2rk+ X[k] = r=0 Carnegie Mellon Slide 1 ECE Department
The Cooley-Tukey decimation in time algorithm Splitting indices in time, we have obtained ( ) ( ) / 2 1 / 2 1 N N = r = r 2 2 k = + + rk rk [ ] 2 [ x ]( ) 2 [ x 1 ]( ) X k r W W r W N N N 0 0 2=e j2 2/ N= e j2 /(N/2)= WN/2 2rkWN k=WN kWN/2 rk But and WN WN So (N/2) 1 (N/2) 1 rk k rk X[k]= +WN x[2r +1]WN /2 x[2r]WN /2 n=0 n=0 N/2-point DFT of x[2r]N/2-point DFT of x[2r+1] Carnegie Mellon Slide 2 ECE Department
Savings so far We have split the DFT computation into two halves: N 1 x[n]WNnk X[k] = k=0 (N/2) 1 (N/2) 1 rk k rk = + WN x[2r +1]WN /2 x[2r]WN /2 n=0 n=0 Have we gained anything? Consider the nominal number of multiplications for N = 8 82=64 Original form produces multiplications 2(42)+8= 40 New form produces multiplications So we re already ahead .. Let s keep going!! Carnegie Mellon Slide 3 ECE Department
Signal flowgraph notation In generalizing this formulation, it is most convenient to adopt a graphic approach Signal flowgraph notation describes the three basic DSP operations: x[n] Addition x[n]+y[n] y[n] a x[n] ax[n] Multiplication by a constant z-1 x[n] x[n-1] Delay Carnegie Mellon Slide 4 ECE Department
Signal flowgraph representation of 8-point DFT kH[k] X[k]= G[k]+WN Recall that the DFT is now of the form The DFT in (partial) flowgraph notation: Carnegie Mellon Slide 5 ECE Department
Continuing with the decomposition So why not break up into additional DFTs? Let s take the upper 4-point DFT and break it up into two 2-point DFTs: Carnegie Mellon Slide 6 ECE Department
The complete decomposition into 2-point DFTs Carnegie Mellon Slide 7 ECE Department
Now lets take a closer look at the 2-point DFT The expression for the 2-point DFT is: 1 x[n]W2 1 x[n]e j2 nk/2 nk= X[k]= n=0 k = 0,1 n=0 Evaluating for we obtain X[0] = x[0]+ x[1] X[1]= x[0]+e j2 1/2x[1]= x[0] x[1] which in signal flowgraph notation looks like ... This topology is referred to as the basic butterfly Carnegie Mellon Slide 8 ECE Department
The complete 8-point decimation-in-time FFT Carnegie Mellon Slide 9 ECE Department
Number of multiplys for N-point FFTs N = 2 where = log2(N) Let (log2(N) columns)(N/2 butterflys/column)(2 mults/butterfly) or ~ multiplys Nlog2(N) Carnegie Mellon Slide 10 ECE Department
Comparing processing with and without FFTs Slow DFT requires N mults; FFT requires N log2(N) mults Filtering using FFTs requires 3(N log2(N))+2N mults Let 1= Nlog2(N)/ N2; 2=[3(Nlog2(N))+ N]/ N2 2 .8124 1 .25 N Note: 1024-point FFT Accomplishes a speedup of ~100 16 32 .50 .156 for filtering~ 30 64 .297 .0935 128 .171 .055 256 .097 .031 1024 .0302 .0097 Carnegie Mellon Slide 11 ECE Department
Additional timesavers: reducing multiplications in the basic butterfly As we derived it, the basic butterfly is of the form r WN r+N /2 WN N /2= 1 Since we can reducing computation by 2 by premultiplying by WN WN r 1 Carnegie Mellon r 1 Slide 12 WN ECE Department
