Fast Fourier Transform

From Hydrogenaudio Knowledgebase
Revision as of 13:01, 22 March 2022 by 36.74.40.190 (Talk)

Jump to: navigation, search

Fast Fourier transform (FFT) is an efficient algorithm for calculating the discrete Fourier transform (DFT). The FFT produces the same results as a DFT but it reduces the execution time by hundreds in some cases. Whereas DFT takes an order of O(n^2)\, computations, FFT takes an order of O(n\,\log\,n), and is definitely the preferred algorithm to be 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  n = 64,128,256,512,1024,2048 etc.

Unlike the DFT, the frequency spacing nor window size per-bin can't be adjusted because FFT bins aren't calculated individually.

External links