Fast Fourier Transform: Difference between revisions

From Hydrogenaudio Knowledgebase
No edit summary
(<math>-ify the expressions)
Line 1: Line 1:
Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform ([[DFT]]). Reduces the execution time by hundreds in some cases. Whereas [[DFT]] takes an order of o(nĀ²) computations, FFT takes an order of o(n lg n), and is definitely the preferred algorithm to used in all applications. The disadvantage of the FFT is that the number of samples must be exactly a power of 2.
Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform ([[DFT]]). Reduces the execution time by hundreds in some cases. Whereas [[DFT]] takes an order of <math>O(n^2)\,</math> computations, FFT takes an order of <math>O(n\,\log\,n)</math>, and is definitely the preferred algorithm to used in all applications. The disadvantage of the FFT is that the number of samples must be exactly a power of 2.




[[Category:Technical]]
[[Category:Technical]]

Revision as of 07:59, 2 September 2006

Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform (DFT). Reduces the execution time by hundreds in some cases. Whereas DFT takes an order of computations, FFT takes an order of , and is definitely the preferred algorithm to used in all applications. The disadvantage of the FFT is that the number of samples must be exactly a power of 2.