Cooley-Tukey FFT Algoritması

Cooley-Tukey FFT Algoritması J.W. Cooley ve John Tukey tarafından geliştirilen hızlandırılmış fourier dönüşümü algoritmalarından biridir.

\(N\) nokta için DFT şu şekilde tanımlanır:

\(\begin{align*}X_k=\sum_{n=0}^{N-1}x_n\;e^{\frac{-2\pi{j}k}{N}n}\end{align*}\)

Her bir \(k\) değeri için \(N-1\) tane complex çarpma işlemi gerekir. Toplamda \(N\) tane \(k\) değeri hesaplanacağından, DTF'nin bu hali için işlem süresi \(O(N^2)\) olur.

DFT'yi \(n=2m\) ve \(n=2m+1\) olacak şekilde \(2\) parçaya ayıralım.

\(\begin{align*}X_k=\sum_{m=0}^{\frac{N}{2}-1}x_{2m}\;e^{\frac{-2\pi{j}k}{N}2m}+\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1}\;e^{\frac{-2\pi{j}k}{N}(2m+1)}\end{align*}\)

\(\begin{align*}X_k=\sum_{m=0}^{\frac{N}{2}-1}x_{2m}\;e^{\frac{-2\pi{j}k}{N}2m}+\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1}\;e^{\frac{-2\pi{j}k}{N}2m}\;e^{\frac{-2\pi{j}k}{N}}\end{align*}\)

\(\begin{align*}X_k=\underbrace{\sum_{m=0}^{\frac{N}{2}-1}x_{2m}\;e^{\frac{-2\pi{j}k}{N}2m}}_{E_k}+e^{\frac{-2\pi{j}k}{N}}\underbrace{\sum_{m=0}^{\frac{N}{2}-1}x_{2m+1}\;e^{\frac{-2\pi{j}k}{N}2m}}_{O_k}\end{align*}\)

\(\begin{align*}X_k=E_k+e^{\frac{-2\pi{j}k}{N}}O_k\end{align*}\)

Burada \(E_k\) \(x_0,x_2,x_4,\dotsc\) terimlerinin DFT'si, \(O_k\) ise \(x_1,x_3,x_5,\dotsc\) terimlerinin DFT'sidir.

DFT'nin özelliği gereği \(X_k=X_{k+\frac{N}{2}}\) eşitliği vardır:

\(\begin{align*}X_{k+\frac{N}{2}}=E_{k+\frac{N}{2}}+e^{\frac{-2\pi{j}}{N}\big(k+\frac{N}{2}\big)}\;O_{k+\frac{N}{2}}\end{align*}\)

\(\begin{align*}X_{k}=E_{k}+e^{\frac{-2\pi{j}k}{N}}\;e^{-2\pi{j}}\;O_{k}\end{align*}\)

\(\begin{align*}X_{k}=E_{k}-e^{\frac{-2\pi{j}k}{N}}\;O_{k}\end{align*}\)

Burada \(e^{\frac{-2\pi{j}k}{N}}\) ifadesi Twiddle Factor olarak adlandırılır ve \(W_N^k\) şeklinde gösterilir.

\(\begin{align*}X_k=E_k+W_N^k\;O_k\;\;\;,\;\;\;0\leq{k} < \frac{N}{2}\end{align*}\)

\(\begin{align*}X_k=E_k-W_N^k\;O_k\;\;\;,\;\;\;\frac{N}{2}\leq{k} < N\end{align*}\)

\(E_k\) DFT'sini \(m=2p\) ve \(m=2p+1\)'li terimlerini ayrı ayrı hesaplayalım.

\(\begin{align*}E_k=\sum_{p=0}^{\frac{N}{4}-1}x_{4p}\;e^{\frac{-2\pi{j}k}{N}4p}+\sum_{p=0}^{\frac{N}{4}-1}x_{4p+2}\;e^{\frac{-2\pi{j}k}{N}(4p+2)}\end{align*}\)

\(\begin{align*}E_k=\underbrace{\sum_{p=0}^{\frac{N}{4}-1}x_{4p}\;e^{\frac{-2\pi{j}k}{N}4p}}_{EE_k}+e^{\frac{-2\pi{j}2k}{N}}\underbrace{\sum_{p=0}^{\frac{N}{4}-1}x_{4p+2}\;e^{\frac{-2\pi{j}k}{N}4p}}_{EO_k}\end{align*}\)

\(\begin{align*}E_k=EE_k+W_N^{2k}\;EO_k\;\;\;,\;\;\;0\leq{k} < \frac{N}{4}\end{align*}\)

\(\begin{align*}E_k=EE_k-W_N^{2k}\;EO_k\;\;\;,\;\;\;\frac{N}{4}\leq{k} < \frac{N}{2}\end{align*}\)

Aynı şekilde \(O_k\) içinde hesap yaparsak:

\(\begin{align*}O_k=\sum_{p=0}^{\frac{N}{4}-1}x_{4p+1}\;e^{\frac{-2\pi{j}k}{N}4p}+\sum_{p=0}^{\frac{N}{4}-1}x_{4p+3}\;e^{\frac{-2\pi{j}k}{N}(4p+2)}\end{align*}\)

\(\begin{align*}O_k=\underbrace{\sum_{p=0}^{\frac{N}{4}-1}x_{4p+1}\;e^{\frac{-2\pi{j}k}{N}4p}}_{OE_k}+e^{\frac{-2\pi{j}2k}{N}}\underbrace{\sum_{p=0}^{\frac{N}{4}-1}x_{4p+3}\;e^{\frac{-2\pi{j}k}{N}4p}}_{OO_k}\end{align*}\)

\(\begin{align*}O_k=OE_k+W_N^{2k}\;OO_k\;\;\;,\;\;\;0\leq{k} < \frac{N}{4}\end{align*}\)

\(\begin{align*}O_k=OE_k-W_N^{2k}\;OO_k\;\;\;,\;\;\;\frac{N}{4}\leq{k} < \frac{N}{2}\end{align*}\)

Bu işlemleri \(\log_2N\) kere tekrarlarsak:

\(\begin{align*}EE\cdots{E}_k=\sum_{r=0}^{0}x_{qr}\;e^{\frac{-2\pi{j}k}{N}qr}+e^{\frac{-2\pi{j}}{N}\frac{qk}{2}}\sum_{r=0}^{0}x_{qr+\frac{q}{2}}\;e^{\frac{-2\pi{j}k}{N}qr}\end{align*}\)

Toplam sembolünün içerisindeki twiddle factor'ler \(1\)'e eşit olduğundan dolayı \(2\) tane complex çarpma işlemi yok edilmiş olur. Cooley Tukey algorimasının hızlanmasını sağlayan bu terimlerin yok edilmesidir.

\(\begin{align*}EE\cdots{E}_k=x_{qr}+W_N^{\frac{qk}{2}}x_{qr+\frac{q}{2}}\;\;\;,\;\;\;0\leq{k} < 1\end{align*}\)

\(\begin{align*}EE\cdots{E}_k=x_{qr}-W_N^{\frac{qk}{2}}x_{qr+\frac{q}{2}}\;\;\;,\;\;\;1\leq{k} < 2\end{align*}\)

\(N=8\) için Cooley-Tukey Algoritmasının Şematik Gösterimi:

Yukarıdaki şemadan da görüleceği gibi her bir state'de \(N\) adet complex çarpma işlemi yapılır. Toplam state sayısı ise \(\log_2N\)'dir. Bu durumda Cooley-Tukey algoritması ile DFT'nin çalışma süresi \(O(N\log_2N)\)'e düşürülmüş olur.

Normal DFT ile Cooley-Tukey DFT'nin Nokta Sayısı-İşlem Yükü Karşılaştırması:

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir