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

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

だから、ソ―トとかと同じ分割統治アルゴリズムで行けそう。」
と言われ、偶数と奇数に分けるバタフライ演算の計算を表していると考えました。
また、
「
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より速い理由である。」...①


の「N=4の時にバタフライ演算を使う場合、
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個の掛け算だけで済むように変形できる。これがバタフライ演算である」
と言われ、O(n*log n)より、この部分もバタフライ演算の計算を表していると考えました。

N=4の時は(N/2)²+(N/2)²=N²/2とO(n*log n)の値は8となり一致しますがN=8の時は値が一致しませんでした。
私の考えが間違っている場合、(N/2)²+(N/2)²=N²/2は①のどの部分を表しているのでしょうか？

質問者からの補足コメント

• 以前に
  
  ＞のように8個の掛け算だけで済むように変形できる。これがバタフライ演算である」と考えたため、バタフライ演算からO(n*log n)が導けたのではないかと考えました。
  
  あってますよ。
  本来ならNｘNの正方行列の行列式よりN^2で、16回の掛け算が必要なところO(n*log n)により8個の掛け算だけで済む。
  
  との事でN=4の時、O(n*log n)は偶数と奇数に分けてバタフライ演算した部分の計算を表している事はわかっています。

    補足日時：2022/03/31 21:06

• 度々失礼致します。
  
  すなわち、
  (N/2)^2+(N/2)^2 は、「N/2-point DFT」の部分の処理量になります。
  との事ですが、
  N=4の時、(N/2)^2+(N/2)^2=N^2/2より
  16/2=8となるため、(N/2)^2+(N/2)^2は結果的に偶数と奇数番の式の計算を行う部分を表していると思ったのですが、正しいでしょうか？
  
  (N/2)^2+(N/2)^2は結果的にN^2/2となり、
  このN^2はN=4の時、
  N列とN列の計算を偶数と奇数に分ければ
  計算の「回数」が8回で済む事を法則的にN^2と導かれただけで(N/2)^2+(N/2)^2はN^2を導く上でN列とN列の計算を偶数と奇数に分ける部分なだけという認識で間違いないでしょうか？

    補足日時：2022/04/06 03:24

• また、
  N=4の時にたまたまN列とN^2とn・log nが同じ値だっただけで、
  n・log nはN列とN列の計算を偶数と奇数に分ける部分を表しているのではなく、以下の()の※のような働きをするという認識で間違いないでしょうか？
  
  (※n・log n の計算量は、「N/2-point DFT」の部分も同様に2*分割されたDFT+バタフライで計算→その中の「DFT」も分割して ... と分割できなくなるところまでやった結果です。)

    補足日時：2022/04/06 03:24

• 度々すいません。
  だとしたら、
  N=4の時にバタフライ演算を使う場合、
  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個の掛け算だけで済むように変形できる。これがバタフライ演算である」
  の部分の計算式はO(n*log n)ではなく、正しくは(N/2)^2+(N/2)^2=N^2/2でしょうか？
  
  kmee様、どうかよろしくお願い致します。

    補足日時：2022/04/06 03:31

• また、O(n*log n)は
  仮にN=8として24と導かれ、この24とは
  バタフライ演算の回数が24回と思うのですが、正しいでしょうか？

    補足日時：2022/04/06 05:29

No.3 回答者： kmee 回答日時： 2022/04/02 11:08

https://en.wikipedia.org/wiki/Butterfly_diagram# …

この図がわかりやすいかと。

(N/2)^2+(N/2)^2 は、「N/2-point DFT」の部分の処理量になります。
※ 通常のDFTの処理量は 大きさ n に対して n^2 の処理量
→ n=N/2 のときは (N/2)^2
→ それが二つあるから (N/2)^2+(N/2)^2

全体の処理量を見るならば、最後のバタフライ演算の分の +N を忘れてはいけません。

n・log n の計算量は、「N/2-point DFT」の部分も同様に2*分割されたDFT+バタフライで計算→その中の「DFT」も分割して ... と分割できなくなるところまでやった結果です。

2分割しかしていない (N/2)^2+(N/2)^2 +N と 限界まで分割した N・log N を比べることが無意味です。
ましてや、 バタフライ演算分の +N を考慮しない (N/2)^2+(N/2)^2 と比較するなど。
N=4 のとき、 (N/2)^2+(N/2)^2 と N・log N が同じになったのは偶然です。





大きさn のDFT(またはFFT)の処理量を T(n) とします。
nが偶数 のとき、2分割 して バタフライ演算 すると
T(n) = 2・T(n/2) + n ...(1)
と表わせることになります。
ここで、 n/2 も偶数なら同様に
T(n/2) = 2・T((n/2)/2) + n/2
= 2・T(n/4) + n/2
であり これを (1) に代入すると
T(n) = 2・(2・T(n/4) + n/2) + n
= 2・2・T(n/4) + n + n
= 4・T(n/4) + 2n
以下、 n/4が偶数なら、n/8が偶数なら... と 続きます。


n=2^m (mは0以上の整数) とすると、
T(n) = T(2^m)
= 2^1・T(2^(m-1)) + 1・n
= 2^2・T(2^(m-2)) + 2・n
= 2^3・T(2^(m-3)) + 3・n
...
= 2^m・T(2^(m-m)) + m・n

ここで、
・T(2^(m-m)) = T(1) = 0 '計算の必要無し
・m=log n
なので、
∴ T(n)=n・log n

この回答へのお礼

わかりやすい解説、大変感謝いたします。
ただ、一つだけ質問したいことがございます。
(N/2)^2+(N/2)^2は私の質問の「」内の文章のどの部分に当たるのでしょうか？

どうかよろしくお願い致します。

お礼日時：2022/04/05 06:47

No.2 回答者： Tacosan 回答日時： 2022/04/02 00:34

なにをいっているのかわからない.... 「NｘNの正方行列の行列式より、出来たN^2を2^2で割って偶数と奇数に分ける」ってどういうことだ. どんな「正方行列」の「行列式」を考えて, それから「N^2」がどうして「出来」て, それを「2^2で割」るとなんで偶数と奇数に「分ける」ことになるんだよ.

ちょうどいいのが
https://en.wikipedia.org/wiki/Butterfly_diagram
にあったのでもうこれに丸投げしとこう.

この回答へのお礼

>> 「N^2」がどうして「出来」て, それを「2^2で割」るとなんで偶数と奇数に「分ける」ことになるんだよ.

私が誤った理解をしている事はわかりました。ならば、(N/2)²+(N/2)²=N²/2が何を表しているのか正しい答えを教えて頂けないでしょうか？

お礼日時：2022/04/02 07:13

No.1 回答者： Tacosan 回答日時： 2022/04/01 02:32

まず「2回の DFT にわかる」としても, その作業量は正確にいうと

(N/2)^2 + (N/2)^2 = N^2/2
にはならない. 実際にはもうちょっと作業が必要になる.

と書いておくけどそもそもこの (N/2)^2 が何を表しているのかわかってる?

この回答へのお礼

ありがとうございます。
>> この (N/2)^2 が何を表しているのかわかってる?
間違っているかもしれませんが答えさせて頂きます。
NｘNの正方行列の行列式より、出来たN^2を2^2で割って偶数と奇数に分ける為であると考えています。
違う場合は何かヒントを頂けないでしょうか？


>> 実際にはもうちょっと作業が必要になる.
差し支えなければどんな作業が必要かどうか教えて頂けないでしょうか？

真に理解したいのでどうかよろしくお願いします。

お礼日時：2022/04/01 03:27