クーリー–テューキー型の周波数間引き（Decimation-In-Frequency, DIF）FFTとは、以降に示す手法で行われるFFTのことです。
クーリー–テューキー型の周波数間引きFFTは、離散時間信号の要素数\(N\)は、2の累乗である必要があります。
また、クーリー–テューキー型の周波数間引きFFTでは、回転因子を用いた掛け算の回数が\(\displaystyle\frac{N}{2}\log_2 N\)回です。
\(N=8\)の場合のクーリー–テューキー型の周波数間引きFFTの手法を説明します。
まず、\(N=8\)の離散フーリエ変換は、回転因子を用いて、以下のように表せます。
\[X[k] = \sum_{n=0}^{7} x[n] W_8^{kn}\]
\(X[0]\sim X[7]\)は、行列の掛け算を利用して、以下のように表せます。
\[\begin{pmatrix} X[0] \\ X[1] \\ X[2] \\ X[3] \\ X[4] \\ X[5] \\ X[6] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^1 & W_8^2 & W_8^3 & W_8^4 & W_8^5 & W_8^6 & W_8^7 \\ W_8^0 & W_8^2 & W_8^4 & W_8^6 & W_8^8 & W_8^{10} & W_8^{12} & W_8^{14} \\ W_8^0 & W_8^3 & W_8^6 & W_8^9 & W_8^{12} & W_8^{15} & W_8^{18} & W_8^{21} \\ W_8^0 & W_8^4 & W_8^8 & W_8^{12} & W_8^{16} & W_8^{20} & W_8^{24} & W_8^{28} \\ W_8^0 & W_8^5 & W_8^{10} & W_8^{15} & W_8^{20} & W_8^{25} & W_8^{30} & W_8^{35} \\ W_8^0 & W_8^6 & W_8^{12} & W_8^{18} & W_8^{24} & W_8^{30} & W_8^{36} & W_8^{42} \\ W_8^0 & W_8^7 & W_8^{14} & W_8^{21} & W_8^{28} & W_8^{35} & W_8^{42} & W_8^{49} \\ \end{pmatrix}\begin{pmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \\ x[4] \\ x[5] \\ x[6] \\ x[7] \\ \end{pmatrix}\]
回転因子の周期性を利用して、以下のように変形します。
\[\begin{pmatrix} X[0] \\ X[1] \\ X[2] \\ X[3] \\ X[4] \\ X[5] \\ X[6] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^1 & W_8^2 & W_8^3 & W_8^4 & W_8^5 & W_8^6 & W_8^7 \\ W_8^0 & W_8^2 & W_8^4 & W_8^6 & W_8^0 & W_8^{2} & W_8^{4} & W_8^{6} \\ W_8^0 & W_8^3 & W_8^6 & W_8^1 & W_8^{4} & W_8^{7} & W_8^{2} & W_8^{5} \\ W_8^0 & W_8^4 & W_8^0 & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} \\ W_8^0 & W_8^5 & W_8^{2} & W_8^{7} & W_8^{4} & W_8^{1} & W_8^{6} & W_8^{3} \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} & W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2} \\ W_8^0 & W_8^7 & W_8^{6} & W_8^{5} & W_8^{4} & W_8^{3} & W_8^{2} & W_8^{1} \\ \end{pmatrix}\begin{pmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \\ x[4] \\ x[5] \\ x[6] \\ x[7] \\ \end{pmatrix}\]
行列を奇数行と偶数行に分けます。これが周波数を間引く操作です。
【奇数行】
\[\begin{pmatrix} X[0] \\ X[2] \\ X[4] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^2 & W_8^4 & W_8^6 & W_8^0 & W_8^{2} & W_8^{4} & W_8^{6} \\ W_8^0 & W_8^4 & W_8^0 & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} & W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2} \\ \end{pmatrix}\begin{pmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \\ x[4] \\ x[5] \\ x[6] \\ x[7] \\ \end{pmatrix}\]
【偶数行】
\[\begin{pmatrix} X[1] \\ X[3] \\ X[5] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^1 & W_8^2 & W_8^3 & W_8^4 & W_8^5 & W_8^6 & W_8^7 \\ W_8^0 & W_8^3 & W_8^6 & W_8^1 & W_8^{4} & W_8^{7} & W_8^{2} & W_8^{5} \\ W_8^0 & W_8^5 & W_8^{2} & W_8^{7} & W_8^{4} & W_8^{1} & W_8^{6} & W_8^{3} \\ W_8^0 & W_8^7 & W_8^{6} & W_8^{5} & W_8^{4} & W_8^{3} & W_8^{2} & W_8^{1} \\ \end{pmatrix}\begin{pmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \\ x[4] \\ x[5] \\ x[6] \\ x[7] \\ \end{pmatrix}\]
これらの行列を整理していきます。まず、奇数行を以下のように変形します。
\[\begin{pmatrix} X[0] \\ X[2] \\ X[4] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^2 & W_8^4 & W_8^6 \\ W_8^0 & W_8^4 & W_8^0 & W_8^{4} \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] \\ x[1] + x[5] \\ x[2] + x[6] \\ x[3] + x[7] \\ \end{pmatrix}\]
偶数行は、回転因子の対称性を利用して、以下のように変形します。
\[\begin{pmatrix} X[1] \\ X[3] \\ X[5] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^1 & W_8^2 & W_8^3 & -W_8^0 & -W_8^1 & -W_8^2 & -W_8^3 \\ W_8^0 & W_8^3 & W_8^6 & W_8^1 & -W_8^{0} & -W_8^{3} & -W_8^{6} & -W_8^{1} \\ W_8^0 & W_8^5 & W_8^{2} & W_8^{7} & -W_8^{0} & -W_8^{5} & -W_8^{2} & -W_8^{7} \\ W_8^0 & W_8^7 & W_8^{6} & W_8^{5} & -W_8^{0} & -W_8^{7} & -W_8^{6} & -W_8^{5} \\ \end{pmatrix}\begin{pmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \\ x[4] \\ x[5] \\ x[6] \\ x[7] \\ \end{pmatrix}\]
偶数行をさらに以下のように変形します。
\[\begin{pmatrix} X[1] \\ X[3] \\ X[5] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^1 & W_8^2 & W_8^3 \\ W_8^0 & W_8^3 & W_8^6 & W_8^1 \\ W_8^0 & W_8^5 & W_8^{2} & W_8^{7} \\ W_8^0 & W_8^7 & W_8^{6} & W_8^{5} \\ \end{pmatrix}\begin{pmatrix} x[0] - x[4]\\ x[1] - x[5] \\ x[2] - x[6] \\ x[3] - x[7] \\ \end{pmatrix}\]
指数法則を利用して、偶数行を以下のように変形します。
\[\begin{pmatrix} X[1] \\ X[3] \\ X[5] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 W_8^0 & W_8^0 W_8^1 & W_8^0 W_8^2 & W_8^0 W_8^3 \\ W_8^0 W_8^0 & W_8^2 W_8^1 & W_8^4 W_8^2 & W_8^{6} W_8^3 \\ W_8^0 W_8^0 & W_8^4 W_8^1 & W_8^{0} W_8^2 & W_8^{4} W_8^3 \\ W_8^0 W_8^0 & W_8^6 W_8^1 & W_8^{4} W_8^2 & W_8^{2} W_8^3 \\ \end{pmatrix}\begin{pmatrix} x[0] - x[4] \\ x[1] - x[5] \\ x[2] - x[6] \\ x[3] - x[7] \\ \end{pmatrix}\]
以下のように変形します。
\[\begin{pmatrix} X[1] \\ X[3] \\ X[5] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^2 & W_8^4 & W_8^{6} \\ W_8^0 & W_8^4 & W_8^{0} & W_8^{4} \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} \\ \end{pmatrix}\begin{pmatrix} W_8^0(x[0] - x[4])\\ W_8^1(x[1] - x[5]) \\ W_8^2(x[2] - x[6]) \\ W_8^3(x[3] - x[7]) \\ \end{pmatrix}\]
変形した奇数行と偶数行を並べます。
【奇数行（変形1）】
\[\begin{pmatrix} X[0] \\ X[2] \\ X[4] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^2 & W_8^4 & W_8^6 \\ W_8^0 & W_8^4 & W_8^0 & W_8^{4} \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] \\ x[1] + x[5] \\ x[2] + x[6] \\ x[3] + x[7] \\ \end{pmatrix}\]
【偶数行（変形2）】
\[\begin{pmatrix} X[1] \\ X[3] \\ X[5] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^2 & W_8^4 & W_8^{6} \\ W_8^0 & W_8^4 & W_8^{0} & W_8^{4} \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} \\ \end{pmatrix}\begin{pmatrix} W_8^0(x[0] - x[4])\\ W_8^1(x[1] - x[5]) \\ W_8^2(x[2] - x[6]) \\ W_8^3(x[3] - x[7]) \\ \end{pmatrix}\]
変形1を奇数行と偶数行に分けて、周波数を間引きます。
【変形1の奇数行】
\[\begin{pmatrix} X[0] \\ X[4] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 & W_8^0 & W_8^0 \\ W_8^0 & W_8^4 & W_8^0 & W_8^{4} \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] \\ x[1] + x[5] \\ x[2] + x[6] \\ x[3] + x[7] \\ \end{pmatrix}\]
【変形1の偶数行】
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^2 & W_8^4 & W_8^6 \\ W_8^0 & W_8^6 & W_8^{4} & W_8^{2} \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] \\ x[1] + x[5] \\ x[2] + x[6] \\ x[3] + x[7] \\ \end{pmatrix}\]
これらの行列を整理していきます。まず、変形1の奇数行を変形します。
\[\begin{pmatrix} X[0] \\ X[4] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] + x[2] + x[6] \\ x[1] + x[5]+ x[3] + x[7]\\ \end{pmatrix}\]
変形1の偶数行は、回転因子の対称性を利用して、以下のように変形します。
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^2 & -W_8^0 & -W_8^2 \\ W_8^0 & W_8^6 & -W_8^{0} & -W_8^{6} \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] \\ x[1] + x[5] \\ x[2] + x[6] \\ x[3] + x[7] \\ \end{pmatrix}\]
さらに変形します。
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^2 \\ W_8^0 & W_8^6 \\ \end{pmatrix}\begin{pmatrix} (x[0] + x[4]) - (x[2] + x[6]) \\ (x[1] + x[5]) - (x[3] + x[7]) \\ \end{pmatrix}\]
指数法則を利用して変形します。
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 W_8^0 & W_8^0 W_8^2 \\ W_8^0 W_8^0 & W_8^4 W_8^2 \\ \end{pmatrix}\begin{pmatrix} (x[0] + x[4]) - (x[2] + x[6]) \\ (x[1] + x[5]) - (x[3] + x[7]) \\ \end{pmatrix}\]
以下のように変形します。
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} W_8^0((x[0] + x[4]) - (x[2] + x[6])) \\ W_8^2((x[1] + x[5]) - (x[3] + x[7])) \\ \end{pmatrix}\]
変形1の奇数行と偶数行を並べると以下になります。
【変形1の奇数行（変形3）】
\[\begin{pmatrix} X[0] \\ X[4] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] + x[2] + x[6] \\ x[1] + x[5]+ x[3] + x[7]\\ \end{pmatrix}\]
【変形1の偶数行（変形4）】
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} W_8^0((x[0] + x[4]) - (x[2] + x[6])) \\ W_8^2((x[1] + x[5]) - (x[3] + x[7])) \\ \end{pmatrix}\]
変形2も同様に周波数を間引いて、以下のように整理します。
【変形2の奇数行（変形5）】
\[\begin{pmatrix} X[1] \\ X[5] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) \\ W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7]) \\ \end{pmatrix}\]
【変形2の偶数行（変形6）】
\[\begin{pmatrix} X[3] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0\\ W_8^0 & W_8^4\\ \end{pmatrix}\begin{pmatrix} W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) \\ W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7])) \\ \end{pmatrix}\]
変形3~6を並べると以下になります。
\[\begin{pmatrix} X[0] \\ X[4] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] + x[2] + x[6] \\ x[1] + x[5]+ x[3] + x[7]\\ \end{pmatrix}\]
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} W_8^0((x[0] + x[4]) - (x[2] + x[6])) \\ W_8^2((x[1] + x[5]) - (x[3] + x[7])) \\ \end{pmatrix}\]
\[\begin{pmatrix} X[1] \\ X[5] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}\begin{pmatrix} W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) \\ W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7]) \\ \end{pmatrix}\]
\[\begin{pmatrix} X[3] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0 & W_8^0\\ W_8^0 & W_8^4\\ \end{pmatrix}\begin{pmatrix} W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) \\ W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7])) \\ \end{pmatrix}\]
\(\begin{pmatrix} W_8^0 & W_8^0 \\ W_8^0 & W_8^4 \\ \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}\)を代入します。
\[\begin{pmatrix} X[0] \\ X[4] \\ \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}\begin{pmatrix} x[0] + x[4] + x[2] + x[6] \\ x[1] + x[5]+ x[3] + x[7]\\ \end{pmatrix}\]
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}\begin{pmatrix} W_8^0((x[0] + x[4]) - (x[2] + x[6])) \\ W_8^2((x[1] + x[5]) - (x[3] + x[7])) \\ \end{pmatrix}\]
\[\begin{pmatrix} X[1] \\ X[5] \\ \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}\begin{pmatrix} W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) \\ W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7]) \\ \end{pmatrix}\]
\[\begin{pmatrix} X[3] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix}\begin{pmatrix} W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) \\ W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7])) \\ \end{pmatrix}\]
行列の掛け算を行い、行列を展開します。
\[\begin{pmatrix} X[0] \\ X[4] \\ \end{pmatrix}=\begin{pmatrix} x[0] + x[4] + x[2] + x[6] + x[1] + x[5]+ x[3] + x[7] \\ x[0] + x[4] + x[2] + x[6] - (x[1] + x[5]+ x[3] + x[7])\\ \end{pmatrix}\]
\[\begin{pmatrix} X[2] \\ X[6] \\ \end{pmatrix}=\begin{pmatrix} W_8^0((x[0] + x[4]) - (x[2] + x[6])) + W_8^2((x[1] + x[5]) - (x[3] + x[7])) \\ W_8^0((x[0] + x[4]) - (x[2] + x[6])) - (W_8^2((x[1] + x[5]) - (x[3] + x[7]))) \\ \end{pmatrix}\]
\[\begin{pmatrix} X[1] \\ X[5] \\ \end{pmatrix}=\begin{pmatrix} W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) + W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7]) \\ W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) - (W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7])) \\ \end{pmatrix}\]
\[\begin{pmatrix} X[3] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) + W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7])) \\ W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) - (W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7]))) \\ \end{pmatrix}\]
これらを一つの行列にまとめます。
\[\begin{pmatrix} X[0] \\ X[4] \\ X[2] \\ X[6] \\ X[1] \\ X[5] \\ X[3] \\ X[7] \\ \end{pmatrix}=\begin{pmatrix} x[0] + x[4] + x[2] + x[6] + x[1] + x[5]+ x[3] + x[7] \\ x[0] + x[4] + x[2] + x[6] - (x[1] + x[5]+ x[3] + x[7])\\ W_8^0((x[0] + x[4]) - (x[2] + x[6])) + W_8^2((x[1] + x[5]) - (x[3] + x[7])) \\ W_8^0((x[0] + x[4]) - (x[2] + x[6])) - (W_8^2((x[1] + x[5]) - (x[3] + x[7]))) \\ W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) + W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7]) \\ W_8^0(x[0] - x[4]) + W_8^2(x[2] - x[6]) - (W_8^1(x[1] - x[5]) + W_8^3(x[3] - x[7])) \\ W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) + W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7])) \\ W_8^0(W_8^0(x[0] - x[4]) - W_8^2(x[2] - x[6])) - (W_8^2(W_8^1(x[1] - x[5]) - W_8^3(x[3] - x[7]))) \\ \end{pmatrix}\]
上記の行列を以下のように図式化して、重複した計算を減らします。
【図の見方】
・点のある箇所で足し算
・線上にマイナス符号（-）がある場合はそこで-1を掛ける
・線上に回転因子がある場合はそこで回転因子を掛ける
上記の図のように計算を行うことをバタフライ演算と呼びます。上図では、左から右にバタフライ演算を3回行っています。各バタフライ演算は、前のバタフライ演算が完了していないと行えません。
すべてのバタフライ演算が完了すると、以下のように離散フーリエ変換の結果が得られます。
・\(x[0]=X[0]\)
・\(x[1]=X[4]\)
・\(x[2]=X[2]\)
・\(x[3]=X[6]\)
・\(x[4]=X[1]\)
・\(x[5]=X[5]\)
・\(x[6]=X[3]\)
・\(x[7]=X[7]\)
このとき、\(X[k]\)の並びは、\(X[k]\)の\(k\)をビットリバースしたものになっています。
バタフライ演算後、\(x[n]\)の\(n\)をビットリバースすると、\(x[n]\)の並びは、以下になります。
・\(x[0]=X[0]\)
・\(x[4]=X[1]\)
・\(x[2]=X[2]\)
・\(x[6]=X[3]\)
・\(x[1]=X[4]\)
・\(x[5]=X[5]\)
・\(x[3]=X[6]\)
・\(x[7]=X[7]\)
よって、\(X[k]\)が連番で得られます。
すべてのバタフライ演算が完了すると、\(k\)がビットリバースされるのは、バタフライ演算の度に行列を以下のように奇数行と偶数行に分けるためです。
| バタフライ演算前 | バタフライ演算1回目 | バタフライ演算2回目 |
|---|---|---|
| 000 | 000 | 000 |
| 001 | 010 | 100 |
| 010 | 100 | 010 |
| 011 | 110 | 110 |
| 100 | 001 | 001 |
| 101 | 011 | 101 |
| 110 | 101 | 011 |
| 111 | 111 | 111 |
\(N=8\)の場合、クーリー–テューキー型のFFTは、以下の計算で行えます。\(x[n]\)は離散時間信号、\(X[k]\)は離散フーリエ変換の結果です。\(W\)は、回転因子です。tempは、一時的な変数です。\(\mathrm{BR}()\)は、\(\log_2 N\)ビットのビットリバースを行う関数です。
\[X[0]=x[\mathrm{BR}(0)]\]
\[X[1]=x[\mathrm{BR}(1)]\]
\[X[2]=x[\mathrm{BR}(2)]\]
\[X[3]=x[\mathrm{BR}(3)]\]
\[X[4]=x[\mathrm{BR}(4)]\]
\[X[5]=x[\mathrm{BR}(5)]\]
\[X[6]=x[\mathrm{BR}(6)]\]
\[X[7]=x[\mathrm{BR}(7)]\]
バタフライ演算を見ると分かりますが、以下の演算が最小構成であることが分かります。
3回目のバタフライ演算もこの最小構成であれば、綺麗にまとまるので以下のように指数が0の回転因子を追加します。指数が0の場合は、1なので計算結果に影響はありません。
\(N=8\)の場合、3回バタフライ演算を行い、1回のバタフライ演算につき最小構成の演算を4回行います。
そして、上記のバタフライ演算の図をよく見ると分かりますが、最小構成の配置、回転因子の指数には、パターンがあります。よって、以下の最小構成の演算における●▲■の数をパターンで変化させれば、高速フーリエ変換できます。
前述した\(N=8\)のクーリー–テューキー型のFFTでは、それぞれのバタフライ演算で最小構成の演算を4回行う際に、●▲■を以下の順番で変化させます。
【1回目のバタフライ演算】
●：0, 1, 2, 3
▲：4, 5, 6, 7
■：0, 1, 2, 3
【2回目のバタフライ演算】
●：0, 1, 4, 5
▲：2, 3, 6, 7
■：0, 2, 0, 2
【3回目のバタフライ演算】
●：0, 2, 4, 6
▲：1, 3, 5, 7
■：0, 0, 0, 0
\(N\)が2の累乗である必要がある理由は、各バタフライ演算時に、行列を奇数行と偶数行に分けて、回転因子の行列が2次の正方行列になるまで繰り返せる必要があるためです。
\(N=2^n\)の場合は、\(n\)回バタフライ演算を行い、1回のバタフライ演算につき最小構成の演算を\(\displaystyle\frac{N}{2}\)回行います。
よって、1回のクーリー–テューキー型の周波数間引きFFTで行われる最小構成の演算の回数は、\(\displaystyle\frac{N}{2}\log_2 N\)になります。