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