高速フーリエ変換はハードウェアでの話なのでしょうか？ それとも紙に高速フーリエ変換の計算通りに計算し

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

No.4 回答者： Tacosan 回答日時： 2020/01/10 01:51

たぶん, 実際にやってみればわかると思うよ.

No.3 回答者： rinkun 回答日時： 2020/01/09 18:05

FFTは単なる計算アルゴリズムですから、別にコンピュータじゃなく紙の上で計算しても、そのアルゴリズム通りにやれば普通の計算よりは早くなりますよ。

ただ結構複雑な計算になるので手作業で間違いなくやるのは難しいと思いますけど。

高速フーリエ変換って、端的に言えば、普通のフーリエ変換の演算だと同じ計算を何度も繰り返すので、計算順序など工夫して同じ演算を一つにまとめれば効率的になるというだけのことですよ。

なお、おおよそ教科書等に載っているのはデータ長が2べきの一番簡単な場合だけですが、実際のFFT実装ではいろいろな素因数とか大きな素因数がある場合の高速化アルゴリズムなんかを組み合わせて2べき長以外でも高速に実行できるように実装されている場合もあります。それらの全体像を理解しようとするとオープンソース実装とかでコメントからそれぞれの高速化手法を記載している論文を探して多数読み込まないといけなくなりそうですね。

この回答へのお礼

なるほど、高速化するために数値によって様々なアルゴリズムがあるのですね。
仮にただのフーリエ変換を早くするとしたらハード面で並列計算したりすれば物理的に早くできそうです。

お礼日時：2020/01/10 06:13

No.2 回答者： 銀鱗 回答日時： 2020/01/09 15:11

ん？

紙に？

値を書き出すのか、グラフを描くのか、
そういった出力の形態にもよるんじゃないかな。

一般的に計算は早く終わる。
…あとは自身で考えてみましょう。

この回答へのお礼

ありがとうございます。
角周波数と大きさの軸にグラフを書きます。

お礼日時：2020/01/09 15:13

No.1 回答者： 銀鱗 回答日時： 2020/01/09 15:05

高速処理するアルゴリズムのことだからなあ。

「アルゴリズム」なんで、基本はソフトウェアで実現するんだけど、
信号をアナログ処理する回路を使ったハードウェアでもできるんだ。

この回答へのお礼

ありがとうございます。
では、そのアルゴリズムに沿えば、紙に高速フーリエ変換をしてもただのフーリエ変換よりも早くF(ω)が得られるのでしょうか？

お礼日時：2020/01/09 15:07