高速フーリエ変換（FFT）- 理論編

参考

前章のDFTで理解した公式、では、変数に対してそれぞれ操作を行うため、計算量はとなってしまう。

これを、非常に巧妙なやり方でにまで落とすのがFFTである。

回転因子を次のように定義する。これは、複素数平面上の点を原点を中心にだけ回転させたものと考えられる。

また、DFTのときに用いた行列（文字が混ざってややこしい）の成分をと表すことができる。

※の方に乗っける部分の正負を逆転させたため、DFTの時とはの中身の符号が逆になっちゃってます。

複素数平面上での回転を考えると、

が偶数のとき、複素数平面上での位置関係から、

のDFTを考える。入力ベクトルを出力ベクトルに変換する操作は以下のように表すことができる。

ここで、[[回転因子の周期性]]を用いると、

上の式はこのように変形される。

前準備で作った行列が持つ性質をうまく利用して、計算量を落としていく。具体的には、奇数行と偶数行に分けて計算していく。

縦線で区切ったときの左右が全く同じ値になっていることがわかる。したがって、と変形できる。

これを[[回転因子の対称性]]を用いて変形すると、