実際に, どのように計算量を削減しているのかを解説していきます.
高速フーリエ変換の導出
離散フーリエ変換の式を行列演算に書き換えます.
$
\begin{flalign}
&X\left(k\right) = \sum_{n = 0}^{N - 1}x\left(n\right)W^{n} \\
\end{flalign}
$
$N = 4$ として, 行列演算に変換します.
$
\begin{bmatrix}
X_{0} \\
X_{1} \\
X_{2} \\
X_{3} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{1} & W^{2} & W^{3} \\
W^{0} & W^{2} & W^{4} & W^{6} \\
W^{0} & W^{3} & W^{6} & W^{9} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix}
$
ここで, 回転因子の性質を利用すると, $W^{4} = W^{0}, W^{6} = W^{2}, W^{9} = W^{1}$ となるので,
$
\begin{bmatrix}
X_{0} \\
X_{1} \\
X_{2} \\
X_{3} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{1} & W^{2} & W^{3} \\
W^{0} & W^{2} & W^{0} & W^{2} \\
W^{0} & W^{3} & W^{2} & W^{1} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix}
$
ここまでで, 離散フーリエ変換の演算を行列演算に変換することができました.
行列演算に変換できたら, 行を偶奇で分割します. 偶数行を行列の上部に入れ替えて, 奇数教を行列の下部に入れ替えます. 変換行列の行を入れ替えるので,
出力となる $X_{k}$ も行が入れ替わることに注意してください.
$
\begin{bmatrix}
X_{0} \\
X_{2} \\
X_{1} \\
X_{3} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{2} & W^{0} & W^{2} \\
W^{0} & W^{1} & W^{2} & W^{3} \\
W^{0} & W^{3} & W^{2} & W^{1} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix}
$
ここで, 回転因子の回転方向を考慮すると, 左上 2 行 2 列の行列と, 右上 2 行 2 列の行列は対称になっている, すなわち,
同じ回転方向の回転因子の行列になっています. 同様に, 左下 2 行 2 列の行列と, 右下 2 行 2 列の行列は負の対称になっている, すなわち,
回転方向が互いに逆方向の回転因子の行列になっています.
これを考慮すると, 行列演算はさらに以下のように変形できます.
$
\begin{bmatrix}
X_{0} \\
X_{2} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} \\
W^{0} & W^{2} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} + x_{2}) \\
(x_{1} + x_{3}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{1} \\
X_{3} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{1} \\
W^{0} & W^{3} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} - x_{2}) \\
(x_{1} - x_{3}) \\
\end{bmatrix}
$
この変形によって, 乗算と加算の回数がおよそ半分まで減らすことができました. ここでさらに回転因子の性質を利用すると, 以下のように変形できます.
$
\begin{bmatrix}
X_{0} \\
X_{2} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} \\
W^{0} & -W^{0} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} + x_{2}) \\
(x_{1} + x_{3}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{1} \\
X_{3} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{1} \\
W^{0} & -W^{1} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} - x_{2}) \\
(x_{1} - x_{3}) \\
\end{bmatrix}
$
ところで, 行の偶奇を入れ替えたので, 出力となる $X_{k}$ の順序が, 入力の順序と一致しなくなります (つまり,
ある時間領域の値のスペクトルが一致しなくなります). 実は, 一見するとランダムに並びますが, 規則性があり, 各インデックスを 2 進数で表現した場合の,
ビットを上下反転させた関係になっています. この関係を利用して, インデックスの並びを整列するアルゴリズムをビットリバースと呼びます.
ビットリバースの対応表 2 ビット ($N = 4$)
Index |
$x_{n}$ |
$X_{k}$ |
0 |
00 |
00 |
1 |
01 |
10 |
2 |
10 |
01 |
3 |
11 |
11 |
同じように, $N = 8$ として, 高速フーリエ変換になるように行列演算します.
$
\begin{bmatrix}
X_{0} \\
X_{1} \\
X_{2} \\
X_{3} \\
X_{4} \\
X_{5} \\
X_{6} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{1} & W^{2} & W^{3} & W^{4} & W^{5} & W^{6} & W^{7} \\
W^{0} & W^{2} & W^{4} & W^{6} & W^{8} & W^{10} & W^{12} & W^{14} \\
W^{0} & W^{3} & W^{6} & W^{9} & W^{12} & W^{15} & W^{18} & W^{21} \\
W^{0} & W^{4} & W^{8} & W^{12} & W^{16} & W^{20} & W^{24} & W^{29} \\
W^{0} & W^{5} & W^{10} & W^{15} & W^{20} & W^{25} & W^{30} & W^{35} \\
W^{0} & W^{6} & W^{12} & W^{18} & W^{24} & W^{30} & W^{36} & W^{42} \\
W^{0} & W^{7} & W^{14} & W^{21} & W^{28} & W^{35} & W^{42} & W^{49} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{bmatrix}
$
回転因子の性質を利用すると,
$
\begin{bmatrix}
X_{0} \\
X_{1} \\
X_{2} \\
X_{3} \\
X_{4} \\
X_{5} \\
X_{6} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{1} & W^{2} & W^{3} & W^{4} & W^{5} & W^{6} & W^{7} \\
W^{0} & W^{2} & W^{4} & W^{6} & W^{0} & W^{2} & W^{4} & W^{6} \\
W^{0} & W^{3} & W^{6} & W^{1} & W^{4} & W^{7} & W^{2} & W^{5} \\
W^{0} & W^{4} & W^{0} & W^{4} & W^{8} & W^{5} & W^{0} & W^{5} \\
W^{0} & W^{5} & W^{2} & W^{7} & W^{4} & W^{1} & W^{6} & W^{3} \\
W^{0} & W^{6} & W^{4} & W^{2} & W^{0} & W^{6} & W^{4} & W^{2} \\
W^{0} & W^{7} & W^{6} & W^{5} & W^{4} & W^{3} & W^{2} & W^{1} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{bmatrix}
$
行列演算に変換できたら, 行を偶奇で分割します. 偶数行を行列の上部に入れ替えて, 奇数教を行列の下部に入れ替えます. 変換行列の行を入れ替えるので,
出力となる $X_{k}$ も行が入れ替わることに注意してください.
$
\begin{bmatrix}
X_{0} \\
X_{2} \\
X_{4} \\
X_{6} \\
X_{1} \\
X_{3} \\
X_{5} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{2} & W^{4} & W^{6} & W^{0} & W^{2} & W^{4} & W^{6} \\
W^{0} & W^{4} & W^{0} & W^{4} & W^{0} & W^{4} & W^{0} & W^{4} \\
W^{0} & W^{6} & W^{4} & W^{2} & W^{0} & W^{6} & W^{4} & W^{2} \\
W^{0} & W^{1} & W^{2} & W^{3} & W^{4} & W^{5} & W^{6} & W^{7} \\
W^{0} & W^{3} & W^{6} & W^{1} & W^{4} & W^{7} & W^{2} & W^{5} \\
W^{0} & W^{5} & W^{2} & W^{7} & W^{4} & W^{1} & W^{6} & W^{3} \\
W^{0} & W^{7} & W^{6} & W^{5} & W^{4} & W^{3} & W^{2} & W^{1} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3} \\
x_{4} \\
x_{5} \\
x_{6} \\
x_{7} \\
\end{bmatrix}
$
ここで, 回転因子の回転方向を考慮すると, 左上 4 行 4 列の行列と, 右上 4 行 4 列の行列は対称になっている, すなわち,
同じ回転方向の回転因子の行列になっています. 同様に, 左下 4 行 4 列の行列と, 右下 4 行 4 列の行列は負の対称になっている, すなわち,
回転方向が互いに逆方向の回転因子の行列になっています.
これを考慮すると, 行列演算はさらに以下のように変形できます.
$
\begin{bmatrix}
X_{0} \\
X_{2} \\
X_{4} \\
X_{6} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{2} & W^{4} & W^{6} \\
W^{0} & W^{4} & W^{0} & W^{4} \\
W^{0} & W^{6} & W^{4} & W^{2} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} + x_{4} \\
x_{1} + x_{5} \\
x_{2} + x_{6} \\
x_{3} + x_{7} \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{1} \\
X_{3} \\
X_{5} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{1} & W^{2} & W^{3} \\
W^{0} & W^{3} & W^{6} & W^{1} \\
W^{0} & W^{5} & W^{2} & W^{7} \\
W^{0} & W^{7} & W^{6} & W^{5} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} - x_{4} \\
x_{1} - x_{5} \\
x_{2} - x_{6} \\
x_{3} - x_{7} \\
\end{bmatrix}
$
ここまでの処理によって, $N = 8$ の高速フーリエ変換を $N = 4$ に帰着することができたので, 再帰的に
$N = 4$ の場合も, 行の偶奇を入れ替えて回転因子の性質を利用して,
$N = 2$ の場合の高速フーリエ変換に帰着させます.
$
\begin{bmatrix}
X_{0} \\
X_{4} \\
X_{2} \\
X_{6} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} & W^{0} & W^{0} \\
W^{0} & W^{4} & W^{0} & W^{4} \\
W^{0} & W^{2} & W^{4} & W^{6} \\
W^{0} & W^{6} & W^{4} & W^{2} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} + x_{4} \\
x_{2} + x_{6} \\
x_{1} + x_{5} \\
x_{3} + x_{7} \\
\end{bmatrix}
$
ここで, 回転因子の回転方向を考慮すると, 左上 2 行 2 列の行列と, 右上 2 行 2 列の行列は対称になっている, すなわち,
同じ回転方向の回転因子の行列になっています. 同様に, 左下 2 行 2 列の行列と, 右下 2 行 2 列の行列は負の対称になっている, すなわち,
回転方向が互いに逆方向の回転因子の行列になっています.
$
\begin{bmatrix}
X_{1} \\
X_{5} \\
X_{3} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{1} & W^{2} & W^{3} \\
W^{0} & W^{5} & W^{2} & W^{7} \\
W^{0} & W^{3} & W^{6} & W^{1} \\
W^{0} & W^{7} & W^{6} & W^{5} \\
\end{bmatrix}
\begin{bmatrix}
x_{0} - x_{4} \\
x_{2} - x_{6} \\
x_{1} - x_{5} \\
x_{3} - x_{7} \\
\end{bmatrix}
$
こちらも, 回転因子の回転方向を考慮すると, 左上 2 行 2 列の行列と, 右上 2 行 2 列の行列は時計回りに
$\frac{2}{8}$ 回転, また, 左下 2 行 2 列の行列と, 右下 2 行 2 列の行列は反時計回りに
$\frac{2}{8}$ 回転しているという対称性があります.
これら考慮すると, 行列演算はさらに以下のように変形できます.
$
\begin{bmatrix}
X_{0} \\
X_{4} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} \\
W^{0} & W^{4} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} + x_{4}) + (x_{2} + x_{6}) \\
(x_{1} + x_{5}) + (x_{3} + x_{7}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{2} \\
X_{6} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{2} \\
W^{0} & W^{6} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} + x_{4}) - (x_{2} + x_{6}) \\
(x_{1} + x_{5}) - (x_{3} + x_{7}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{1} \\
X_{5} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{1} \\
W^{0} & W^{5} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} - x_{4}) + W^{2}(x_{2} - x_{6}) \\
(x_{1} - x_{5}) + W^{2}(x_{3} - x_{7}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{3} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{3} \\
W^{0} & W^{7} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} - x_{4}) - W^{2}(x_{2} - x_{6}) \\
(x_{1} - x_{5}) - W^{2}(x_{3} - x_{7}) \\
\end{bmatrix}
$
ここでさらに回転因子の性質を利用すると, 以下のように変形できます.
$
\begin{bmatrix}
X_{0} \\
X_{4} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{0} \\
W^{0} & -W^{0} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} + x_{4}) + (x_{2} + x_{6}) \\
(x_{1} + x_{5}) + (x_{3} + x_{7}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{2} \\
X_{6} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{2} \\
W^{0} & -W^{2} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} + x_{4}) - (x_{2} + x_{6}) \\
(x_{1} + x_{5}) - (x_{3} + x_{7}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{1} \\
X_{5} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{1} \\
W^{0} & -W^{1} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} - x_{4}) + W^{2}(x_{2} - x_{6}) \\
(x_{1} - x_{5}) + W^{2}(x_{3} - x_{7}) \\
\end{bmatrix}
$
$
\begin{bmatrix}
X_{3} \\
X_{7} \\
\end{bmatrix}
=
\begin{bmatrix}
W^{0} & W^{3} \\
W^{0} & -W^{3} \\
\end{bmatrix}
\begin{bmatrix}
(x_{0} - x_{4}) - W^{2}(x_{2} - x_{6}) \\
(x_{1} - x_{5}) - W^{2}(x_{3} - x_{7}) \\
\end{bmatrix}
$
$N = 2$ の場合の高速フーリエ変換に帰着できたので, 最後にビットリバースを適用してインデックスを並び替えます.
ビットリバースの対応表 3 ビット ($N = 8$)
Index |
$x_{n}$ |
$X_{k}$ |
0 |
000 |
000 |
1 |
001 |
100 |
2 |
010 |
010 |
3 |
011 |
110 |
4 |
100 |
001 |
5 |
101 |
101 |
6 |
110 |
011 |
7 |
111 |
111 |
高速フーリエ変換のサイズを一般化して, $N = 2^{m}$ の場合も,
$2^{m}, 2^{m - 1}, 2^{m - 2}\cdots 32, 16, 8, 4$ と再帰的に高速フーリエ変換を導出することが可能です. また,
このセクションで解説した高速フーリエ変換は, 時間間引き型高速フーリエ変換のアルゴリズムとなります.
周波数間引き型高速フーリエ変換のアルゴリズムは, 細部は異なりますが本質的には同じです.
同様に, 逆離散フーリエ変換の (時間) 計算量も $O\left(N^{2}\right)$ から
$O\left(N\mathrm{log_{2}}N\right)$ に減らすことができます (逆高速フーリエ変換 (IFFT:
Inverse Fast Fourier Transform)).