![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
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ベストアンサー
- 回答日時:
なんかまだ飲み込めてないね。
元々のDFTの処理は2分割で半分になって行きほぼゼロになってしまう。
逆にそうするためのバタフライの演算量は増えるため、分割を進めると
最終的にそっちが支配的になる。
クイックソートで、ソ―ト対象を2分割する処理時間が
支配的になるのと一緒。
飲み込みが悪くてほんとにすいません。
あの、(N/2)²+(N/2)²=N²/2の計算式が「」ないに見当たらないのですが、(N/2)²+(N/2)²=N²/2 を使っていないのでしょうか?
また、に関してN²なぜNが自乗されるのでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
女性はマンコ舐めてほしいんで...
-
昨日の晩にスゴくいやらしい体...
-
男性に質問:彼女をオカズにし...
-
処女を抱いた男性へ質問です
-
息子と性的関係になり抜け出せない
-
男性に質問です! 男性は女性の...
-
エロくなってきた妻
-
処女とエッチして 相手の男性が...
-
28才OLです、マスターベー...
-
入れられてる側は(女性側)どん...
-
付き合えそうな女性との行為…想...
-
男性は好きな女性なら挿入行為...
-
処女のとき、何回目のHで挿入...
-
セフレの女性が離れていきそうな時
-
職場の女性社員を見て妄想する...
-
私はちんこが好きです。 凄く下...
-
男性は前戯だけでも我慢できる...
-
男の人が勃ってるときって、頭...
-
母とセックスしたい
-
彼女はみんな彼氏にクンニをし...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
男性に質問:彼女をオカズにし...
-
生とゴムの違い
-
息子と性的関係になり抜け出せない
-
昨日の晩にスゴくいやらしい体...
-
エロくなってきた妻
-
男性が好きな人でオナニーする...
-
男性に質問です! 男性は女性の...
-
処女とエッチして 相手の男性が...
-
処女を抱いた男性へ質問です
-
男性側はセックスでの挿入時、...
-
女性はマンコ舐めてほしいんで...
-
28才OLです、マスターベー...
-
付き合えそうな女性との行為…想...
-
処女のとき、何回目のHで挿入...
-
男性は好きな女性なら挿入行為...
-
入れられてる側は(女性側)どん...
-
職場の女性社員を見て妄想する...
-
セフレの女性が離れていきそうな時
-
私はちんこが好きです。 凄く下...
-
男性は前戯だけでも我慢できる...
おすすめ情報