Fast Fourier Transforms, Butterfly structure, DIT, DIF

Fast Fourier Transforms, Butterfly structure, DIT, DIF

1. FAST FOURIER TRANSFORM (FFT) P.ANBARASAN ASST. PROFESSOR/ EEE DEPT

2. FFT The FFT is an algorithm that efficiently computes the discrete Fourier transform (DFT) k = 0 to N-1 k = 0 to N-1 Twiddle Factor

3. FFT Radix-2 FFT Algorithm Basic DFT is of size 2 The N point DFT is decimated into 2 point DFT Decimation in Time (DIT) Algorithm Decimation in Frequency (DIF) Algorithm

4. Decimation in Time (DIT-FFT) Breaking x(n) in to its even and odd numbered values, Substitute n=2r for n even and n=2r+1 for n odd, we have

5. Using Symmetry property

6. 4 Point DFT

7. 4 Point DFT Similarly,

8. Two point DFT

9. Flow Graph DIT-FFT N=8

10. Flow Graph DIT-FFT N=8

11. Basic Butterfly Structure

12. Given x(n)={0,1,2,3,4,5,6,7}, find X(k) using DIT FFT algorithm.

13. X(k) = { 28 , -4+j9.656, -4+j4, -4+j1.656, -4, -4-j1.656, -4-j4, -4-j9.656 }

14. Given x(n)={1,2,3,4,4,3,2,1}, find X(k) using DIT FFT algorithm.

15. Decimation in Frequency (DIF-FFT)

16. k=2r and 2r+1

17. Where

18. Flow Graph-First Stage DIF-FFT

19. Where

20. Flow Graph-First Stage DIT-FFT

21. Flow Graph-Second Stage DIT-FFT