こんにちは。現在、フーリエ変換について勉強しているのですが、ちょっとわからないことがあったので質問させていただきました。
質問内容は高速フーリエ変換についてで、cooley&tukeyのアルゴリズムを利用すると、データが2の冪乗個のときは計算量をО(NlogN)に減らせる事ができるというものでした。
しかしデータが2の冪乗個でないとき。例えばN=5000くらいのときはデータを切り取って無理やりN=4096(=2^12)みたいな感じにすれば良いんですよね?
やっぱりその時って、N=5000で通常の離散フーリエ変換したときと周波数値に誤差が出ると思うのですが、それはどうやったら計算できるのでしょうか。。。
どなたかご教授していただければ幸いです。
No.3
- 回答日時:
#2です。
>これは仮にデータを配列a[8191]に格納するとしたら、a[0]~a[4999]までは
普通にデータを格納し、a[5000]~a[8191]には0を格納するという事でしょうか?
そうです。
サンプリング周波数をFsとしたとき、Δf=Fs/8192間隔で
スペクトルが計算されます。
なお、データが本来もっと長時間のデータを5000個だけ
切り取ったものである場合には、窓関数を掛け算すると
データの両端での切り取りの影響が小さくなります。
窓関数(Window function)には、Hamming、Hanning,Blackmanなどが
あります。
完全な孤立波(有限持続信号)なら窓を掛ける必要はありません。
No.2ベストアンサー
- 回答日時:
離散フーリエ変換は、信号が周期的であることを前提としています。
離散フーリエ変換でのデータ数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を選べます。
この場合、逆変換は周期的な拡張が行われることに注意が必要です。
ご回答ありがとうございますm(_ _)m
N=5000が1周期であるとかは全く考えていませんでした^^;すいません。
>>データ数が5000ならば、Nは8192とし足りないデータには、
>>0を詰めます。
これは仮にデータを配列a[8191]に格納するとしたら、a[0]~a[4999]までは
普通にデータを格納し、a[5000]~a[8191]には0を格納するという事でしょうか?
No.1
- 回答日時:
実際のところ, 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 にしたままでもそれほど時間はかからないのではないでしょうか.
データが2^nでなくとも小さめの素因数があれば計算量を減らすことができるということでしょうか。大変参考になりました。有難うございますm(_ _)m
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
-
ゆるやかでぃべーと タイムマシンを破壊すべきか。
これはディベートの論題だと仮定したうえでの回答お願いします。あなたは、その末にタイムマシンを壊してしまうのか、使い道を探すのかどうかを考えてもらいたいです。
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
Excelで4096点以上のFFTの方法
その他(Microsoft Office)
-
信号長が2の累乗以外のFFTがやりたいです
数学
-
FFTの結果ついて
C言語・C++・C#
-
-
4
フーリエ変換のデータの補間について
数学
-
5
EXCELにてローパスフィルタを作成する
その他(教育・科学・学問)
-
6
窓関数(方形窓)について
その他(自然科学)
-
7
エクセルでハイパスフィルタをかけたいのですがどのようにすればよいですか?
工学
-
8
フーリエ変換後の負の周波数成分の扱いについて
数学
-
9
FFT・PSDの縦軸は何を意味するのでしょう?
物理学
-
10
エクセルでノイズ値を除去する方法。
数学
-
11
離散フーリエ変換(DFT)の実数と虚数
数学
-
12
高速フーリエ変換とフーリエ変換の違い
物理学
-
13
FFTのDC成分って、なんで大きくなるんですか?
物理学
-
14
エクセル2010 グラフの軸の最大値最小値をセル参照する
Excel(エクセル)
-
15
wavファイルをcsvファイルに変換する。
フリーソフト
-
16
行列 線形代数 diag"って何ですか?"
数学
-
17
二つのデータの波形が似てるかどうかの判定方法
数学
-
18
ピリオドグラムって…
数学
-
19
エクセルの散布図のX軸に文字を表示したいのですが、どうしたらよいのでしょうか?
Excel(エクセル)
-
20
エクセルで長い行を5行ごとに1列にするには?
Excel(エクセル)
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「未使用」と「不使用」ってど...
-
パレート図等で「N=100」とあ...
-
高速フーリエ変換でデータ数が...
-
XMLデータってなんですか?
-
インスタの設定について。 イン...
-
ワードの差し込み印刷のデータ...
-
日本通信の当月利用データ量は...
-
d’の求め方
-
ネットカフェから、メールでき...
-
Excel Webクエリ
-
シリアルRS-232出力機器からの...
-
Excelの“並び替え”で文字コード...
-
OUTLOOK2003 予定表について
-
相関行列作成時の数字以外のデ...
-
【MSOffice Publisher2010差し...
-
エクセルのグラフのデータ系列...
-
PCの内蔵メモリにデータは残る?
-
メモリーの読み出し方式
-
印刷キューに表示されるサイズ...
-
排他的論理和の問題
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「未使用」と「不使用」ってど...
-
高速フーリエ変換でデータ数が...
-
PCの内蔵メモリにデータは残る?
-
日本通信の当月利用データ量は...
-
パレート図等で「N=100」とあ...
-
XMLデータってなんですか?
-
ネットカフェから、メールでき...
-
インスタの設定について。 イン...
-
データ用HDDの別のPCへの乗せ替え
-
エクセルのグラフのデータ系列...
-
エクセルで縦に並んだデータを...
-
Excel Webクエリ
-
Excelの“並び替え”で文字コード...
-
電子辞書の画面をPCに映すには
-
ワードの差し込み印刷のデータ...
-
職務質問で聞かれたデータはど...
-
表計算: 多次元の表を作りたい
-
相関行列作成時の数字以外のデ...
-
Excel グラフで数値の正と負の...
-
フーリエ変換のデータの補間に...
おすすめ情報