FFT（高速フーリエ変換）の考え方

質問

///////////質問(1)////////////////////

離散フーリエ変換が以下の式で表せることは理解できます。

　 　　 N-1　　 　 　　nk 　 　　 　 　 -2πi / N
Ａ ＝　 Σ　　ａ 　 Ｗ ，　　 Ｗ ＝ ｅ 　
　n 　 k=0　　　k 　　 　　 　 　 　 　 　

n：基本周波数のn倍
N：データ数

ここで、実際のプログラム上では、
(1)akに サンプリングしたデータとサンプリング周期を掛けたもの を入れ、
(2)それをWと掛けあわせて行くと思います。
では、Wには何を代入すればいいのでしょうか？

Wを実部・虚部にわける、もしくは、 絶対値・位相にわけて計算する方法で
あっているのでしょうか？
Anは周波数n成分の面積を表していると思うのですが、面積に虚数概念がで
てくるのも変な話なような気がして、質問させていただきました。

///////////質問(2)////////////////////

　　　N/2-1　　　　2nk　　　n　N/2-1　　　　　2nk
Ａ　＝　Σ　ａ　　Ｗ　＋　Ｗ　　Σ　　ａ　　Ｗ
　n　　k=0　　2k　　　　　　　　k=0　　2k+1

Cooley-Tukey 型 FFTは質問(1)の式を上記のように２項に分解することで、
計算を減らすことができるとのことです。

しかし、私には理解できません。
左側の項でN/2回の掛け算を行い、右側の項でもN/2回の掛け算を行うのでは、
結局式を分解しただけで、何も変わっていないように思えます。

どのように考えればいいのでしょうか？
アドバイスよろしくお願いします。

回答No.6

keyguy

実数乗算で乗算回数を示すと
複素数乗算は実数乗算4回分だから

FFTの場合
テーブルはW^0～W^(N/2-1)を求めればいいから
(N/2-2)×4回
メイン計算1段分は
N/2×4回
全部でlog2(N)段だから
N/2×log2(N)×4回
結局総計
(N/2×log2(N)+(N/2-2))×4回

非FFTの場合は
テーブルはW^0～W^(N-1)を求めればいいから
(N-2)×4回
メイン計算は
N×N×4
で総計
(N^2+N-2)×4

N=8192とすると
非FFTの計算時間/FFTの計算時間=
67100670回/229368回=292.5459088倍

したがって
FFTで1分かかったとすると
非FFTでは5時間弱かかる事になる
8192でも驚異的な差です
16384の場合はどのようになるか補足してください

お礼

私の説明不足のせいで、私の求めている内容と回答内容との間にずれがあり、皆様のアドバイスからは理解することができませんでした。
としても、複数回の回答、本当にどうもありがとうございました。

回答No.5

keyguy

細かい話ですが
バタフライ1個の計算は（乗算2回と書いたが本当は）複素数乗算1回ででき2つのサンプルが求まるので少し修正すると
テーブル計算まで含めたFFTの乗算回数は

N・log2(N)/2+N/2

です
さらに計算量の差は大きくなります
またいろんな工夫をする事によりさらに1/2にするテクニックもある
やや複雑な構成になるが余弦変換として求める計算方法もある

回答No.4

keyguy

ややこしいので複素数の掛け算を1回と数えましょう
相対比較ならば比がでるので問題ないから

N=8の場合には
まともにやると
一つのanを求めるのに8回の乗算がいりますね
よってnが8通りなので8×8=64回
なおan×W^kはあらかじめW^kを求めておく事にして
1回の乗算とします
N=8だとこの時間は馬鹿にならないがNが大きくなるとほとんど寄与しません

FFTでやると
3段の変換になりますが
たすきがけバタフライは2回の乗算ですが2個もとまるので
1段の変換で8回の乗算階数になります
よって乗算回数は8×3=24です

この場合には3倍弱ですが

一般には
まともにすると
乗算回数:N^2
で
FFTだと
乗算回数:N×log2(N)
ですから
N=8192の場合は630倍の差です

テーブルはWをk回かければ
W,W^2,W^3，・・・W^(k-1)
が求まるので
テーブルを求めるのにFFTに必要な乗算回数はN/2回です

よってテーブルまで含めた回数は
FFTの場合
N×log2(N)＋N/2
です
8192だと4096回増えるだけで3.8%増です
非FFTだともっと大きなテーブルになります

回答No.3

natsumitoka

＞Cooley-Tukey 型 FFTは質問(1)の式を上記のように２項に分解することで、
計算を減らすことができるとのことです。

これは，基数2の時間間引きFFTのことです．
はっきり言って，FFTはシグナルフローに尽きると思います．2項間のバタフライ演算が理解できれば後は楽だと思います．

ちなみに，検索すればたくさん引っかかりますよ．

お礼

回答ありがとうございます。

インターネットで検索して、いろいろサイトを見て回ったのですが、理解できませんでした。。。

他の方の補足部分に、理解できない部分をもう少し詳しく書きましたので、アドバイスよろしくお願いします。

回答No.2

keyguy

計算量が如何に減るかは計算してみれば分かります
256個のFFTを使わないで計算する場合に
256^2=65536回の乗算が必要です
FFTを使うと
256×log2(256)=4096回の乗算が必要です(1/16)
実際には256でころではなく8192以上なのですからこの差は雲泥の差です(1/630)
なお指数算はテーブルを見ながらするのでほとんど寄与せず数には含めません
(FFTのテーブルは非FFTに比べて極めて小さいがこの点も有利)
複素数乗算ですから上の双方2，3倍に増えます

FFTは単に1つのFFTを2つに分解する事が基本です
後は逐次的に2個のFFTにまで分解するのです
だから1つを2つにするところを理解すれば分かるはずです
結果から分解していくか対象から分解していくかによって2通りあるのです

補足

回答どうもありがとうございます。
FFTを使うと計算回数が対数的に減らせるらしいんですよね。。。
ただ、私にはそれが理解できないのです。

以下少し長くなりますが、例を挙げます。

ここにN=8個のサンプリング値があるとします。
a0,a1,a2,a3,a4,a5,a6,a7

A0 =　　　(a0*W0 + a2*W0 + a4*W0 + a6*W0) 　←A0偶数組
　　 + W0*(a1*W0 + a3*W0 + a5*W0 + a7*W0) 　←A0奇数組

A1 =　　　(a0*W0 + a2*W2 + a4*W4 + a6*W6) 　←A1偶数組
　　 + W1*(a1*W0 + a3*W2 + a5*W4 + a7*W6) 　←A1奇数組

A2 =　　　(a0*W0 + a2*W4 + a4*W0 + a6*W4) 　←A2偶数組
　　+ W2*(a1*W0 + a3*W4 + a5*W0 + a7*W4) 　←A2奇数組

A3 =　　　(a0*W0 + a2*W6 + a4*W4 + a6*W2) 　←A3偶数組
　　 + W3*(a1*W0 + a3*W6 + a5*W4 + a7*W2) 　←A3奇数組

Ａ０～Ａ３までの掛け算の回数
計36回　＝　偶数組16回 + 奇数組 16回 + 外に出したWとの掛け算4回
※Ｗの使いまわしはできていますが、そんなに計算回数は減っていないと思います。

A4 =　　　(a0*W0 + a2*W0 + a4*W0 + a6*W0) 　←A0偶数組と同じ
　　 + W4*(a1*W0 + a3*W0 + a5*W0 + a7*W0) 　←A0奇数組と括弧の中は同じ

A5 =　　　(a0*W0 + a2*W2 + a4*W4 + a6*W6) 　←A1偶数組と同じ
　　 + W5*(a1*W0 + a3*W2 + a5*W4 + a7*W6) 　←A1奇数組と括弧の中は同じ

A6 =　　　(a0*W0 + a2*W4 + a4*W0 + a6*W4) 　←A2偶数組と同じ
　　+ W6*(a1*W0 + a3*W4 + a5*W0 + a7*W4) 　←A2奇数組と括弧の中は同じ

A7 =　　　(a0*W0 + a2*W6 + a4*W4 + a6*W2) 　←A3偶数組と同じ
　　 + W7*(a1*W0 + a3*W6 + a5*W4 + a7*W2) 　←A3奇数組と括弧の中は同じ

Ａ５～Ａ７までの掛け算の回数
計4回　＝　偶数組0回 + 奇数組 0回 + 外に出したWとの掛け算4回
※私の読んだ本にはここが0回と書いていました。　なぜでしょう？？？

総合計　掛け算回数　40回

確かに、計算回数が減っていることは減っています。
しかし、Ａ５～Ａ７で括弧の外側に出したＷと括弧内の掛け算が残っているので、
劇的には計算回数が減りません。

私が計算したところによると、この方法では計算回数は以下にまでしか減りません。
(N^2)/3 + 2N

本来のFFTはN×log2(N)まで計算回数が減るとのことですので、私の考え方が間違っているのでしょう・・

書籍やインターネットを参考にしながら考えてはいるのですが、依然理解できません。
アドバイスよろしくお願いします。m(_ _)m

回答No.1

JaritenCat

wは、オイラーの定理 e^(ix) = cos(x)+i・sin(x) を使って実数部と虚数部を分けて計算します。
akはk番目のデータですね。
Anの絶対値のlogを取ればパワースペクトルを計算できます。

FFTはw^(2nk)を使いまわしして計算量を減らします。

お礼

回答ありがとうございます。

Anは絶対値を取ればいいのですね。
どうもありがとうございました。

なお、FFTの考え方の方ですが、いまだに理解できません。
お時間＆心の余裕がありましたら、もう少し詳しくアドバイスよろしくお願いします。