https://same.blog/2021/05/28/c言語高速フーリエ変換の実装周波数間引き型fftコ/
より、仮に画像のフーリエ変換の式をC言語のプログラムにしたらどんな風に書くのでしょうか?
また、フーリエ変換を高速フーリエ変換にどうやって導いたのでしょうか?
なぜ高速化できるとわかったのでしょうか?
また、こちらのサイトの「普通のフーリエ変換はO(n^2)に対し、高速フーリエ変換はO(n*log n)で計算できます。」に関して、
普通のフーリエ変換のO(n^2)は画像の式でいうどの部分を表しているのでしょうか?
また、なぜO(n*log n)とすると普通のフーリエ変換より高速で計算できるとわかったのでしょうか?
出来れば、高速フーリエ変換の式のどの部分がO(n*log n)なのか教えて頂けますか?
最後に
https://www.gfd-dennou.org/arch/prepri/2002/hoku …
のサイトの(3.5.1)の高速フーリエ変換がなぜ一番最初に載せたプログラムのような複雑なプログラムになるのでしょうか?
普通に(3.5.1)の式のまま書けば良いのではないでしょうか?
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
かなりいい加減なことを書いたので訂正。
基本は、任意のDFTは、データが偶数個なら、
処理量が1/4の2つのDFTに分解できるということ。
#ここまでは合ってます(^_^;)
これを繰り返すとN個の極小なDFTに
分解できるので、分解の手間を考えなければ
処理量はNに比例することになります。
しかし分解にNに比例する演算が必要。
個々の極小DFTの演算は1回だけで無視できる。
なので
分解に必要な手間だけ考えると
分解の手間はlog(N)とNに比例するので
NLog(N)
に比例することになります。
これが基本となるアイデアです。
No.1
- 回答日時:
ここで詳細を書くのはきついので
フーリエ変換の教科書を読んで見ては?
基本は、任意のDFTは、データが偶数個なら、
処理量が1/4の2つのDFTに分解できるということ。
これを繰り返すとlog(N)個の極小なDFTに
分解できるので処理量はlog(N)に比例することに
なります。
ソートで処理量をLog(N)にするパターンと
とてもよくにてます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(学校・勉強) ラプラス変換とフーリエ変換の違いを教えて下さい! 4 2021/10/28 18:41
- 数学 離散フーリエ逆変換が周波数分割数をNにできる理由について 4 2022/09/18 12:56
- 数学 フーリエ変換、逆変換の「2π」の扱いについて 3 2022/10/07 08:31
- 数学 高速フーリエ変換に関する質問です。 図はN=8の時のバタフライ演算でしょうか? 1 2022/03/31 19:30
- 数学 フーリエ変換後の負の周波数成分の扱いについて 4 2022/09/03 10:18
- 物理学 複素フーリエ級数展開からフーリエ変換 1 2023/05/12 16:15
- 数学 f(x)のフーリエ変換をF(ξ) g(x)のフーリエ変換をG(ξ)とする時、 ①f(ax+b)のフー 1 2023/02/06 18:25
- 工学 周波数fで表現したフーリエ変換の対称性に関する質問です。 1 2022/09/14 12:27
- 数学 f(x)=e^(-ax+b) のフーリエ変換をフーリエ変換の定義に従って計算せよ。但し、a>0、bは 1 2023/02/06 18:26
- 哲学 フォルダによる本質証明と述語証明 2 2023/10/10 00:53
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
あるプログラムのコマンドライ...
-
Excelに埋め込んだVBAのプログ...
-
VBAにてメール作成した際、一部...
-
「Outlookが他のプログラムによ...
-
C言語でのaccess violationに...
-
C言語で、文字をbmp形式の画像...
-
CreateObject関数について
-
方対数グラフを書く為の計算方...
-
C++でExcel操作
-
プログラムのループの周期を設...
-
PICマイコンのコピー(クローン...
-
VBAでユーザーフォームが自動的...
-
テキストボックスのエンターキ...
-
TMBMSRV.exeによるCPU使用率上昇
-
VB6から他のプログラムを強制終...
-
デスクトップのフォルダ名を取...
-
n88basicからwindows版Basicへ...
-
自動クエリとはどういうもので...
-
クリックするとページ内で説明...
-
3Dモデルにおける法線の計算に...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Excelで4096点以上のFFTの方法
-
あるプログラムのコマンドライ...
-
VBAにてメール作成した際、一部...
-
PICマイコンのコピー(クローン...
-
長距離・マラソンをやりながら...
-
Excelに埋め込んだVBAのプログ...
-
「Outlookが他のプログラムによ...
-
自動クエリとはどういうもので...
-
未使用の変数を一括検索する方法
-
読み込み中にアクセス違反が発...
-
VBAでユーザーフォームが自動的...
-
エクセルとワードをデスクトッ...
-
モジュール、アプリケーション...
-
テキストボックスのエンターキ...
-
画像を読み込むのと取り込むの...
-
Vba 実数および実数タイプの変...
-
インクリメント演算子のみを用...
-
main関数を先頭に置くデメリット
-
C言語でのaccess violationに...
-
Application.ScreenUpdatingが...
おすすめ情報