Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Why and how is FFT faster than DFT?

Status
Not open for further replies.

muralicrl

Full Member level 5
Joined
Feb 6, 2008
Messages
286
Helped
53
Reputation
106
Reaction score
19
Trophy points
1,298
Location
Bangalore
Activity points
2,626
sp question

Hello
Why FFT is faster than DFT?

Regards,
N.Muralidhara
 

Re: sp question

The FFT is just a mathematically efficient method of calculating an DFT. It basically relies on breaking the required calculations into smaller ones that can be done very rapidly. The smallest unit is a 2 point calculation. That is why most FFT implementations require that the number of points being analyzed be equal to a power of 2 (256, 512, 1024, etc.). The number of calculations to implement the DFT equation directly is proportional to N*N, where N is the number of data points. The FFT algorithm reduces this a number proportional to NlogN where the log is to base 2. Since logN increasea at a much lower rate than N, the time saved in using the FFT can be considerable. For example, for N = 1024, the ratio of N/logN is about 100. Thus if a 1024 point DFT takes 100 seconds, the FFT on the same data would only take 1 second.
 
sp question

The FFT ia a FAST ALGORITHM to compute DFT. Rather than compute an N point DFT, where N is a composite number, FFT computes several smaller DFTs and combines the result in a smart manner. This is due to the fact that N can be decomposed as N= N1 N2 ... Nm
 

Re: sp question

Dear Friend,

In addition to what has been said above, the "fastness" of FFT lies in an efficient use of what are called "FFT bins".

Sai
 

Re: sp question

Hi Friend,


In FFT we go in for Butterfly Structure and we also use the bit reversal order so it is faster than that of DFT in which we go for analytical calculations.


Regards,
Avinash.S.
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top