高速フーリエ変換とフーリエ変換の違い

高速フーリエ変換とフーリエ変換の違いについて教えて下さい。
高速フーリエ変換は何か近似を行うことによって、計算速度を速くしているのでしょうか？
もし、何かの極限で出てくる結果が違う場合などがあれば教えて下さい。

No.3 ベストアンサー 回答者： walkingdic 回答日時： 2008/08/20 07:12

>出てくる結果は全く同じだということなのでしょうか？

その通りです。

No.2 回答者： walkingdic 回答日時： 2008/08/19 15:52

ご質問は当然離散フーリエ変換について話をしていると思うので、それに限定して話をします。

高速フーリエ変換（ＦＦＴ）とフーリエ変換（ＦＴ）の違いですが、単に計算速度の違いに過ぎません。つまり得られる答えは同じです。
近似しているわけではありません。

わかりやすく言えば、通常のフーリエ変換で必要な計算を、一定の制約（データ点数）の元で省略できるように工夫しているということです。

ただＦＴと異なりＦＦＴではデータ点数が２のべき乗でなければならないという制約があります。この制約を克服する方法もないわけではありませんが、当然ながら計算量は増えてしまいます（それでもまともにＦＴするよりは計算量は少ないです）。

この回答へのお礼

回答ありがとうございます。

お二人の回答をまとめると、
離散フーリエ変換は普通のフーリエ変換をPCで扱いやすいように、離散的な時間でのみ可能なようにしたもの。
従って、離散時間を細かく区切ったときのみ普通のフーリエ変換と同じ結果が出てくる。
高速フーリエ変換はアルゴリズムを工夫してやって、離散フーリエ変換をより計算速度の速いものにしたもので、出てくる結果は全く同じだということなのでしょうか？

そういえば、量子フーリエ変換みたいなものもあったと思うのですが、これとの違いは何なのなのでしょうか？

お礼日時：2008/08/19 20:38

No.1 回答者： reiman 回答日時： 2008/08/19 15:10

高速フーリエ変換は離散フーリエ変換を高速に行う計算方法のことなので、

＞高速フーリエ変換とフーリエ変換の違いについて教えて下さい。
はとんちんかんな質問で
離散フーリエ変換とフーリエ変換の違いについて教えて下さい。
と質問するべきでしょう。
フーリエ変換は非周期、連続時間関数を変換対象にできるので応用範囲が広いのです。
離散フーリエ変換は
周期、離散時間関数しか変換対象にできません。
周期を長くとればその長さに応じて多少は妥協できるかもしれません。
また、幅を短くとって連続関数に近づけることも可能です。
しかし、あくまでも
離散フーリエ変換の変換対象は周期、離散時間関数のみです。