Fast Fourier Transform
Hızlı Fourier dönüşümü (Fast Fourier Transform) — Ayrık Fourier Dönüşümü'nü doğrudan O(N²) hesaplamak yerine yapısal simetrilerden yararlanarak tipik olarak O(N log N) maliyetle hesaplayan algoritma ailesi.
DFT ile FFT Aynı Şey Değildir
DFT matematiksel dönüşümdür; FFT ise DFT sonucunu daha az işlemle hesaplayan algoritma ailesidir. En bilinen Cooley-Tukey yaklaşımı problemi daha küçük dönüşümlere ayırır.
Uygun boyutlarda doğrudan O(N²) DFT yerine yaklaşık O(N log N) işlem maliyeti elde edilebilir.
Sinyal Analizinde Kullanım
Ses ve titreşim analizinde FFT, zaman alanındaki örnekleri frekans bileşenleri açısından incelemek için kullanılır. Ancak sonucun anlamı pencereleme, örnekleme hızı ve frame uzunluğuna bağlıdır.
FFT bin'i doğrudan "gerçek frekansın kendisi" değildir; frekans çözünürlüğü örnekleme hızı ve dönüşüm boyutuyla belirlenir.
Gerçek Zaman Maliyeti
Uzun FFT daha iyi frekans çözünürlüğü sağlayabilirken frame'in tamamlanmasını beklemek ve daha fazla hesaplama yapmak latency'yi artırabilir.