No.9
- 回答日時:
>画像の式がバタフライ演算の式でしょうか?
式の右側の∑の中にバタフライが見えますよね。
でもそこが本質じゃない。
これをこのまま再帰でプログラムしてもFFTになります。
もっと効率よく出来ますが、枝葉末節なので
まずは基本を押さえることをお勧めします。
なるほど、バタフライ演算の部分を画像の式で表しただけで、用は「 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)」のバタフライ演算の部分を画像の式で置いただけだとわかりました。
ありがとうございます
No.7
- 回答日時:
>「計算回数を激減できるバタフライ演算」
>を扱う場合とは違うのでしょうか?
同じです。DFTの2分割が
バタフライを生みだすのです。
ありがとうございます
すいません
(N/2)²+(N/2)²=N²/2
が
以下の部分のどこを表しているかは説明出来ますでしょうか?
「 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)」
どうかよろしくお願い致します。
No.6
- 回答日時:
前にも同じ質問に答えた気がしますが、
発想自体はシンプルなので、いずれだれかが
思い付いたと思います。
FFTの基本は、DFTはサンプル数Nが偶数なら
2つのDFTに分解できるということ。
分解するとDFTの処理量は
N²だから、半分に割れれば、(N/2)²+(N/2)²=N²/2
で処理量を半分にできる。
だから、ソ―トとかと同じ分割統治アルゴリズムで行けそう。
Nを2とか4まで落としてゆけばcosやsinの値はわかり切ってるから
更に速く出来そう。
という所から始まった気がします。
No.5
- 回答日時:
No4です
>高速フーリエ変換の式に関しても式のままプログラミングするのではなくpcで高速で動かすために高速フーリエ変換の計算アルゴリズムを作ったのですね!
そうです。
例えば組み合わせ 10C3 の計算を考えてみてください
nCm = n! / m! (n-m)! なので、 10C3 = 10! / (3! 7!) ですので
10x9x8x7x6x5x4x3x2x1/(3x2x1 x 7x6x5x4x3x2x1) ですが、式のまま計算する人はあまりいないと思います。質問者さんも、まずは通分して
10x9x8 / 3x2x1 = 5 x 3 x 8
で計算しますよね。
計算の手続き(プログラム)は「通分する」という処理が追加になり複雑になりますが、通分すると計算量は大幅に減少できますよね。
「高速フーリエ変換の式をそのまま使わずに工夫をする事」は、組み合わせ計算の「通分して計算する」部分にあたり、
ジェイムズ・クーリーが発見した「高速に計算できるアルゴリズム」はプログラムはややこしくなりますが、「計算回数を激減できるバタフライ演算で計算する」ことに相当するということです。
usa3usaさん、この場をお借りさせて頂きます。
tknak muri様、
どうか画像の1と3だけで良いので回答して頂けないでしょうか?
どうかよろしくお願い致します。
No.4
- 回答日時:
>どうやって高速フーリエ変換の式からアルゴリズムを導いたのでしょうか?
「計算回数を激減できるバタフライ演算」が活用できるような計算アルゴリズムを発見できたから
でしょうね。
>具体的な計算や言葉を用いて説明して頂けると助かります。
No3さんの回答の通り。
なるほど!ありがとうございます!
すなわち、No.3の方が例題として離散フーリエ変換DFTを式のままプログラミングするのではなく、高速をpcで高速で動かすために離散フーリエ変換DFTの計算アルゴリズムを考えたように、
高速フーリエ変換の式に関しても式のままプログラミングするのではなくpcで高速で動かすために高速フーリエ変換の計算アルゴリズムを作ったのですね!
No.3
- 回答日時:
以下は昔のメモから取り出したので少し形は違うが、その画像の式は離散フーリエ変換DFTを
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より速い理由である。
N = 4 のケースでは 高々 4^2 = 16回から8回に半減しただけだが、もし N = 1024 なら 1024^2 = 1,048,576 回の掛け算が 4608回に激減するのだ。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 高速フーリエ変換に関する質問です。 図はN=8の時のバタフライ演算でしょうか? 1 2022/03/31 19:30
- その他(学校・勉強) ラプラス変換とフーリエ変換の違いを教えて下さい! 4 2021/10/28 18:41
- 数学 「FFTの基本は、DFTはサンプル数Nが偶数なら 2つのDFTに分解できるということ。 分解するとD 3 2022/03/31 21:01
- 高校受験 高校化学の問題の質問です! 1 2021/11/05 12:14
- カスタマイズ(バイク) スーパーカブ50の70ccにボアアップ後の走行性能について 4 2021/11/19 11:49
- 数学 離散フーリエ逆変換が周波数分割数をNにできる理由について 4 2022/09/18 12:56
- Excel(エクセル) エクセルの数式の規則性がうまくコピーされません。 3 2021/11/10 21:14
- 車検・修理・メンテナンス 特定の回転数での異音 3 2021/10/31 22:29
- 数学 フーリエ変換、逆変換の「2π」の扱いについて 3 2022/10/07 08:31
- 数学 【算数】速度の計算がわかりません。 7 2022/05/24 20:32
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
[ EXCEL VBA ] 図形を読み込む...
-
C♯で電卓を作成しています。演...
-
期間重複チェックがわかりません
-
BCDについて
-
ハッシュアルゴリズム
-
アルゴリズムとプロトコールの違い
-
c言語で画像から文字を認識 キ...
-
ドロネー三角形のプログラム
-
プログラミングの才能のある無...
-
巡回セールスマン問題において...
-
パズルが好きな人ってプログラ...
-
vbaで、連立方程式を解く方法に...
-
グループを均等に分けるには?...
-
画像から文字を認識してテキス...
-
あるプログラムのコマンドライ...
-
Excelに埋め込んだVBAのプログ...
-
VBAにてメール作成した際、一部...
-
0除算して、落ちるプログラムと...
-
VBAで仕様書は書きますか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
BCDについて
-
[ EXCEL VBA ] 図形を読み込む...
-
Stuck
-
グループを均等に分けるには?...
-
画像から文字を認識してテキス...
-
Dijkstraて
-
期間重複チェックがわかりません
-
JPEG圧縮で8×8に分割する理由に...
-
多変数関数の最小値を求めるプ...
-
OpenCVのライセンスについて
-
データを圧縮したい
-
ルービックキューブを揃えるた...
-
5人のテストの点数を入力すると...
-
C♯で電卓を作成しています。演...
-
ドロネー三角形のプログラム
-
vbaで、連立方程式を解く方法に...
-
動画で間違ったこと言っている
-
トップダウン解析とボトムアッ...
おすすめ情報
具体的な計算や言葉を用いて説明して頂けると助かります。
こんな式です。
こんな式です
最後に質問が4つあるのですが、
1,画像の式を展開すると「」の中のような計算になるのでしょうか?...①
2,なぜCkが画像では A2kや A2k+2となっているのはなぜでしょうか?
「」に書かれた②の式とは見た目が違いますが、なぜ違うのでしょうか?
3,①が正しい場合(N/2)²+(N/2)²=N²/2は「」の中のどの部分を指しているのでしょうか?
多分、奇数行と偶数行をわける部分が(N/2)²+(N/2)²=N²/2を指すのかなと考えています。
要はN個の奇数行とNこの偶数行を2で割って奇数行と偶数行合わせてN個にした事まではわかるのですが、
4, (N/2)²+(N/2)²=N²/2に関して、なぜ2乗するかわかりません。
(※式のままでプログラムすると16回の掛け算が必要なので、そこで式を奇数行と偶数行に分け、すなわちバタフライ演算して8回にするために、(N/2)²+(N/2)²=N²/2があるのだろうと考えています。)
5,「画像の1行目の式 A2kと「」に書かれた②の式とは見た目が違いますが、なぜ違うのでしょうか?」
に関して、画像の1行目の式 A2kを置き換えて②の式にしたならば、画像の1行目の式を置き換えて②の式になるまでの過程の計算を教えて頂けないでしょうか?
6,どうやって画像の1行目の式 A2kから画像の2行目の A2k+1を導いたのでしょうか?
「
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) ・・・・・(#)
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より速い理由である。」