# Difference between revisions of "Fast Fourier Transform"

From Hydrogenaudio Knowledgebase

(16 intermediate revisions by 6 users not shown) | |||

Line 1: | Line 1: | ||

− | Fast Fourier | + | '''Fast Fourier transform''' ('''FFT''') is an efficient algorithm for calculating the [[DFT|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 <math>O(n^2)\,</math> computations, FFT takes an order of <math>O(n\,\log\,n)</math>, 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 <math> n = 64,128,256,512,1024,2048</math> 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== | ||

+ | * {{wikipedia|Fast Fourier transform}} | ||

+ | |||

+ | [[Category:Signal Processing]] | ||

+ | [[Category:Technical]] |

## Latest revision as of 13:01, 22 March 2022

**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 computations, FFT takes an order of , 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 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[edit]

- Fast Fourier transform on Wikipedia