FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE) PDF Download

UNIT:  III, FFT(Fast frequency transform)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)   0 ≤K ≤ N - 1

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

  • Direct evaluation of X(k) requires N 2 complex multiplications and N(N-1) complex additions.
  • 4 N2 real multiplications 
  • { 4(N-1) + 2} N = N(4N-2) real additions
  • The direct evaluation of DFT is basically inefficient because it does not use the symmetry
  •  & periodicity properties  FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

DITFFT:

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Although k=0 to N-1, each of the sums are computed only for k=0 to N/2 -1, since Xe(k) & Xo(k) are periodic in k with period N/2

For K≥ N/2  FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

X(k) for K≥N/2

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

N = 8

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

X(0) & X(4) having same i/ps with opposite signs

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE) (0 to 1)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

For N=8

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Where Xee(k) is the 2 point DFT of even no. of xe(n) & Xeo(k) is the 2 point DFT of odd no. of xe(n)

Similarly, the sequence xo(n) can be divided in to even & odd numbered sequences as 

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Xoe(k) is the 2-pt DFT of even-numbered of xo(n)

Xoo(k) is the 2-pt DFT of odd-numbered of xo(n)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

No. of StagesNo. of points NNo. of Complex MultiplicationsSpeed Improvement Factor:
  Direct N2FFT   FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)
241644
3864125.33
416256328
53210248012.8
664409619221.33

For N=8

No of stages given by= Log2N = Log28 = 3.

No. of 2 i/p sets = 2( Log 2N  -1 ) = 4

Total No. of Complex additions using DITFFT is  NLog2N

= 8 * 3 =24

Each stage no. of butterflies in the stage= 2m-q where q = stage no. and N=2m Each butterfly operates on one pair of samples and involves two complex additions and one complex multiplication. No. of butterflies in each stage N/2

DITFFT: ( different representation) (u can follow any one) ( both representations are 
correct

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE) k= 0 to N/2 -1 =  0 to 3

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE) k = N/2 to N-1 = 4 to 7

2 pt DFT

  FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Xee(0) = x(0)+x(4)

Xee(1) = x(0)-x(4)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Other way of representation

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

DIFFFT:

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE) put n’ = n+N/2

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Let f(n) = x(n) + x(n+N/2)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

N=8

f(0) = x(0) + x(4)

f(1) = x(1) + x(5)

f(2) = x(2) + x(6)

f(3) = x(3) + x(7)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

X(4k) = f(0) + f(2) + [ f(1) + f(3) ] FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

X(4k+2) = f(0) – f(2) + { [ f(1) – f(3) ]  FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

X(0) = f(0) + f(2) + f(1) + f(3)

X(4) = f(0) + f(2) – [ f(1) + f(3) ]

X(2) = f(0) - f(2) + [ f(1) - f(3)] W82

X(6) = f(0) - f(2) - [ f(1) - f(3)]W82

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

Find the IDFT using DIFFFT

X(k) = { 4,  1-j 2.414,  0,  1-j 0.414,  0,  1+j 0.414,  0,  1+j 2.414 }

Out put 8x*(n) is in bit reversal order x(n) = { 1,1,1,1,0,0,0,0}

The document FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE) is a part of the Electronics and Communication Engineering (ECE) Course Signals and Systems.
All you need of Electronics and Communication Engineering (ECE) at this link: Electronics and Communication Engineering (ECE)
32 videos|76 docs|63 tests

Top Courses for Electronics and Communication Engineering (ECE)

FAQs on FFT (Fast Frequency Transform) - Signals and Systems - Electronics and Communication Engineering (ECE)

1. What is FFT and how does it work?
Ans. FFT stands for Fast Fourier Transform. It is an algorithm used to efficiently compute the Discrete Fourier Transform (DFT) of a sequence or signal. The FFT breaks down a signal into its frequency components, allowing us to analyze its spectral content. It works by recursively dividing the DFT into smaller DFTs, reducing the computational complexity from O(n^2) to O(n log n).
2. What are the main applications of FFT?
Ans. FFT has various applications in different fields. Some common applications include signal processing, image processing, audio compression, speech recognition, data analysis, and solving differential equations. It is widely used in fields such as telecommunications, astronomy, medical imaging, and radar systems.
3. How does FFT improve computational efficiency?
Ans. FFT significantly improves computational efficiency compared to the naive DFT algorithm. The key factor is the divide-and-conquer approach used in FFT. By recursively breaking down the DFT into smaller DFTs, the number of computations required is reduced from O(n^2) to O(n log n). This makes it much faster and more practical for analyzing large data sets or real-time processing.
4. Can FFT be used for non-periodic signals?
Ans. Yes, FFT can be used for non-periodic signals as well. Although FFT assumes periodicity in the signal, non-periodic signals can still be analyzed by applying windowing techniques. Windowing involves multiplying the signal with a window function that gradually reduces the amplitude towards the signal edges. This helps to minimize spectral leakage and allows FFT to be applied effectively to non-periodic signals.
5. Are there any limitations or drawbacks of using FFT?
Ans. While FFT is a powerful tool, it does have some limitations. One limitation is the assumption of a stationary signal, meaning that the signal characteristics should not change significantly during the analysis. If the signal is non-stationary, other techniques like the Short-Time Fourier Transform (STFT) may be more appropriate. Additionally, FFT assumes that the signal is discrete and evenly sampled. If the signal is continuous or irregularly sampled, suitable pre-processing techniques need to be applied before using FFT.
32 videos|76 docs|63 tests
Download as PDF
Explore Courses for Electronics and Communication Engineering (ECE) exam

Top Courses for Electronics and Communication Engineering (ECE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Sample Paper

,

video lectures

,

practice quizzes

,

MCQs

,

shortcuts and tricks

,

mock tests for examination

,

Previous Year Questions with Solutions

,

Exam

,

Summary

,

Semester Notes

,

study material

,

Objective type Questions

,

pdf

,

Viva Questions

,

past year papers

,

Free

,

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

,

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

,

Extra Questions

,

Important questions

,

FFT (Fast Frequency Transform) | Signals and Systems - Electronics and Communication Engineering (ECE)

,

ppt

;