Brief summary
The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2N2 to 2Nlog2N. 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.
Videoloeng slaididega: http://chuck.ut.ee:8080/ess/echo/presentation/bcc67a6c-0702-407a-ab09-cce510219bad
