FFTアルゴリズムのバリエーション

[] [] []


FFTのアルゴリズムには次のバリエーションがある

(1) 基数(radix)

(2) 時間間引き(DIT)と周波数間引き(DIF)

(3) フローグラフの形(インデックスの順序)

前項で導いたFFTのアルゴリズムはradix-2,DITという一例であり他にもいろいろなバリエーションがある。

(1) 基数(radix)

前項の例では、インデックスn,k2進数表記して式(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-44クロック、radix-22クロックかかり、radix-4radix-22倍にしか速くならない。そこで、普通はメモリを分割して複数データを同時に読み出すように工夫するのだが、メモリ読み出しを並列化するのに合わせて、演算器もradix-2のバタフライ演算を4並列化してしまえば、演算器数も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に戻すと

DITDIFは、次のようにバタフライ演算が異なる。また一番下に示すように同じ形のフローグラフでも係数のインデックスが異なる。

 

バタフライ演算

DIT

DIF

◇◇◇

(3) フローグラフの形(インデックスの順序)

前項の例ではCooley-Tukey型のフローグラフを導いた。一旦フローグラフが得られたら、各ステージ内のノードの順序は演算結果に影響しないので、好きなように並べ替えてよい。といっても意味のある並べ替えはそんなに多くはなく、代表的なものは次のとおり。具体的なフローグラフは一番下に示してある。

DIT/DIF

フローグラフの形

入力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でも外付けメモリよりもオンチップメモリ(キャッシュ)を使った方が高速に読み書きできるので、オンチップメモリに収まるように配列を小さくした方が計算は速くできる。場合によっては、四則演算の回数を気にするよりも、チップ内のメモリに収めることを優先して演算の順番を変えた方がよいぐらいである。となると、in-placeでないのは、配列がx[N] x1[N]2倍必要になって不利なのである。

一方、ビットリバース順に並べ替える操作は、外部との入出力転送と同時にやってしまえばよいので、それほど欠点ではない。

◇◇◇◇

いろいろなバリエーションのフローグラフをまとめて以下に示す。


[] [] []