Hizli Fourier Donusumu algoritmasi nasil calisir?

Question

Ingilizce kaynaklarda Fast Fourier Transform adi altinda gecen algoritmanin calisma prensibi nedir?

Answer 1

Hizli Fourier Donusumu algoritmasi Ayrik Fourier Donusumunu $O(n^2)$ den hizli hesaplamak icin kullanilan tum algoritmalarin genel adiymis. Bilgisiyar biliminde acik sorulardan bir tanesi bu donusumu $O(n\log{n})$ den hizli yapabilirmiyiz imis.

Ben Cooley-Tukey algoritmasindan bahsedecegim. Ilginc bir anektod olarak bu algoritmayi Cooley ve Tukeyden 160 sene kadar once Gauss  astreoidlerin yorungesini hesaplamak icin bulmus/kullanmis.

$N$ uzunlugundaki $x_n$ dizisinin Ayrik Fourier Transformasyonu su sekilde veriliyor:

$k \in [0, N-1] \quad X_k = \sum_{n=0}^{N-1}x_n e^{-\frac{2\pi i}{N}nk}$

$X_k$ yi baska bir sekilde ifade edelim.

$X_k = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N}2mk} + \sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N}(2m+1)k}$

$X_k = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N/2}mk} + e^{-\frac{2\pi i}{N}k}\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N/2}mk}$

Dikkatli bakarsaniz toplamanin sagi $x_{2k}$ dizisinin , toplamanin sol tarafi $x_{2k+1}$ dizisinin Ayrik Fourier Donusumu.

$e^{i\cdot}$ nin periyodikliginden yararlanip gosterebiliriz ki

$X_k = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N/2}mk} + e^{-\frac{2\pi i}{N}k}\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N/2}mk}$

$X_{k+\frac{N}{2}} = \sum_{m=0}^{\frac{N}{2}-1}x_{2m} e^{-\frac{2\pi i}{N/2}mk} - e^{-\frac{2\pi i}{N}k}\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1} e^{-\frac{2\pi i}{N/2}mk}$

Bu sekilde ozyinelemeli olarak yazarsak yapacagimiz islem sayisi $O(n^2)$ den $O(n\log{n})$ duser.

Python da yazarsak

def hizli_fourier(x):
    N = len(x)
    if(N <=1):
       return x
    cift = hizli_fourier(x[0::2])
    tek = hizli_fourier(x[1::2])
    T= [ exp(-2j*pi*k/N)*tek[k] for k in range(N//2) ]
    sol = [ cift[k] + T[k] for k in range(N//2)] 
    sag =  [cift[k] - T[k] for k in range(N//2)]
    return sol+sag

 

Duzenleme :

Su soruyu da inceleyebilirsiniz. Verilen cevap matematiksel olarak daha temiz.