高速フーリエ変換の式をそのまま使わずに工夫をする事で高速に計算できるアルゴリズムをジェイムズ・クーリ

Question

詳しい人求む！

高速フーリエ変換の式をそのまま使わずに工夫をする事で高速に計算できるアルゴリズムをジェイムズ・クーリ

解決済

質問者：akitv
質問日時：2022/03/06 13:47
回答数：10件

usa3usa · Accepted Answer

No4です。
お礼拝見しました

＞tknak muri様、
＞どうか画像の1と3だけで良いので回答して頂けないでしょうか？
＞どうかよろしくお願い致します。

マナーとして、別の質問として、画像の1と3の解説について質問されたほうが、良いとおもいますけど・・

ひなげしのはな · Answer

さぁ……。

Tacosan · Answer

あなたのいう「高速フーリエ変換の式」って, どういう「式」なの?

都の西北我瀬駄の隣バカ田大学危機管理学科 · Answer

以下は昔のメモから取り出したので少し形は違うが、その画像の式は離散フーリエ変換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回に激減するのだ。

usa3usa · Answer

>どうやって高速フーリエ変換の式からアルゴリズムを導いたのでしょうか？
「計算回数を激減できるバタフライ演算」が活用できるような計算アルゴリズムを発見できたから
でしょうね。

>具体的な計算や言葉を用いて説明して頂けると助かります。
No3さんの回答の通り。

usa3usa · Answer

No４です
＞高速フーリエ変換の式に関しても式のままプログラミングするのではなくpcで高速で動かすために高速フーリエ変換の計算アルゴリズムを作ったのですね！
そうです。

例えば組み合わせ 10C3 の計算を考えてみてください
nCm = n! / m! (n-m)! なので、  10C3 = 10! / (3! 7!) ですので
10x9x8x7x6x5x4x3x2x1/(3x2x1 x 7x6x5x4x3x2x1) ですが、式のまま計算する人はあまりいないと思います。質問者さんも、まずは通分して
10x9x8 / 3x2x1 = 5 x 3 x 8 
で計算しますよね。  
計算の手続き（プログラム）は「通分する」という処理が追加になり複雑になりますが、通分すると計算量は大幅に減少できますよね。