「教えて!ピックアップ」リリース!

高速フーリエ変換の式をそのまま使わずに工夫をする事で高速に計算できるアルゴリズムをジェイムズ・クーリーは発見しましたが、どうやって高速フーリエ変換の式からアルゴリズムを導いたのでしょうか?

質問者からの補足コメント

  • 具体的な計算や言葉を用いて説明して頂けると助かります。

      補足日時:2022/03/06 13:47
  • こんな式です。

    「高速フーリエ変換の式をそのまま使わずに工」の補足画像2
      補足日時:2022/03/06 19:36
  • こんな式です

    「高速フーリエ変換の式をそのまま使わずに工」の補足画像3
      補足日時:2022/03/06 19:38
  • 最後に質問が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
      補足日時:2022/03/16 11:44
  • 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を導いたのでしょうか?

      補足日時:2022/03/16 11:45

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

    と定義したものを

      補足日時:2022/03/16 11:47
  • 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)の性質から

      補足日時:2022/03/16 11:48
  • 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回の掛け算が必要なのは変わらない。そこで上の式を奇数行と偶数行に分け

      補足日時:2022/03/16 11:48
  • 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
     ここからは上の展開式を行列で表さないとわかりにくいのだが、メンドーなので省略する。とにかく上のように行を入れ替えると

      補足日時:2022/03/16 11:49
  • 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より速い理由である。」

      補足日時:2022/03/16 11:49

A 回答 (10件)

No4です。


お礼拝見しました

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

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

Thank you

すいませんでした。
そうさせて頂きます。
出来れば、usa3usa様からも解答を頂けるとありがたいです。

どうもありがとうございます。

お礼日時:2022/03/18 00:05

>画像の式がバタフライ演算の式でしょうか?


式の右側の∑の中にバタフライが見えますよね。

でもそこが本質じゃない。
これをこのまま再帰でプログラムしてもFFTになります。
もっと効率よく出来ますが、枝葉末節なので
まずは基本を押さえることをお勧めします。
    • good
    • 0
この回答へのお礼

なるほど、バタフライ演算の部分を画像の式で表しただけで、用は「 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)」のバタフライ演算の部分を画像の式で置いただけだとわかりました。
ありがとうございます

お礼日時:2022/03/15 04:28

出発点はこれ。


1つのDFTを2つのDFTに分ける式。

まずはこれが恒等式である事を理解するのが
良いと思います。

WNが回転因子。
「高速フーリエ変換の式をそのまま使わずに工」の回答画像8
    • good
    • 0
この回答へのお礼

画像の式がバタフライ演算の式でしょうか?
あるいは、バタフライ演算を使わないやり方なのでしょうか?
どうかもう少しわかりやすく教えて頂けないでしょうか?

お礼日時:2022/03/15 01:37

>「計算回数を激減できるバタフライ演算」


>を扱う場合とは違うのでしょうか?

同じです。DFTの2分割が
バタフライを生みだすのです。
    • good
    • 1
この回答へのお礼

ありがとうございます
すいません

(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)」
どうかよろしくお願い致します。

お礼日時:2022/03/14 23:57

前にも同じ質問に答えた気がしますが、


発想自体はシンプルなので、いずれだれかが
思い付いたと思います。

FFTの基本は、DFTはサンプル数Nが偶数なら
2つのDFTに分解できるということ。
分解するとDFTの処理量は
N²だから、半分に割れれば、(N/2)²+(N/2)²=N²/2
で処理量を半分にできる。

だから、ソ―トとかと同じ分割統治アルゴリズムで行けそう。

Nを2とか4まで落としてゆけばcosやsinの値はわかり切ってるから
更に速く出来そう。

という所から始まった気がします。
    • good
    • 1
この回答へのお礼

ありがとうございます。
回答して頂いた解説は「計算回数を激減できるバタフライ演算」を扱う場合とは違うのでしょうか?

お礼日時:2022/03/14 17:54

No4です


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

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

「高速フーリエ変換の式をそのまま使わずに工夫をする事」は、組み合わせ計算の「通分して計算する」部分にあたり、
ジェイムズ・クーリーが発見した「高速に計算できるアルゴリズム」はプログラムはややこしくなりますが、「計算回数を激減できるバタフライ演算で計算する」ことに相当するということです。
    • good
    • 1
この回答へのお礼

usa3usaさん、この場をお借りさせて頂きます。
tknak muri様、
どうか画像の1と3だけで良いので回答して頂けないでしょうか?
どうかよろしくお願い致します。

お礼日時:2022/03/17 18:20

>どうやって高速フーリエ変換の式からアルゴリズムを導いたのでしょうか?


「計算回数を激減できるバタフライ演算」が活用できるような計算アルゴリズムを発見できたから
でしょうね。

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

なるほど!ありがとうございます!
すなわち、No.3の方が例題として離散フーリエ変換DFTを式のままプログラミングするのではなく、高速をpcで高速で動かすために離散フーリエ変換DFTの計算アルゴリズムを考えたように、
高速フーリエ変換の式に関しても式のままプログラミングするのではなくpcで高速で動かすために高速フーリエ変換の計算アルゴリズムを作ったのですね!

お礼日時:2022/03/08 11:12

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

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

    • good
    • 3

さぁ……。

    • good
    • 4

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング