FFTの基本は、DFTはサンプル数Nが偶数なら 2つのDFTに分解できるということ。 分解するとDF

FFTの基本は、DFTはサンプル数Nが偶数なら
2つのDFTに分解できるということ。
分解するとDFTの処理量は
N²だから、半分に割れれば、(N/2)²+(N/2)²=N²/2
で処理量を半分にできる。

に関して、以下のように説明を受けたのですが、
なぜN²のように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より速い理由である。」

No.1 ベストアンサー 回答者： tknakamuri 回答日時： 2022/03/17 12:54

なんかまだ飲み込めてないね。

元々のDFTの処理は2分割で半分になって行きほぼゼロになってしまう。
逆にそうするためのバタフライの演算量は増えるため、分割を進めると
最終的にそっちが支配的になる。

クイックソートで、ソ―ト対象を2分割する処理時間が
支配的になるのと一緒。

この回答へのお礼

飲み込みが悪くてほんとにすいません。

あの、(N/2)²+(N/2)²=N²/2の計算式が「」ないに見当たらないのですが、(N/2)²+(N/2)²=N²/2 を使っていないのでしょうか？
また、に関してN²なぜNが自乗されるのでしょうか？

お礼日時：2022/03/17 19:35