高速フーリエ変換でデータ数が２のべき乗でない時

質問

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

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

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

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

回答No.2

sinisorsa · ベストアンサー

離散フーリエ変換は、信号が周期的であることを前提としています。
離散フーリエ変換でのデータ数Ｎは、離散時間信号の周期に当たります。変換の結果は線スペクトルとなります。
Ｎ＝５０００がその信号の１周期なのでしょうか。
もしそうならば、４０９６にすれば、誤差が大きくなるでしょう。
Ｎ＝５０００で変換すべきです。この場合にも高速アルゴリズムが
存在します。＃１の方のとおりです。
ＦＯＲＴＲＡＮの時代には、パッケージがありました。
ＮはＮ＝２＾ｍ＊３＾ｎ＊５＾ｋ＊７＾Ｌだったと思います。

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

お礼

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

>>データ数が５０００ならば、Ｎは８１９２とし足りないデータには、
>>０を詰めます。

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

回答No.3

sinisorsa

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

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

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

回答No.1

Tacosan

実際のところ, 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 にしたままでもそれほど時間はかからないのではないでしょうか.

お礼

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