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ı: