FFTのバタフライ演算についてまとめます。「自分で勉強したけれど難しかった」という方、ご覧ください。前回、前々回の記事からの続きです。
FFT（高速フーリエ変換）とは、DFT（離散フーリエ係数）に高速化の工夫を施した手続きです。Ｔ秒間で手に入るＮ個のデータ
から、Ｎ個の離散フーリエ係数
を次の式によって計算するのがDFTです。
ここでＷは回転子を表します。回転子とは
で定義される数値です。Ｎの値によって変わるので注意しましょう。
実は、DFTはそのままの式で計算するとＮが大きい値のときには計算量が爆発的に増えてしまい、コンピュータを使ってもどうにもなりません。そこで計算量を減らす工夫が必要なのです。それがFFTです。FFTはバタフライ演算という計算法の組み合わせで実現されます。これが分かりにくく、前の記事で「分かりやすい解説の載った本」ということで『道具としてもフーリエ解析』を紹介したのでした。「これを読んでください」でもよいのですが、ここではバタフライ演算の簡単な解説をしておきます（いずれ、なぜバタフライ演算に「ビットリバース」が出てくるのか、記事にします）。
とりあえず、バタフライ演算が何をどんな手順で計算するものなのか理解しましょう。その上で機会を改めて「どうしてこういう計算法で正しい結果が出るのか」と考えればよいと思います。数学の証明も、定理の主張がよく分かっていた方が分かりやすくなります。同じです。
さて、FFTではデータの個数は2の累乗に限っています。そういう制限のある方法なのです。理屈はとりあえず置くとして、Ｎ＝2（データの個数が2個）のときのFFTは次のバタフライ演算で実現できます。
「ー」（マイナスの記号）が図の中にあることが分かります。この図は、
という計算を表しています。マイナスの意味も分かるでしょう。「バタフライ」というのは、図が蝶々のようだから……ですね。
Ｎ＝４のときのFFTは次のバタフライ演算で実現されます。
この図は、次の計算を表しています。
図のどこが式にどこに対応しているのかよく見てください。ここでＷはＮ＝４のときの回転子です。次の式で定義されます。
を、すでに解説したN=2のFFTに渡しています。その結果、
が計算されます。
も同様です。このとき、計算結果は
でなく
であることに注意。結果の添え字は0, 1, 2, 3を2桁の2進数とみてビットの並びを逆転したもの（ビットリバースしたもの）です。一応、全ての添え字で見てみます。
次にＮ＝8のFFTを見てみましょう。これが分かればどんなＮに対してもFFTの計算法が見通せます。
上の図は、下の8本の式を表しています。N=4のときの計算の手順をそのままN=8に拡張したようなものですが、必ず図と式の対応を確認してください。
ここでＷは回転子ですが、N=8のときの回転子なので、N=4のときのものとは違います。N=8のときの回転子は次の通りです。
この記事では、Ｎ＝４のときの回転子とＮ＝8のときの回転子に同じ記号、Ｗを使っています。いろいろな書籍で、例えばＮ＝8のときの回転子を
と表しています。しかし文脈からＮの値は分かるケースが多く、式も煩雑になるのでこの記事では下付きの添え字は省略しました。
図では
をN=4のFFTに渡しています。その結果、
が計算されるのです。
も同様です。このとき、全体の計算結果は
でなく
であることに注意。結果の添え字は0, 1, 2, 3, 4, 5, 6, 7を3桁の2進数で表してビットの並びを逆転したもの（ビットリバースしたもの）です。いくつかの例で確認してみましょう。
以上でFFTの計算、バタフライ演算について解説しました。これが分かればもうＮ＝16でもＮ＝32でも計算もプログラミングもできるでしょう。しかし、まだ「なぜ最後の出力がビットリバースになっているのか」は解決していません。いろいろテキストを見ると「ビットリバースになっている」などのひと言で説明していることもあります。数学のテキストというわけでもない場合、Ｎ＝８くらいまででは確かにビットリバースになっているのだからもうこれでいいだろう、のような雰囲気なのかも知れません。気持ちの悪い人もいるかと思いますが、数学的帰納法で示せます（確認してはいませんが）。そこまでしなくても、「Ｎ＝4ではビットリバースになる」を仮定して「Ｎ＝8でもビットリバースになる」を示せば、一般の場合の数学的帰納法の証明に自信が持てます。今回はここまでにしておきますが、いずれその部分も記事にするつもりです。
