質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Mathematica

Mathematicaは、ウルフラム・リサーチによって開発されている数式処理システムです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

971閲覧

FFTのプログラムを組む上で疑問があります。

mathmax

総合スコア1

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Mathematica

Mathematicaは、ウルフラム・リサーチによって開発されている数式処理システムです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2022/03/19 10:26

編集2023/03/08 23:21

FFT(高速フーリエ変換を更に速くするために改良されたプログラム)の偶数行と奇数行に分けて計算を行うバタフライ演算に関して疑問があります。
(N/2)²+(N/2)²=N²/2の(N/2)²に関してN自乗されるのはわかるのですが、なぜ分母の2まで自乗されるのでしょうか?

また、なぜ偶数行と奇数行に分ける事でさらに早く計算処理が出来るとわかったのでしょうか?

どうかよろしくお願い致します。

補足です。
なぜ高速フーリエ変換(FFT)はO(n*log n)で計算できるのでしょうか?
どうか理由を詳しく教えて下さい。

以下の「」はFFT
を説明したものですが、
「」のどの部分がO(n*log n)を、表すのでしょうか?


Ck = (1/N)∑[m=0→N-1] fm・e^(-jkmωD) (k = 0, 1, 2, …… , N-1)...②
ω = 2π/T = 2π/ND、j は虚数単位

と定義したものを

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

と書き変えたものに過ぎない。DFTを高速フーリエ変換FFTに変えるにはバタフライ演算というややこしいものを理解しないといけない。はっきり言って掲示板でチョコチョコ説明できるようなものではない。
離散フーリエ変換は、数学者の書いたフーリエ解析の本にはまず載っていないので、信号処理関係の本を探して勉強されたい。

 W^(km) = e^(-jkmωD) として N = 4 のとき(#)を展開すれば
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
となるがW^(km)の性質から
X0 = f0・W^0 + f1・W^0 + f2・W^0 + f3・W^0
X1 = f0・W^0 + f1・W^1 - f2・W^0 - f3・W^1
X2 = f0・W^0 - f1・W^0 + f2・W^0 - f3・W^0
X3 = f0・W^0 - f1・W^1 - f2・W^0 + f3・W^1
と簡単になる。しかし、これでも16回の掛け算が必要なのは変わらない。そこで上の式を奇数行と偶数行に分け
X0 = f0・W^0 + f1・W^0 + f2・W^0 + f3・W^0
X2 = f0・W^0 - f1・W^0 + f2・W^0 - f3・W^0
X1 = f0・W^0 + f1・W^1 - f2・W^0 - f3・W^1
X3 = f0・W^0 - f1・W^1 - f2・W^0 + f3・W^1
ここからは上の展開式を行列で表さないとわかりにくいのだが、メンドーなので省略する。とにかく上のように行を入れ替えると
X0 = W^0(f0+f2) + W^0(f1+f3)
X2 = W^0(f0+f2) - W^0(f1+f3)
X1 = W^0(f0-f2) + W^1(f1-f3)
X3 = W^0(f0-f2) - W^1(f1-f3)
のように8個の掛け算だけで済むように変形できる。これがバタフライ演算であり、FFTがDFTより速い理由である。」

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

私も詳しくないので,分かるところだけ。
「」の部分のO(n×log n)について。

「」の中で示されている例は,n=4です。演算量は全ての式の「×」の数と考えていいですね。理由としては複素数の場合一つの乗算で

複素数の乗算

のように,4つの実数の乗算が含まれるので,計算速度を上げるには
乗算回数を減らすことが有効といえます。

元のDFTの式

DFT

の場合,O(4×4)といえます。

最後に示しているFFTの式は

FFT

ですが,ここでは合計8回の乗算ですんでいます。
演算量で示すlog nlog2(n)のことを示すことが多く,log2(4) = 2であるので,
n=4の場合,FFTの演算量はO(4× log 4) = O(4×2)ということです。

このように,FFTは「一つにまとめられる掛け算をまとめる」ということで高速化しており,
この考え方は,大量のデータを処理する時の高速化にも利用できるものです。

投稿2022/08/28 05:23

ujimushi_sradjp

総合スコア2066

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mathmax

2023/03/08 14:21

ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問