FFT - メモ

何回見ても非再帰 FFTの話が覚えられないのでメモ

1のN乗根をgとする。
$f(x)=\sum_{i=0}^{N-1}a_i x^i$ を離散フーリエ変換したい。
その結果は
$\hat{f}(x)=\sum_{i=0}^{N-1}f(g^i) x^i$
になる。ということで、全てのiについての $f(g^i)$ が求められればよい。
$f(g^i)=\sum_{k=0}^{N-1}a_k g^{ik}$
これを頑張って計算する。
ところで、再帰 FFTの気持ちには2種類あることをご存じでしたか？ぼくは今知りました。

kの偶奇で分ける

$\begin{eqnarray*} f(g^i)&=&\sum_{k:even}a_k g^{ik}&+&\sum_{k:odd}a_k g^{ik}\\ &=& \sum_{k'=0}^{N/2-1} a_{2k'} g^{i2k'}&+&\sum_{k'=0}^{N/2-1} a_{2k'+1} g^{i(2k'+1)}\\ &=& \sum_{k'=0}^{N/2-1} a_{2k'} (g^{2i})^{k'}&+&g^i \sum_{k'=0}^{N/2-1} a_{2k'+1} (g^{2i})^{k'}\\ &=& f_e(g^{2i})&+&g^i f_o(g^{2i}) \end{eqnarray*}$
ということで、fの偶数次の項、奇数次の項のみからなるN/2次の多項式をFFTできればよいので再帰的にやればできる

iの偶奇で分ける

$\begin{eqnarray*} f(g^{2i})&=&\sum_{k=0}^{N/2-1}a_k g^{2ik}&+&\sum_{k=N/2}^{N-1} a_k g^{2ik}\\ &=&\sum_{k=0}^{N/2-1}a_k g^{2ik}&+&\sum_{k=0}^{N/2-1} a_{k+N/2} g^{2i(k+N/2)}\\ &=&\sum_{k=0}^{N/2-1}a_k g^{2ik}&+&\sum_{k=0}^{N/2-1} a_{k+N/2} g^{2ik}\\ &=&\sum_{k=0}^{N/2-1}(a_k+a_{k+N/2}) g^{2ik}& & \end{eqnarray*}$
$\begin{eqnarray*} f(g^{2i+1})&=&\sum_{k=0}^{N/2-1}a_k g^{(2i+1)k}&+&\sum_{k=N/2}^{N-1} a_k g^{(2i+1)k}\\ &=&\sum_{k=0}^{N/2-1}(a_k g^k)g^{2ik}&+&\sum_{k=N/2}^{N-1} (a_k g^k) g^{2ik}\\ &=&\sum_{k=0}^{N/2-1}(a_k g^k) g^{2ik}&+&\sum_{k=0}^{N/2-1} (a_{k+N/2} g^{k+N/2}) g^{2i(k+N/2)}\\ &=&\sum_{k=0}^{N/2-1}(a_k g^k) g^{2ik}&+&\sum_{k=0}^{N/2-1}(- a_{k+N/2} g^k) g^{2i(k+N/2)}\\ &=&\sum_{k=0}^{N/2-1}(a_k-a_{k+N/2}) g^k g^{2ik}& & \end{eqnarray*}$
ということで、iが偶数のときは $\sum_{k=0}^{N/2-1}(a_k+a_{k+N/2})x^k$ 、奇数のときは $\sum_{k=0}^{N/2-1}(a_k-a_{k+N/2})g^k x^k$ という多項式がそれぞれFFTできればよいので再帰的にやればできる

非再帰 FFT

iの偶奇で分けるFFTを非再帰にするのは簡単。 $a_k+a_{k+N/2}$ と $(a_k-a_{k+N/2}) g^k$ を作っていけばいいだけなので。
欲張りにinplaceでやりましょう。適当に、前半に $a_k+a_{k+N/2}$ を、後半に $(a_k-a_{k+N/2}) g^k$ をまとめていくことにする。
とりあえず1回

これで前半と後半が別の問題になったので、後半のことは忘れて前半だけに注目してもう1回

ところでこうやってやっていくと、前半には「下のbitが0のもの」が、後半には「下のbitが1のもの」が集まっていくことになる。
要するにbit reverseされているので、最後にその辺をうまく並び替えればOK