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.