• ベストアンサー

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

お世話になります。 仕事でFFTのプログラムを内製しようとしています。 初心者なので、他の人（今は退社していません）が昔作ったFFTのプログラムを参考にしようと思いそれを解読中です。 そのプログラムはC言語で書かれていますが、「ガウスの消去法を使って連立方程式を解く」というプロセスが含まれています。 私の認識では、FFTではガウスの消去法を使う事はないので、私が見たプログラムはFFTではなくDFTのプログラムではないかと思っています。 FFTのプログラムでガウスの消去法を使う事はあるのでしょうか？勉強中なのと、周りに知っている人がいないため、どなたか教えて下さい。 よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • kmee
  • ベストアンサー率55% (1857/3366)
回答No.4

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でも動作すると思います。 ただし、メモリ量や計算速度が実用的なレベルになるかどうかまではわかりません。

my7goh
質問者

お礼

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

その他の回答 (3)

回答No.3

>ちなみに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ライブラリも当然付いています。

my7goh
質問者

お礼

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

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

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

my7goh
質問者

補足

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

  • kmee
  • ベストアンサー率55% (1857/3366)
回答No.1

それって、FFT以外の計算も含まれた、総合的な「数値演算ライブラリ」とかではないでしょうか? または ・方程式を解く→その結果を使って作った数列をFFT とか ・FFT→変換結果を最小二乗近似→そのために連立方程式を解く とか、全体の流れの中で使用するけど、FFTとは独立したもの、だとか。、

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 物理学

関連するQ&A

  • C言語プログラムの離散フーリエ変換

    C言語プログラムの離散フーリエ変換について教えてください。「C言語による画像再構成の基礎」という本のプログラムをもとに二次元画像をDFT（通常の離散フーリエ変換）→InveresFFT（逆高速フーリエ変換）すると画像が左右反転、上下反転してしまいます。DFT→InverseDFTやFFT→InverseFFTだとそのようにはなりません。通常のDFTとFFTのアルゴリズムの違いからしかたがないのでしょうか？それともプログラムの変更で修正できるのでしょうか？どうしてもDFT→InverseFFTでがぞうをもとに戻したいのです。 サンプルページ　http://www.iryokagaku.co.jp/frame/03-honwosagasu/370/370-dl.html P4-14fourier2d1d.c (離散フーリエ変換DFT）　　 P4-15fft.c（高速フーリエ変換）プログラムです

  • 連立方程式

    C言語で反復法の「ヤコビ法」と「ガウス・ザイデル法」、消去法を用いて連立方程式を解くプログラムを作りたい。 また、プログラムは任意の元数に対応できるように作りたい。 分かる方がいましたら、回答よろしくお願いします。

  • 連立方程式の解法

    有限要素法のプログラムにおいて、連立方程式を解く方法にガウスの消去法を使用しています。ガウスの消去法の他に、行列を解く方法や計算精度が上がるテクニックなどあれば教えてほしいのですが‥‥

  • ガウスの消去法

    1000変数の連立一次方程式をガウスの消去法で解いたとき、計算時間は１０秒だったとする。このとき１００００変数の連立一次方程式をガウスの消去法で解くのにどれぐらいの計算時間がかかるのかという疑問について、いったい何秒になるのでしょうか？オーダ(n^3/3)に１００００を入れればいいのでしょうか？

  • FFTで小数点以下のsin周波数を検出することはできるのでしょうか？

    FFTで小数点以下のsin周波数を検出することはできるのでしょうか？ 私はFFTどころか「フーリエの冒険」を読んででやっとDFTがなんたるかを理解できた人間なんですが、 今どうしてもC言語のFFTのプログラムを必要としています。 で、今の私ではFFTのプログラムを作ることはできないと思ったので インターネットからプログラムをコピーして使用していたのですが、 私が調べた限りだと小数点以下のsin周波数を正常に検出できるようなFFTのプログラムはみつかりませんでした。 ですので、詳しい人がいたら小数点以下のプログラムがあるところを教えてください。お願いします。 あと気になる点があるのですが、 http://mak-oto.cocolog-nifty.com/blog/2009/10/post-84b1.html ↑のURL先の記事を読んで、小数点以下の周波数をどう検出したらいいのかよく分からなくなりました。 そこについての補足もできればよろしくお願いします。

  • 連立一次方程式を解くプログラムについて

    数値計算の本を見たら必ず載っている連立1次方程式の解法ですが、どのようなタイプの行列でも解くことができるものにはどのような解法があるでしょうか。もちろん、解くことができる範囲でということではあります。その意味でガウスの消去法（ピボット付）になるでしょうか。ガウスの消去法は解き方に基本的な制約はないですね。一方、共役勾配法の説明を見ると"対称正定値行列の場合、..."となっており、その範囲でしか考えていないということでしょうか。そうなるとかなり絞られることになってしまいます。任意の行列は変換して対称正定値に変換できる、ということでもないと思いますが。 有限要素法に関連した連立方程式解法についても書籍1冊分の解説とかありそうですが。高速化のために長い解説があったとしても前提によって使える範囲が狭いものが多いように思えるのですが。よろしくお願いします。

  • 連立一次方程式を解くプログラム

    すこし煩雑な(21×11です)の連立一次方程式を解くプログラムを作りたいのですが 何か良い文献、HPなどは無いでしょうか？ いろいろなものを見ましたが大体縦横が同じ(ｎ次元？)の 計算のヒントみたいなのしか見つけれませんでした。 プログラムはほとんどやったことが無いので、 ソースなどが公表されていてそれをちょっと書き換えれば 目的のものがつくれるというのが理想ですが・・・。 解法はガウスジョルダンとかガウスサイデル あるいは他にもっとよいものがあればそちらで構いません。 また、連立一次方程式のちゃんとした答え(言い方悪いですね)が求まらない場合、 近似解を算出することになると思うのですが これはどういった基準で「解」とされるのでしょうか？ 計算の反復回数とかでしょうか？ まとまりのない質問ですがよろしくお願いします。 何かあれば補足をお願いします。

  • ガウスの消去法

    次の連立方程式の解を、ガウスの消去法で出来るだけ精度よく求めたいです 0.001x+y=1 x+2y=3

  • 高速フーリエ変換(FFT)のプログラム

    高速フーリエ変換(FFT)のプログラム 高速フーリエ変換のプログラムが必要になり、visual c++で作成しています。 http://www.kiso.tsukuba.ac.jp/~watanabe/FFT.htm こちらのサイトの一番下のプログラムを参考にして作成しています。 ここで質問なのですが信号データが８点のプログラムが上記のサイトにはあり、私は作成したプログラムが正しいかどうかチェックするため４点の信号データのFFTを求めたいのですが、以下のようにx0=2,x1=2,x3=8,x4=-4の値をフーリエ変換するプログラムにしたところ、この4点フーリエ変換の正規の値と、このプログラムの出力値が違ってしまいます。私の知識不足も否めませんがどこが間違っているのかわからずこまっています。 よろしければ教えてください。 void four1(float datar[],float datai[],unsigned long nn, int isign){ unsigned long n,mmax,m,j,istep,i; double wtemp,wr,wpr,wpi,wi,theta; float tempr,tempi; n=nn; j=0; for (i=0;i<n ;i++) { if (j > i) { SWAP(datar[j], datar[i]); SWAP(datai[j], datai[i]); } m=n >> 1; while (m >= 1 && j > m) { j -= m; m >>= 1; } j += m; } mmax=1; while (n > mmax) { istep=mmax << 1; theta=isign*(6.28318530717959/istep); wtemp=sin(0.5*theta); wpr = -2.0*wtemp*wtemp; wpi=sin(theta); wr=1.0; wi=0.0; for (m=0;m<mmax;m++) { for (i=m;i<n;i+=istep) { j=i+mmax; tempr=wr*datar[j]-wi*datai[j]; tempi=wr*datai[j]+wi*datar[j]; datar[j]=datar[i]-tempr; datai[j]=datai[i]-tempi; datar[i] += tempr; datai[i] += tempi; } wr=(wtemp=wr)*wpr-wi*wpi+wr; wi=wi*wpr+wtemp*wpi+wi; } mmax=istep; } } void realft() { float datar[4]={2.0,2.0,8.0,-4.0}; float datai[4]={0.0,0.0,0.0,0.0}; int i; four1(datar,datai,4,-1); for(i=-1;i<3;i++){ printf("i = %d:\tReal: %f, \tImag: %f\n", i, datar[i]/4,datai[i]/4); } }

  • C言語によるディジタル信号処理のお勧めの本やサイト

    C言語を使ったディジタル信号処理でFFT，DFT，ハミング窓，ギブスの現象，FIR(IIR)フィルタなどのいろいろなアルゴリズム，プログラムが載っていてしかも分かりやすかったり，有名な本ってありますか？ また，何故その本がお勧めのかの理由も聞かせていただければ大変有難く思います。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する