FFT(高速フーリエ変換を更に速くするために改良されたプログラム)の偶数行と奇数行に分けて計算を行うバタフライ演算に関して疑問があります。
(N/2)²+(N/2)²=N²/2の(N/2)²に関してN自乗されるのはわかるのですが、なぜ分母の2まで自乗されるのでしょうか?
また、なぜ偶数行と奇数行に分ける事でさらに早く計算処理が出来るとわかったのでしょうか?
どうかよろしくお願い致します。
補足です。
なぜ高速フーリエ変換(FFT)はO(n*log n)で計算できるのでしょうか?
どうか理由を詳しく教えて下さい。
以下の「」はFFT
を説明したものですが、
「」のどの部分がO(n*log n)を、表すのでしょうか?
「
Ck = (1/N)∑[m=0→N-1] fm・e^(-jkmωD) (k = 0, 1, 2, …… , N-1)...②
ω = 2π/T = 2π/ND、j は虚数単位
と定義したものを
N・Ck = Xk = ∑[m=0→N-1] fm・e^(-jkmωD) (k = 0, 1, 2, …… , N-1) ・・・・・(#)
と書き変えたものに過ぎない。DFTを高速フーリエ変換FFTに変えるにはバタフライ演算というややこしいものを理解しないといけない。はっきり言って掲示板でチョコチョコ説明できるようなものではない。
離散フーリエ変換は、数学者の書いたフーリエ解析の本にはまず載っていないので、信号処理関係の本を探して勉強されたい。
W^(km) = e^(-jkmωD) として N = 4 のとき(#)を展開すれば
X0 = f0・W^0 + f1・W^0 + f2・W^0 + f3・W^0
X1 = f0・W^0 + f1・W^1 + f2・W^2 + f3・W^3
X2 = f0・W^0 + f1・W^2 + f2・W^4 + f3・W^6
X3 = f0・W^0 + f1・W^3 + f2・W^6 + f3・W^9
となるがW^(km)の性質から
X0 = f0・W^0 + f1・W^0 + f2・W^0 + f3・W^0
X1 = f0・W^0 + f1・W^1 - f2・W^0 - f3・W^1
X2 = f0・W^0 - f1・W^0 + f2・W^0 - f3・W^0
X3 = f0・W^0 - f1・W^1 - f2・W^0 + f3・W^1
と簡単になる。しかし、これでも16回の掛け算が必要なのは変わらない。そこで上の式を奇数行と偶数行に分け
X0 = f0・W^0 + f1・W^0 + f2・W^0 + f3・W^0
X2 = f0・W^0 - f1・W^0 + f2・W^0 - f3・W^0
X1 = f0・W^0 + f1・W^1 - f2・W^0 - f3・W^1
X3 = f0・W^0 - f1・W^1 - f2・W^0 + f3・W^1
ここからは上の展開式を行列で表さないとわかりにくいのだが、メンドーなので省略する。とにかく上のように行を入れ替えると
X0 = W^0(f0+f2) + W^0(f1+f3)
X2 = W^0(f0+f2) - W^0(f1+f3)
X1 = W^0(f0-f2) + W^1(f1-f3)
X3 = W^0(f0-f2) - W^1(f1-f3)
のように8個の掛け算だけで済むように変形できる。これがバタフライ演算であり、FFTがDFTより速い理由である。」
回答1件
あなたの回答
tips
プレビュー