A Fourier-transzformáció gyakran felbukkan a fizikában és a matematikában, ami azt is jelenti, hogy a mindennapi életben is sokfelé használják.
Röviden, a Fourier-transzformáció egy bemeneti jelet, amely gyakran idő- vagy tértartományban van, átalakít a frekvenciatartományba.
Konkrétabban, ha a bemeneti jel különböző frekvenciák keverékéből (azaz szuperpozíciójából) áll, a transzformáció különválasztja az egyes frekvenciákat, és megmutatja a relatív erősségüket.
Ez a transzformációt a jelfeldolgozás (például szűrés, tömörítés stb.) és számos adattudományi alkalmazás egyik fő eszközévé teszi.
Ezért talán szélesebb körben használják, mint azt elsőre gondolnánk, ami egyben kiváló példa is arra, ahol a képzetes számok nélkülözhetetlenné válnak, tekintve, hogy a Fourier-transzformáció kimenete általában komplex szám.
Bár a Fourier-transzformációnak van integrálos alakja, mi digitálisak vagyunk, ezért a diszkrét változat érdekel minket.
A transzformáció levezetése meghaladja ennek a feladatnak a kereteit, de az előremenő diszkrét transzformáció (a frekvenciatartományba) a következő alakot ölti:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Itt az összegzés n felett fut, N a minták száma, k a frekvencia, i a képzetes egység, xₙ pedig egyetlen minta.
Bár rendkívül hasznos, a Fourier-transzformáció naiv megvalósítása kissé lassú (O(n²)).
A gyors Fourier-transzformáció (FFT) egy olyan algoritmus, amely jelentősen felgyorsítja ezt.
Ez általában egy oszd meg és uralkodj stratégián keresztül történik, amely kihasználja a formulában rejlő szimmetriákat, és aszimptotikusan O(Nlog(N)) komplexitást eredményez.
Ez a gyorsítás nagymértékben javítja a transzformáció gyakorlati használhatóságát és a rá alkalmas alkalmazások körét.
