2の基数のFFT

「♪FFTは知っててもぉ、それだけーじゃ困りますー♬」©JASRAC14924126。うそ。
ということでまず基本の2のベキのFFTから。

2の基数のFFT

2のベキのFFTは一番基本でこれが一番簡単。また、後から整理するChirp z変換を利用した任意基数のFFTでは、Nが2のベキのFFTを計算することに帰着させて、素直にDFTを計算するよりも計算量を減らすという方法をとっているので、Nが2のベキのFFTが効率よく計算できないとChirp z変換の効率にも影響する。

Nが2のベキの場合のFFTは「2の基数のFFT」と言われ、FFTを最初に考えたKooleyとTukeyが提案したアルゴリズムで、Kooley-Tukeyアルゴリズム（K-T型FFT）などとも言われる。

2のベキのFFTはいろいろなところで解説されているので簡単に。

基本的な考え方

さっき決めたノーテーションでのもとのDFTの定義

で

であるとする。

kの偶数と奇数、nを前半と後半にわけて

これは

とおくと

となって、半分の長さN（Nのオーバーラインのつもり。書けない）のふたつのDFTに分解できたことになる。式がごちゃごちゃして見えるけど注意すれば右肩の乗数を書き換えているだけでそれほど難しくはない。

かけ算の回数を比べるともとのDFTがN²回なのに対して、二つにわけた場合2N²+Nに減る。さらに

であるならこれを入れ子にすればよい。入れ子にするときは式-12を計算して一つの列にしたものを入れ子の内側に渡してやればいい。Nが2のベキなら要素の数が2個になるまで繰り返すことができる。これが2の基数のFFTの考え方。

もうひとつのやり方

逆にnを偶数と奇数、kを前半と後半にわけてもよい。

こちらの場合は

とすると、

とできて、やはりふたつのDFTに分解できる。

混乱しそうだけど、こっちも同じように入れ子にすることができる。こっちの入れ子は入力配列を偶数添字と奇数添字の二つにわけてそれぞれ入れ子の内側に渡して、その結果から合成する。ややこしくて間違いそう。

ちなみに最初のnを前半と後半、kを偶数と奇数にわけるやりかたを「周波数間引き（decimation-in-frequency）」nを偶数と奇数、kを前半と後半にわけるやりかたを「時間間引き（decimation-in-time）」と呼ぶ。すぐどっちがどっちかわからなくなるけど。