gooドクター有料プランが1ヶ月間無料!

こんにちは。現在、フーリエ変換について勉強しているのですが、ちょっとわからないことがあったので質問させていただきました。

質問内容は高速フーリエ変換についてで、cooley&tukeyのアルゴリズムを利用すると、データが2の冪乗個のときは計算量をО(NlogN)に減らせる事ができるというものでした。

しかしデータが2の冪乗個でないとき。例えばN=5000くらいのときはデータを切り取って無理やりN=4096(=2^12)みたいな感じにすれば良いんですよね?
やっぱりその時って、N=5000で通常の離散フーリエ変換したときと周波数値に誤差が出ると思うのですが、それはどうやったら計算できるのでしょうか。。。

どなたかご教授していただければ幸いです。

gooドクター

A 回答 (3件)

離散フーリエ変換は、信号が周期的であることを前提としています。


離散フーリエ変換でのデータ数Nは、離散時間信号の周期に当たります。変換の結果は線スペクトルとなります。
N=5000がその信号の1周期なのでしょうか。
もしそうならば、4096にすれば、誤差が大きくなるでしょう。
N=5000で変換すべきです。この場合にも高速アルゴリズムが
存在します。#1の方のとおりです。
FORTRANの時代には、パッケージがありました。
NはN=2^m*3^n*5^k*7^Lだったと思います。

もうひとつの考え方は、有限持続時間信号のフーリエ変換としての
適用です。これは、連続スペクトルとなります。データ数Nは
スペクトルの分解能に関係します。サンプリング周波数をNで割った
ものが周波数分解能となります。
実際のデータよりも2倍程度のNを使うことが多いと思います。
データ数が5000ならば、Nは8192とし足りないデータには、
0を詰めます。これならば、2のべき乗のNを選べます。
この場合、逆変換は周期的な拡張が行われることに注意が必要です。
    • good
    • 1
この回答へのお礼

ご回答ありがとうございますm(_ _)m
N=5000が1周期であるとかは全く考えていませんでした^^;すいません。

>>データ数が5000ならば、Nは8192とし足りないデータには、
>>0を詰めます。

これは仮にデータを配列a[8191]に格納するとしたら、a[0]~a[4999]までは
普通にデータを格納し、a[5000]~a[8191]には0を格納するという事でしょうか?

お礼日時:2009/10/29 17:03

#2です。


>これは仮にデータを配列a[8191]に格納するとしたら、a[0]~a[4999]までは
普通にデータを格納し、a[5000]~a[8191]には0を格納するという事でしょうか?

そうです。
サンプリング周波数をFsとしたとき、Δf=Fs/8192間隔で
スペクトルが計算されます。

なお、データが本来もっと長時間のデータを5000個だけ
切り取ったものである場合には、窓関数を掛け算すると
データの両端での切り取りの影響が小さくなります。
窓関数(Window function)には、Hamming、Hanning,Blackmanなどが
あります。
完全な孤立波(有限持続信号)なら窓を掛ける必要はありません。
    • good
    • 3

実際のところ, N = mn と 2数の積に分解できれば N点のフーリエ変換は m点のフーリエ変換 (のようなもの) と n点のフーリエ変換 (のようなもの) を連続して行うことで求まり, その時の計算量は O(N*(m+n)) となります. これを繰り返すと, 結局 N = p1^e1 p2^e2 ... pk^ek と素因数分解できたときに計算量は O(N(e1 p1 + e2 p2 + ... + ek pk)) と表されることになります.


N = 2^n のときにこの分解が最も効率よくなり, O(N log N) となります. そうでないときには効率が落ちるのですが, それはそれでそれなりに計算できます.
例えば N = 5000 = 2^3 * 5^4 だと 5点に対するフーリエ変換を 4回, 2点に対するフーリエ変換を 3回行うことになり, その時の計算量はおよそ 5000*(5*4+2*3) = 5000*26 に比例します. 一方 N = 4096 に対する高速フーリエ変換は 4096*24 に比例します.
ということで「データ 1個当たりの所要時間」は大して変わらないことが分かると思います. つまり, 普通の高速フーリエ変換とは違うものの, 「5点に対するフーリエ変換」を作ることさえできれば, 点数を 5000 にしたままでもそれほど時間はかからないのではないでしょうか.
    • good
    • 1
この回答へのお礼

データが2^nでなくとも小さめの素因数があれば計算量を減らすことができるということでしょうか。大変参考になりました。有難うございますm(_ _)m

お礼日時:2009/10/29 16:55

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング