FFT — Hızlı Fourier Dönüşümü Basitçe Açıklandı

FFT, yani hızlı Fourier dönüşümü, ayrık Fourier dönüşümünü (DFT) hesaplamanın hızlı bir yoludur. Eşit aralıklı örneklerle başlarsanız, DFT bu örneklerde her bir ayrık frekans örüntüsünden ne kadar bulunduğunu söyler.

Önemli nokta şudur: FFT sonucu değiştirmez. Doğrudan formülle aynı DFT değerlerini verir, ama bunu çok daha az tekrarlı işlemle yapar.

FFT Tek Cümlede

FFT, DFT’nin zaten tanımladığı aynı frekans alanı sayılarını hesaplayan daha hızlı bir algoritmadır.

DFT Neyi Ölçer

$x_0, x_1, \dots, x_{N-1}$ örneklerine sahip olduğunuzu varsayalım. DFT, aşağıdaki şekilde tanımlanan $X_0, X_1, \dots, X_{N-1}$ sayılarını üretir:

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

Her $X_k$, verinin bir ayrık frekans örüntüsüyle ne kadar güçlü eşleştiğini ölçer.

Örnekler, örnekleme hızı $f_s$ ile eşit aralıklı alınmışsa, komşu frekans kutuları arasındaki aralık

$$\frac{f_s}{N}$$

olur.

Bu koşul önemlidir. Bilinen bir örnekleme hızı olmadan da DFT kutularınız vardır, ama bunları hertz gibi fiziksel frekanslar olarak etiketleyemezsiniz.

FFT Neden Daha Hızlıdır

FFT, DFT’yi verimli biçimde hesaplayan bir algoritma ailesidir. Temel fikir, neredeyse aynı toplamları sıfırdan yeniden hesaplamak yerine karmaşık üstel çarpanlardaki yapıyı yeniden kullanmaktır.

Gözde canlandırması en kolay sürüm radix-2 FFT’dir. En doğal biçimde $N$, $2$’nin bir kuvveti olduğunda çalışır ve sonuçları birleştirmeden önce bir uzunluk-$N$ dönüşümünü iki uzunluk-$N/2$ dönüşümüne ayırır.

Doğrudan DFT’de aritmetik işlem miktarı $N^2$ mertebesinde büyür. Yaygın FFT yöntemlerinde ise bu yaklaşık $N \log N$ seviyesine düşer.

FFT’lerin pratikte önemli olmasının nedeni bu farktır. Küçük girdilerde iki yöntem de kabul edilebilir görünebilir. Büyük girdilerde ise FFT çok daha hızlıdır.

FFT İşi Nasıl Böler

FFT, her örneği her frekans örüntüsüyle doğrudan karşılaştırmak yerine problemi daha küçük dönüşümlere ayırır, sonra bunları faz çarpanlarıyla yeniden birleştirir.

Standart bir ayrım şöyledir:

1. Çift indeksli örnekleri bir listeye koyun.
2. Tek indeksli örnekleri başka bir listeye koyun.
3. Bu listeler üzerinde daha küçük dönüşümler hesaplayın.
4. İki yarıyı birleştirin.

Bu, frekans analizine uygulanan böl ve yönet yaklaşımıdır.

4 Noktalı FFT Örneği

Şu 4 noktalı sinyali alın:

$$x = [1, 0, 1, 0]$$

Bu örüntü $1$ ile $0$ arasında dönüşümlüdür; bu yüzden tamamen düz bir sonuç yerine bir miktar frekans yapısı bekleriz.

Bunu çift ve tek indekslere ayıralım:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

Çift kısmın 2 noktalı DFT’si

$$E = [2, 0]$$

ve tek kısmın 2 noktalı DFT’si

$$O = [0, 0]$$

olur.

4 noktalı bir FFT için birleştirme adımı şöyledir:

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

burada

$$W_4 = e^{-i 2 \pi / 4}$$

olur.

$O_k = 0$ olduğu için birleştirme özellikle basittir:

$$X = [2, 0, 2, 0]$$

Şimdi sonucu yorumlayalım.

$X_0 = 2$ sıfır frekans terimidir, dolayısıyla örneklerin sıfırdan farklı ortalama değerini yansıtır. $X_2$’deki sıfırdan farklı değer, bu 4 noktalı durumda örüntünün dönüşümlü kısmını yakalar. Önce ortalamayı çıkarırsanız, $X_0$ terimi kaybolur ve dönüşümlü bileşen daha net öne çıkar.

Bu örnek küçüktür, ama fikir ölçeklenir: Her seferinde tüm toplamı yeniden kurmak yerine daha küçük dönüşümleri çözün, sonra bunları birleştirin.

FFT ile İlgili Yaygın Hatalar

FFT ve DFT’yi Farklı Sonuçlar Sanmak

Öyle değildir. FFT, DFT’yi hesaplamanın daha hızlı bir yöntemidir.

Kutuları Fiziksel Frekanslar Olarak Çok Erken Okumak

Kutu konumları ancak örnek aralığı bilindiğinde fiziksel frekanslara dönüşür. Örnekleme hızı $f_s$ ise, eşit aralıklı örneklerde kutu aralığı $f_s/N$ olur.

Sıfır Doldurmanın Yeni Bilgi Eklediğini Sanmak

Sıfır doldurma, alttaki dönüşümü daha ince örneklediği için spektrumu daha pürüzsüz gösterebilir, ama yeni ölçülmüş veri eklemez.

Sinyal Hazırlığını Göz Ardı Etmek

Ortalama çıkarma, pencereleme ve dikkatli örnekleme seçimleri çok önemli olabilir. Bu koşullar göz ardı edilirse, FFT çıktısı verilen örnekler için matematiksel olarak doğru olsa bile yorum açısından yanıltıcı olabilir.

FFT Nerelerde Kullanılır

FFT, örneklenmiş veriden hızlı frekans alanı bilgisine ihtiyaç duyulan her yerde karşımıza çıkar. Yaygın örnekler arasında spektrum analizi, filtreleme, görüntü işleme, titreşim analizi, diferansiyel denklemlerin sayısal çözümü ve hızlı polinom ya da evrişim hesapları bulunur.

Nedeni pratiktir: Birçok işlem, örnek alanından frekans alanına geçtikten sonra daha kolay ya da daha hızlı hale gelir.

Benzer Bir Durumu Deneyin

Bir tam periyot boyunca tek bir sinüs dalgasının eşit aralıklı $8$ örneğini alın ve DFT’yi hesap makinesiyle ya da bir betikle hesaplayın. Sonra sabit bir ofset ekleyin ve yeni çıktıyı karşılaştırın. $X_0$’daki daha güçlü değer, FFT’nin neyi ayırdığını görmenin basit bir yoludur.