Fast Fourier Transform: Difference between revisions
mNo edit summary |
mNo edit summary |
||
| Line 2: | Line 2: | ||
Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform ([[DFT]]). It 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 in terms of computational complexity. The FFT in most implementations consistent of samples that are exactly a power of 2, this is commonly known as a | Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform ([[DFT]]). It 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 in terms of computational complexity. The FFT in most implementations consistent of samples that are exactly a power of 2, this is commonly known as a ''FFT Radix 2'' algorithm where <math> n = 64,128,256,512,1024,2048</math> etc. | ||
[[Category:Signal Processing]] | [[Category:Signal Processing]] | ||
Revision as of 18:09, 25 November 2006
This article is a stub. You can help the Hydrogenaudio Knowledgebase by expanding it.
Fast Fourier Transform is an efficient algorithm for calculating the discrete fourier transform (DFT). It 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 in terms of computational complexity. The FFT in most implementations consistent of samples that are exactly a power of 2, this is commonly known as a FFT Radix 2 algorithm where etc.
