ここから本文です

高速フーリエ変換はハードウェアでの話なのでしょうか?

dai********さん

2020/1/914:56:34

高速フーリエ変換はハードウェアでの話なのでしょうか?

それとも紙に高速フーリエ変換の計算通りに計算してもふつうのフーリエ変換よりも早くF(ω)が得られるのでしょうか?
もし違う場合はなぜハードウェアやソフトウェアでしか高速フーリエ変換は出来ないのでしょうか?

閲覧数:
219
回答数:
3
お礼:
25枚

違反報告

ベストアンサーに選ばれた回答

fby********さん

2020/1/916:05:45

あれ、ID 非公開にしたと思ったけどwwwwww

ふつうのフーリエ変換は無限大の周期を取り扱うので手計算では使わない。

> 高速フーリエ変換はハードウェアでの話なのでしょうか?

なんかもうため息が出るなあ。
「道具としてのフーリエ解析」にそんなこと全然書いてないでしょう。

コンピュータでフーリエ解析する手段である離散フーリエ変換 DFT は

Ck = (1/N)∑[m=0→N-1] fm・e^(-jkmωD) (k = 0, 1, 2, …… , N-1)
D = T/N はサンプリング周期。j は虚数単位。

高速フーリエ変換FFT に備えて次のように変形する。

Xk = N・Ck = ∑[m=0→N-1] fm・e^(-jkmωD) (k = 0, 1, 2, …… , N-1)

N = 4の場合
N = 4 のとき ωD = 2π/4 = π/2
W^(km) = e^(-jkmωD) = e^(-jkmπ/2)
と置く。すると

Xk = ∑[m=0→3] fm・W^(km) (k = 0, 1, 2, 3)

なので、展開すると

X0 = f0・W^0 + f1・W^0 + f2・W^0 + f3・W^0
X1 = f0・W^0 + f1・W^1 + f2・W^2 + f3・W^3
X2 = f0・W^0 + f1・W^2 + f2・W^4 + f3・W^6
X3 = f0・W^0 + f1・W^3 + f2・W^6 + f3・W^9

つまり DFT では X0 から X3 を求めるのに各 4 回、合計 16 回の掛け算が必要。
一般に DFT では N 個のデータがあるとき N^2 の掛け算が必要。

N = 4 のときの回転子 W^(km) = e^(-jkmπ/2) の性質により
W^2 = W^6 = -W^0
W^3 = -W^1
W^4 = W^0
W^9 = W^1
なのでバタフライ演算により FFT では最終的に

X0 = (f0+f2) + W^0(f1+f3)
X2 = (f0+f2) - W^0(f1+f3)
X1 = (f0-f2) + W^1(f1-f3)
X3 = (f0-f2) - W^1(f1-f3)

と展開でき、4回の掛け算ですむ。だからFFTは早い。データの数が大きければ大きいほど両者の違いは桁外れになる。
以上のことが「道具としてのフーリエ解析」にはもっと正確に、もっと丁寧に書いてある。

  • 質問者

    dai********さん

    2020/1/916:37:41

    毎度、ありがとうございます!
    なるほど、手計算でもアルゴリズムを使えば早く計算できるのですね!

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

この回答は投票によってベストアンサーに選ばれました!

ベストアンサー以外の回答

1〜2件/2件中

並び替え:回答日時の
新しい順
|古い順

mar********さん

2020/1/915:10:07

別に手計算であっても、離散的なデータを元にフーリエ変換するなら、当然高速フーリエのアルゴリズムの方が速く計算できますよ。

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

pet********さん

2020/1/915:01:36

計算量が減るからその分だけ早く終わるよ。

あわせて知りたい

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる