FFTアルゴリズムのバリエーション
|
FFTのアルゴリズムには次のバリエーションがある (1) 基数(radix) (2) 時間間引き(DIT)と周波数間引き(DIF) (3) フローグラフの形(インデックスの順序) |
前項で導いたFFTのアルゴリズムはradix-2,DITという一例であり、他にもいろいろなバリエーションがある。
◇
(1) 基数(radix)
前項の例では、インデックスn,kを2進数表記して式(1)を導いた。この場合を radix-2という。
別の方法として何進数にしてもよいので、例えば4進数(radix-4という)にすると。
こうすると、2項のバタフライ演算
が次のような4項の演算になる。(形は異なるがこれもバタフライ演算とよぶことにする)
複素乗算の数で比較してみると、次表のとおりradix-4の方がradix-2より少なくて済む。
|
基数 |
ステージ数 (a) |
ステージ内の バタフライ演算の数(b) |
バタフライ演算内の 複素乗算の数(c) |
全複素乗算数 (a)*(b)*(c) |
|
radix-2 |
log2N |
N/2 |
1 |
(N/2)log2N |
|
radix-4 |
log4N=(log2N)/2 |
N/4 |
3 |
(3N/8)log2N |
一見radix-4の方が速くなりそうだが、実際には実装方法に依存する。
CPUで実行する場合は演算器が1個なので、複素乗算の回数が少ないradix-4の方が速くなりそうである。
FPGAで実装する場合のトレードオフは複雑になる。まず、バタフライ演算をパイプライン化してradix-2でもradix-4でも同じ1クロックで実行できるようにすれば、radix-4の方が4倍速くなる。しかし、1つのメモリからは1個ずつしかデータが読み出せないので、radix-4は4クロック、radix-2は2クロックかかり、radix-4はradix-2の2倍にしか速くならない。そこで、普通はメモリを分割して複数データを同時に読み出すようにするのだが、メモリ読み出しを並列化するのに合わせて、radix-2のバタフライ演算も並列化してしまえば、結局radix-4と差異がなくなる。そう考えると、radix-2の方が並列化回路が簡単そうな分だけ有利かもしれない。
◇◇
(2) 時間間引き(DIT)と周波数間引き(DIF)
前項の例では、係数を時間軸nのビットstuごとに分けた。この方法を、時間間引き Decimation in Time (DIT)という。
別の方法として、周波数軸kのビットpqrごとに分けてもよい。こちらを、周波数間引き Decimation in Frequency (DIF)という。
s,t,uそれぞれの和に分けて書き下すと次の3ステージの式になる。
式を見やすくするためインデックスの表記をk,nに戻すと
DITとDIFは、次のようにバタフライ演算が異なる。また一番下に示すように同じ形のフローグラフでも係数のインデックスが異なる。
|
|
バタフライ演算 |
|
DIT |
|
|
DIF |
|
◇◇◇
(3) フローグラフの形(インデックスの順序)
前項の例ではCooley-Tukey型のフローグラフを導いた。一旦フローグラフが得られたら、各ステージ内のノードの順序は演算結果に影響しないので、好きなように並べ替えてよい。といっても意味のある並べ替えはそんなに多くなく、代表的なものは次のとおり。具体的なフローグラフは一番下に示してある。
|
間引き |
フローグラフの形 |
入力x(n)の順序 |
係数wkの順序 |
出力X(k)の順序 |
バタフライ演算の入出力 |
|
DIT |
Cooley-Tukey |
bit-reversed |
natural |
natural |
in-place |
|
Cooley-Tukeyの変形 |
natural |
bit-reversed |
bit-reversed |
in-place |
|
|
Stockham |
natural |
natural |
natural |
out-of-place |
|
|
DIF |
Cooley-Tukey |
bit-reversed |
bit-reversed |
natural |
in-place |
|
Cooley-Tukeyの変形 |
natural |
natural |
bit-reversed |
in-place |
|
|
Stockham |
natural |
natural |
natural |
out-of-place |
最初のCooley-Tukey型は入力がビットリバース順(bit-reversed order)になっている。次のCooley-Tukeyの変形は、入力を0,1,2...と自然な順番(natural order)に並べ替えたものであるが、出力がビットリバース順になってしまう。最後のStockham型は入力も出力も各ステージのインデックス2mn+kも自然な順番に並び替えたものであるが、バタフライ演算の入出力が異なる位置(out-of-place)になってしまう。このようにどれも一長一短があり、実装方法によってどれが有利かを考えなければならない。
このうち、バタフライ演算の入出力が同じ位置にある(in-place)ことは、実装面で重要である。なぜなら、CPUでもFPGAでも外付けメモリよりもオンチップメモリ(キャッシュ)の方が高速に読み書きできるので、多少演算が増えてもオンチップメモリに収まるように配列を小さくした方が、速く計算できる。なので、配列が2倍になるout-of-placeは大きな欠点になる。
一方、ビットリバース順に並べ替える操作は、外部との入出力転送と同時にやってしまえばよいので、それほど欠点にならない。
◇◇◇◇
いろいろなバリエーションのフローグラフをまとめて以下に示す。
