FFT（高速フーリエ変換）のプログラム

質問

お世話になります。

仕事でFFTのプログラムを内製しようとしています。

初心者なので、他の人（今は退社していません）が昔作ったFFTのプログラムを参考にしようと思いそれを解読中です。

そのプログラムはC言語で書かれていますが、「ガウスの消去法を使って連立方程式を解く」というプロセスが含まれています。

私の認識では、FFTではガウスの消去法を使う事はないので、私が見たプログラムはFFTではなくDFTのプログラムではないかと思っています。

FFTのプログラムでガウスの消去法を使う事はあるのでしょうか？勉強中なのと、周りに知っている人がいないため、どなたか教えて下さい。

よろしくお願いします。

回答No.4

kmee · ベストアンサー

http://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
ここで、
e^ix=cos(x)+i * sin(x) を使って
f_real(j) + i*f_imag(j)
= Σ((x_real(k) + i * x_imag(k))*(cos(-2*π*(j^k)/n) + i*sin(-2*π*(j^k)/n))
※ -2*π*(j^k)/n=θとして、上記式を展開
= Σ(x_real(k)*cosθ + i * x_imag(k)*cosθ + i*x_real(k)*sinθ - x_imag(k)*sinθ )
∴ 実数部と虚数部に分けて
f_real(j)= Σ(x_real(k)*cosθ- x_imag(k)*sinθ )
f_imag(j) = Σ( x_imag(k)*cosθ + x_real(k)*sinθ )

つまり、DFTは、ひたすら「θを計算→sinθ,cosθを計算→掛けて足す」 を繰り返すだけです。
(三角関数の性質(周期等)を利用して、先に使用するcos,sinを計算しておく、等といった工夫を加えることもできますが)

FFTは、DFTの特殊なケース(xの数 n が2のべき乗個のとき)に、対称性等を利用して計算を減らしたものです。

どちらにも、多元連立方程式を解くようなものは出てきません。

もう一度、処理の流れを確かめてください。
・その消去法は、実際にプログラムで使用されているのでしょうか?
定義されているだけで、呼び出されていない(実行されていない)、ということは無いでしょうか?
・そのプログラムは、純粋にFFTを計算するだけのものでしょうか?
一連の処理の中にFFTがある、というものではありませんか?
生のデータ→前処理→FFT→後処理→欲しいデータ
という流れで、前処理や後処理に使われているだけではないでしょうか?

○VBA
プログラムを作ること自体は問題ありません。
http://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
にVisual Basicの例が載っていますが、ほぼここままでVBAでも動作すると思います。

ただし、メモリ量や計算速度が実用的なレベルになるかどうかまではわかりません。

お礼

お世話になります。お礼が遅くなり申し訳ありません。
あれからよく勉強して確認してみました。
FFTとDFTについては仰る通りである事確認し理解出来ました。
どうもありがとうございました！
消去方はDFTで求めたピークを2次式で近似する時に用いていたもので、周波数解析に直接関係あるものではありませんでした。
丁寧にご教示いただきありがとうございました！

回答No.3

sakadoneko

>ちなみにFFTはC言語やVBでコード化されているものが多いように思うのですが、
>VBAでやっても問題ないのでしょうか？
問題ありません。

VBAのメリット：
　Excelワークシートにデータを書き出せば表やグラフを簡単に作れる
　なのでデバッグも簡単

デメリット：
　計算が遅い
　FFT呼出などはExcelのバージョンによって動かなくなったりする
　割り込みとか、VBより不自由な点もある？

ExcelだとFFT機能がすでにあるので、それをVBAから呼び出す手もあります。
ただしmy7gohさんの場合は、まだそのソフトの出力データの流れを把握されてないようなので、そのソースをそのまま移植した方が早いかも知れませんが。

ExcelのFFT機能を使うには、アドインで分析ツールを追加する必要があります。
Excel2003ならツール：アドインで「分析ツール」と「分析ツール-VBA」を追加します。
するとツール：分析ツール：フーリエ解析で、手動でFFTできます。
http://homepage1.nifty.com/gfk/fourier-transform.htm

自動でFFTさせる方法を調べるには、ツール：マクロ：新しいマクロの記録、でFFT操作をVBAで出力させてみると良いでしょう。
http://www.gizcollabo.jp/vbtomo/log/archive/choshoqa_19973_0.html
http://www.riam.kyushu-u.ac.jp/gikan/report/12/001-mada.pdf

VBAで書いたFFTを公開している方もいらっしゃいます。
そのほうがバージョンによって動かなくなるリスクが減って良いかも知れません。
http://blog.livedoor.jp/sce_info3-craft/archives/7774799.html

VBA以外では、MATLABやScilabといった数値計算用の言語だと科学技術計算ライブラリが豊富で、FFTライブラリも当然付いています。

お礼

お世話になります。お礼が遅くなり申し訳ありません。
結局勉強して自分でFFTのプログラムを作りました。
VBAとCで作って動くことは確認出来ました。
仰る通りVBAだと簡単でしたが計算速度が遅いのでCで作りこんで行こうと思います。
親切に教えていただき誠にありがとうございました。

回答No.2

Tacosan

う～ん, DFT にしても消去法は出てこないんだけどなぁ....

補足

DFTでも消去法は出てこないんですか？
よく勉強してみます。
ちなみにFFTはC言語やVBでコード化されているものが多いように思うのですが、VBAでやっても問題ないのでしょうか？プログラム言語によって善し悪しがあるのでしょうか？？

回答No.1

kmee

それって、FFT以外の計算も含まれた、総合的な「数値演算ライブラリ」とかではないでしょうか?

または
・方程式を解く→その結果を使って作った数列をFFT
とか
・FFT→変換結果を最小二乗近似→そのために連立方程式を解く
とか、全体の流れの中で使用するけど、FFTとは独立したもの、だとか。、