2. Fourier pöörde numbrilised implementatsioonid

Brief summary

The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2N² to 2Nlog₂N. There are several implementations how to achieve that. Fast Fourier transform algorithms generally fall into two classes: decimation in time, and decimation in frequency.

Kokkuvõte

Kiire Fourier’ teisendus (FFT) on diskreetse Fourier’ teisenduse algoritm, mis põhineb teisenduse teostamiseks vajalike arvutuste mahu vähendamises (vajalik N punkti jaoks alates 2N2 kuni  2Nlog2N). On olemas mitmeid viise, kuidas seda saavutada. Kiire Fourier’ teisenduse algoritmid jagunevad tavaliselt kahte klassi: aja detsimatsioon ja sageduse detsimatsioon.