Hızlı Fourier Dönüşümü (FFT): Modern Bilgisayar Çağının En Değerli Algoritması

"1 milyon sayıyı saniyeler içinde dönüştür"

Bir müzik dosyası saniyede 44,100 örnek içerir. 1 saatlik bir şarkı: 158 milyon sayı. Bu sayıları frekans bileşenlerine ayırmak için Fourier dönüşümü uygulanmalı.

Naif Fourier hesabı $n$ örnek için $O(n^2)$ zaman alır. 158 milyon örnek için: $\sim 2.5 \times 10^{16}$ işlem. Modern CPU bunu yıllarla ölçer. Müzik dinleyemezdik.

FFT (Fast Fourier Transform) aynı işlemi $O(n \log n)$ zamanda yapar. 158 milyon örnek için: $\sim 4 \times 10^9$ işlem. Modern CPU bunu saniyelerle ölçer. 40 milyon kat hızlanma.

FFT nedir?

Ayrık Fourier Dönüşümü (DFT) bir sayı dizisini frekans bileşenlerine ayırır:

$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-2\pi i k n / N}$

Bu formül her $k$ için $N$ çarpma; toplam $N^2$ işlem.

FFT aynı sonucu çok daha az işlemle hesaplar. Anahtar fikir: böl-ve-fethet. $N$'yi 2'ye böl, alt parçalar üzerinde DFT hesapla, sonra birleştir:

$X_k = X_k^{(\text{çift})} + e^{-2\pi i k/N} X_k^{(\text{tek})}$

Bu özyineleme $N = 2^m$ için sonuçta $N \log_2 N$ işleme indirir.

1965: Cooley-Tukey algoritması

James Cooley (IBM) ve John Tukey (Princeton) 1965'te "An Algorithm for the Machine Calculation of Complex Fourier Series" makalesini yayımladı. FFT modern formu doğdu.

Anekdot: Tukey 1963'te Başkan Kennedy'nin bilim danışmanı olarak çalışırken, nükleer test izleme sorununu düşünüyordu. Sismik verilerden nükleer patlamaları tespit etmek için çok büyük Fourier dönüşümleri gerekiyordu — naif yöntemle imkânsız.

Tukey bir toplantıda fikrini özetledi. Cooley implementasyonu kodladı. Sonuç tarihi.

Aslında Gauss önce buldu (1805)

İlginç bir tarihsel ironi: Carl Friedrich Gauss 1805'te yayımlamadığı not defterinde aynı algoritmayı zaten geliştirmişti. Asteroid yörünge hesabı için. Notları ölümünden sonra yayımlandı ama dikkat çekmedi.

Cooley ve Tukey kendi kanıtlarını bağımsız geliştirdiler. Gauss'un öncülüğü ancak 1980'lerde tarihçiler tarafından fark edildi.

Yine "yayımlayan kazanır" kuralı: Gauss buldu ama yaygınlaştırmadı; Cooley-Tukey 1965'te yayımladı, FFT onların adıyla anılıyor.

Hız farkının pratik etkisi

$n$ (örnek)	$n^2$ (naif)	$n \log n$ (FFT)	Oran
$1024$	$\sim 10^6$	$10^4$	100×
$10^6$	$10^{12}$	$2 \times 10^7$	50,000×
$10^9$	$10^{18}$	$3 \times 10^{10}$	33 milyon×

Modern teknoloji bu hız sıçramasıyla mümkün.

Pratik uygulamalar

FFT olmadan modern dijital dünya mümkün olmazdı:

1) Ses sıkıştırma (MP3, AAC)

Ses dosyalarını dalga bileşenlerine ayır; insan kulağının duymadığı frekansları at; geriye kalanı sıkıştır. MP3 %90 sıkıştırma sağlar.

2) Görüntü sıkıştırma (JPEG)

Görüntüyü 8×8 bloklara böl; her bloka 2-boyutlu FFT (aslında DCT — discrete cosine transform, FFT'nin akrabası); önemsiz yüksek-frekansları at; sıkıştır.

3) Video sıkıştırma (MPEG, H.264, HEVC)

Video çerçevelerini frekans bileşenlerine ayır; zaman üzerinden değişimleri sıkıştır. Modern streaming'in (Netflix, YouTube) temeli.

4) MRI ve CT taramaları

Tıbbi görüntüleme verisi frekans uzayında elde edilir. FFT ile pratik zamanda 3D anatomik görüntü oluşturur.

5) 5G ve modern iletişim

OFDM (Orthogonal Frequency Division Multiplexing) modülasyonu FFT'ye dayanır. WiFi, 4G, 5G — hepsi FFT kullanır.

6) Radar ve sonar

Sinyal işleme, hedef tespiti, Doppler analizi.

7) Hisse senedi analizi

Fiyat zaman serilerinde gizli frekansları bulma; trading algoritmalarında.

8) Astronomi

Sinyal-gürültü oranı düşük gözlemlerden periyodik sinyaller çıkarma (egzo gezegen tespiti, pulsar arayışı).

9) Sayısal hesaplama

Konvolüsyon işlemi FFT ile çok hızlanır. Modern derin öğrenme konvolüsyonel sinir ağları (CNN) bu sayede pratiktir.

10) Müzik notasyonu

Akustik enstrümanların frekans tanıma ve otomatik nota üretme.

"Yüzyılın algoritması"

SIAM (Society for Industrial and Applied Mathematics) 2000'de "20. yüzyılın en önemli 10 algoritması" listesini yayımladı. FFT birinci sırada. Eleştirmen şöyle yazdı:

"FFT olmadan modern bilgisayar uygulamalarının çoğu kalıcı olarak yavaş kalırdı."

Aynı yıl Cooley ve Tukey IEEE Centennial Medal kazandı.

Cooley-Tukey: detay bakış

Cooley-Tukey algoritmasının özü: DFT'nin yapısal düzenliliği'ni kullanmak.

Bir $N$-noktalı DFT, iki adet $N/2$-noktalı DFT ile yapılabilir:

• Çift indeksli örnekler için bir DFT.
• Tek indeksli örnekler için bir DFT.
• Twiddle factors ($e^{-2\pi i k/N}$) ile birleştir.

Bu özyineleme $N = 2^m$ için ideal. Diğer $N$ değerleri için mixed-radix veya Bluestein algoritmaları var.

Kütüphaneler

Modern FFT implementasyonları:

• FFTW ("Fastest Fourier Transform in the West") - MIT'de geliştirildi, dünyanın en hızlı genel FFT kütüphanesi.
• CuFFT - NVIDIA GPU için.
• Intel MKL - Intel CPU için optimize.
• numpy.fft (Python) - genel amaçlı.

Bu kütüphaneler donanım-spesifik optimize edilmiştir; mühendisler genellikle "kendi FFT'lerini yazmaz", bunlardan birini kullanır.

"Saklı tetik"

FFT modern dijital dünyanın görünmeyen tetikçisi'dir. Bir telefon görüşmesinin temizlenmesi, bir müziğin sıkıştırılması, bir MRI taramasının yapılması, bir WiFi sinyalinin alınması — hepsinde FFT çalışıyor.

Tukey'in 1963'te nükleer test izleme için aklına gelen fikir, 60 yıl sonra dünyamızı dönüştürdü. 40 milyon kat hızlanma, modern teknoloji devriminin matematiksel kalbidir.

Bir algoritma, bir devrim. FFT olmadan dijital dünya olmazdı.