質問編集履歴
1
か
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -4,3 +4,46 @@
|
|
|
4
4
|
また、なぜ偶数行と奇数行に分ける事でさらに早く計算処理が出来るとわかったのでしょうか？
|
|
5
5
|
|
|
6
6
|
どうかよろしくお願い致します。
|
|
7
|
+
|
|
8
|
+
|
|
9
|
+
補足です。
|
|
10
|
+
なぜ高速フーリエ変換(FFT)はO(n*log n)で計算できるのでしょうか？
|
|
11
|
+
どうか理由を詳しく教えて下さい。
|
|
12
|
+
|
|
13
|
+
以下の「」はFFT
|
|
14
|
+
を説明したものですが、
|
|
15
|
+
「」のどの部分がO(n*log n)を、表すのでしょうか？
|
|
16
|
+
|
|
17
|
+
|
|
18
|
+
「
|
|
19
|
+
Ck = (1/N)∑[m=0→N-1] fm･e^(-jkmωD) (k = 0, 1, 2, …… , N-1)...②
|
|
20
|
+
ω = 2π/T = 2π/ND、j は虚数単位
|
|
21
|
+
|
|
22
|
+
と定義したものを
|
|
23
|
+
|
|
24
|
+
N･Ck = Xk = ∑[m=0→N-1] fm･e^(-jkmωD) (k = 0, 1, 2, …… , N-1) ･････(#)
|
|
25
|
+
|
|
26
|
+
と書き変えたものに過ぎない。DFTを高速フーリエ変換FFTに変えるにはバタフライ演算というややこしいものを理解しないといけない。はっきり言って掲示板でチョコチョコ説明できるようなものではない。
|
|
27
|
+
離散フーリエ変換は、数学者の書いたフーリエ解析の本にはまず載っていないので、信号処理関係の本を探して勉強されたい。
|
|
28
|
+
|
|
29
|
+
W^(km) = e^(-jkmωD) として N = 4 のとき(#)を展開すれば
|
|
30
|
+
X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
|
|
31
|
+
X1 = f0･W^0 + f1･W^1 + f2･W^2 + f3･W^3
|
|
32
|
+
X2 = f0･W^0 + f1･W^2 + f2･W^4 + f3･W^6
|
|
33
|
+
X3 = f0･W^0 + f1･W^3 + f2･W^6 + f3･W^9
|
|
34
|
+
となるがW^(km)の性質から
|
|
35
|
+
X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
|
|
36
|
+
X1 = f0･W^0 + f1･W^1 - f2･W^0 - f3･W^1
|
|
37
|
+
X2 = f0･W^0 - f1･W^0 + f2･W^0 - f3･W^0
|
|
38
|
+
X3 = f0･W^0 - f1･W^1 - f2･W^0 + f3･W^1
|
|
39
|
+
と簡単になる。しかし、これでも16回の掛け算が必要なのは変わらない。そこで上の式を奇数行と偶数行に分け
|
|
40
|
+
X0 = f0･W^0 + f1･W^0 + f2･W^0 + f3･W^0
|
|
41
|
+
X2 = f0･W^0 - f1･W^0 + f2･W^0 - f3･W^0
|
|
42
|
+
X1 = f0･W^0 + f1･W^1 - f2･W^0 - f3･W^1
|
|
43
|
+
X3 = f0･W^0 - f1･W^1 - f2･W^0 + f3･W^1
|
|
44
|
+
ここからは上の展開式を行列で表さないとわかりにくいのだが、メンドーなので省略する。とにかく上のように行を入れ替えると
|
|
45
|
+
X0 = W^0(f0+f2) + W^0(f1+f3)
|
|
46
|
+
X2 = W^0(f0+f2) - W^0(f1+f3)
|
|
47
|
+
X1 = W^0(f0-f2) + W^1(f1-f3)
|
|
48
|
+
X3 = W^0(f0-f2) - W^1(f1-f3)
|
|
49
|
+
のように8個の掛け算だけで済むように変形できる。これがバタフライ演算であり、FFTがDFTより速い理由である。」
|