FFTアルゴリズムの導出

[] [] []


散フーリエ変換(DFT)は複素乗算がN2回必要だが、

係数wの周期性を使うと複素乗算が(N/2)log2N回に減らせる 【高速フーリエ変換(FFT)

離散フーリエ変換(DFT)

を式どおりに計算すると複素乗算がN2回必要なのでNが大きくなると効率が悪いが、係数wの周期性を使うと複素乗算が(N/2)log2N回に減らせることが知られており、そのアルゴリズムを高速フーリエ変換Fast Fourie Transform (FFT)という。FFTアルゴリズムの説明を教科書でみると、N点のDFTN/2点のDFTに分解できるのでこれを再帰的に繰り返せばよいと説明されているのだが、この再帰的という所がやっかいで、FFTのフローグラフや(再帰的でない)プログラムコードがどうやって導びかれるのかが追いきれなかった。そこで、N,N/2,N/4,...と大きい方から追うのでなく、N=8と小さい場合で導出して一般のNの場合を類推することにする。なお以下の説明の中で、インデックスを2進数表記して計算する方法は「Excelで学ぶフーリエ変換」(渋谷道雄,渡邊八一)によっている。

N=8の場合のDFTの式

において、インデックn2数で表すと

ここでバーは2進数表記であることを示す

さらにインデックスk2進数表記して、係数の周期性w8=1, w4=-1を使うと

の式(1)FFTのアルゴリズムを表している。これをs,t,uれぞれの和に分けて書き下すと次の3ステージの式になる。

ここで、最初と最後のステージの変数はx(n)X(k)ある。

式を見やすくするためインデックスの表記をk,nに戻す

各ステージの式は8個ずつあり、そのうち半分は同じ係数がかかっているから、複素乗算は各ステージで8/2回になる。またステージは3=log28あるから

結局、FFTアルゴリズムを表す式(1)を使うと、複素乗算はDFTのときの8x8回から(8/2)log28に減る。

◇◇

上記の3ステージの式からフローグラフを導いてみる。まず表に書き下すと

n=

(stu)

x(n)=

x0(stu,0)

x1(tu,r)=

x0(0tu,0)+(-)r x0(1tu,0)

x2(u,qr)=

x1(0u,qr)+ (-)q w2r x1(1u,qr)

x3(0,pqr)=

x2(u,pqr)+ (-)p w2q+r x2(u,pqr)

X(k)=

x3(0,pqr)

k=

(pqr)

(000)

x(0)

x1(0,0)=x0(0,0)+w0 x0(4,0)

x2(0,0)=x1(0,0)+w0 x1(2,0)

x3(0,0)=x2(0,0)+w0 x2(1,0)

X(0)

(000)

(100)

x(4)

x1(0,1)=x0(0,0)-w0 x0(4,0)

x2(0,1)=x1(0,1)+w2 x1(2,1)

x3(0,1)=x2(0,1)+w1 x2(1,1)

X(1)

(001)

(010)

x(2)

x1(2,0)=x0(2,0)+w0 x0(6,0)

x2(0,2)=x1(0,0)-w0 x1(2,0)

x3(0,2)=x2(0,2)+w2 x2(1,2)

X(2)

(010)

(110)

x(6)

x1(2,1)=x0(2,0)-w0 x0(6,0)

x2(0,3)=x1(0,1)-w2 x1(2,1)

x3(0,3)=x2(0,3)+w3 x2(1,3)

X(3)

(011)

(001)

x(1)

x1(1,0)=x0(1,0)+w0 x0(5,0)

x2(1,0)=x1(1,0)+w0 x1(3,0)

x3(0,4)=x2(0,0)-w0 x2(1,0)

X(4)

(100)

(101)

x(5)

x1(1,1)=x0(1,0)-w0 x0(5,0)

x2(1,1)=x1(1,1)+w2 x1(3,1)

x3(0,5)=x2(0,1)-w1 x2(1,1)

X(5)

(101)

(011)

x(3)

x1(3,0)=x0(3,0)+w0 x0(7,0)

x2(1,2)=x1(1,0)-w0 x1(3,0)

x3(0,6)=x2(0,2)-w2 x2(1,2)

X(6)

(110)

(111)

x(7)

x1(3,1)=x0(3,0)-w0 x0(7,0)

x2(1,3)=x1(1,1)-w2 x1(3,1)

x3(0,7)=x2(0,3)-w3 x2(1,3)

X(7)

(111)

この表でnの順番が変則的になっているのは、式(1)で和をとる順番がs,t,uと上位ビットからになっているのに合わせたためである。このようにビットの上位と下位をひっくり返した順番に並び変えることを ビットリバーサル(bit-reversal)いう。

次に、繰り返し出てくる基本演算を

という図形で表すことにすると(この形状からバタフライ演算という)、表は次のフローグラフで表される。

ちなみにこのフローグラフCooley-Tukeyというものである。


[] [] []