フーリエ変換を高速で行えるFFT(高速フーリエ変換)というのがありますが、
具体的にどういうものなのでしょうか?何故に速くなるのですか?ちなみにフーリエ変換は理解しています。

A 回答 (4件)

siegmund です.



質問をよく見ましたら,
「何故に速くなるのですか?」もありましたね.
ちょっと早合点しちゃいました.

m=0 から m=N-1 までのN個のmの値に対して f(m) が与えられたとして
(前の回答ではxと書きましたが,離散的なのでmにしました)
離散フーリエ変換は
(1)  F(k) = Σ(m=0~N-1) f(m) W^(km)
です.ただし,W = exp(2πi/N) です.
(1)のままやると,N^2 回の乗算が必要です.

ところが,N = N1×N2 と因数分解できるとき
(3)  φ(k1,m2) = W^(k1m2) Σ(m1=0~N1-1) f(N2m1+m2) W^(N2k1m1)
(4)  F(k1+N1k2) = Σ(m2=0~N2-1) φ(k1,m2) W^(N1k2m2)
と分解できます.
ただし,
(5)  k1=0,1,・・・,N1-1
(6)  m2=0,1,・・・,N2-1
(7)  k2=0,1,・・・,N2-1
です.
(3)の乗算は N1×N2 回
(4)はこの各々に対して N2 回ですから,全体で N1(N2)^2 回の乗算で,
もとの N^2 = N1^2×N2^2 回の乗算に対して 1/N1 になりました.

ametsuchi さんご紹介のHPの「1.2.1 基本的な考え方」では,
この分解が N=2×(N/2) になっている場合が例示されています.

細かいテクニックは色々あるようですが,
私はそちらの専門家ではないので詳細をつっこまれるとボロが出ます.
演算量が減る原理ということで,お答えしました.
式が書きにくいんで,ミスプリが心配です.
    • good
    • 0
この回答へのお礼

非常に詳しい説明を有難うございます。よくわかりました。

お礼日時:2001/04/26 23:24

siegmund先生のいわれるとおりで、わたし如きシロートの出る幕はないのですが、やさしい解説が以下のURLに付いていますので参照してください。



手元の資料によれば、N log N ではなく、N/2 log N となっていますが、「オーダー」とおっしゃられているので、間違いではないでしょう。

FFTが、現場でどれだけ約に立っているか、身近に接する機会も多いでしょう。コンピュータの処理能力の向上とともに、音声・画像など、これから益々重要になってきますが、FFT抜きではとても考えられないことです。

参考URL:http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/
    • good
    • 0

高速フーリエ変換は数値計算の話で,


離散的なxについて関数値が知られているとき,
これを離散的フーリエ変換しようとするものです.

N個のxの値について関数値が知られているとき,
離散的フーリエ変換の式そのもので計算しますと N^2 回のオーダーの乗算が必要ですが,
アルゴリズムの工夫により N log N のオーダーの乗算回数で結果が得られます.
1965年にクーリーとチューキーが開発した手法です.
    • good
    • 0

計算回数を減らせるようアルゴリズムが工夫してあるからです。

    • good
    • 0

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

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QFFTによるフーリエ変換のピーク値

エクセルの分析ツールを使って,フーリエ解析をしました。その中でどうしてもわからないところがあったので教えて下さい。例えばある単純な正弦波をフーリエ変換したとします。そのときデータの個数を256, 512, 1024, 2048, 4096というように増加させると,ピーク値に相当する周波数は変化しないのに,ピーク値が増加します。これはどうしてなのでしょうか?このときはどのように処理すればいいのでしょうか?基本的な質問かもしれませんが,どうぞよろしくお願いいたします。

Aベストアンサー

離散フーリエ変換の定義式(下記参考URL)をご覧ください。
例えば、複素正弦波1周期をn分割した
xk=exp(2πik/n)をフーリエ変換すると(i=√(-1))
fj=n   (j=1)
fj=0   (j≠1)
となります。ご質問のピーク値f1はnに比例していることがわかります。ついでにいいますと、逆フーリエ変換の式で係数1/nが現れるのはこのためなのです。

参考URL:http://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

QFFT フーリエ変換 について

FFTについて質問があります。

あるシミュレーションのために
・サンプリング周波数48kHz
・量子化24ビット
・1kHzのサイン波
のデータを作って、それをFFTにかけてみると
裾野が広がり、フロアの高いスペクトラム
となってしまいました。(データは4096ポイント、Hanning窓)

ポイント数が少ないことによる劣化だと考え、データポイントを
65536ポイントで取ってみると綺麗なスペクトラムとなっており、
データの作り方としては間違っていないのではないかと考えています。

一般的にFFTはデータポイントが多い方が、FFTをとったときに、
裾野広がらず、シャープなスペクトルを得ることはわかっています。
が、そこを何とか少ないポイント数で綺麗なFFTを得られるような
入力データは作れないものでしょうか?

出所は不明ですが、私の持っている別のデータを入力として用いると
少ないポイントでも綺麗なFFTを得ることが出来ているので、
何かデータを作るコツのようなものがあると思って投稿させて
いただきました。

どなたか詳しい方がいらっしゃいましたら、ご教授お願いします。

FFTについて質問があります。

あるシミュレーションのために
・サンプリング周波数48kHz
・量子化24ビット
・1kHzのサイン波
のデータを作って、それをFFTにかけてみると
裾野が広がり、フロアの高いスペクトラム
となってしまいました。(データは4096ポイント、Hanning窓)

ポイント数が少ないことによる劣化だと考え、データポイントを
65536ポイントで取ってみると綺麗なスペクトラムとなっており、
データの作り方としては間違っていないのではないかと考えています。

一般的にFFTはデータ...続きを読む

Aベストアンサー

サイン波(あるいは一般に周期Tの関数)であるなら、窓関数など使わず、
データの幅を周期の整数倍に合わせればきれいになりますよ。

つまり、FFTのデータ数をN、nを任意の自然数として、
サンプリング周期をnT/Nにとります。

窓関数を使うなら、信号をf(x)、窓関数をw(x)、
それぞれのフーリエ変換をF(s), W(s)とすると、
窓関数をかけたフーリエ変換

∫[-∞→+∞] f(x)w(x) e^{isx}dx

はF(s)とW(s)の畳み込み

(1/2π)F*G(s)=(1/2π)∫[-∞→+∞] F(t)W(s-t) dt

になるので、W(s)をせまく、つまりw(x)を広く取れば広がりは抑えられるはずです。
(係数(1/2π)はフーリエ変換の定義により変わります。)

Qフーリエ変換--フーリエ変換分光法の原理の証明

画像の2段目の式(B(t)のフーリエ変換)はどのようになるのでしょうか。
A(オメガ)となってほしいのですが, どのように計算すればよいでしょうか。

ちなみにこの式はフーリエ変換分光法において, 「得られたインターフェログラムをフーリエ変換することで, 試料のスペクトルとなる」ということを証明するための式です.
数式中のB(t)をインターフェログラム, A(オメガ)を光源のパワースペクトルと考えています.


----------画像中の数式について---------------
1段目の積分記号の右にあるRのような文字は複素数の実部を示す記号です. iは虚数, tは時刻, ωは角周波数を示しています.
なお, A(オメガ)は実数関数とします.

以上よろしくお願いいたします.

Aベストアンサー

ご質問の B(t) の式
  B(t) = ∫[-∞ to ∞]Re[A(ω)exp(iωt)dω]
が意味不明なので、
  B(t) = ∫[-∞ to ∞]Re[A(ω)exp(iωt)]dω
と解することにします。

A(ω) が ( -∞, ∞ ) で積分可能であり、かつ、 A(ω) のフーリエ変換も ( -∞, ∞ ) で積分可能なら、

[1]  ∫[-∞ to ∞]B(t)exp(-iωt)dt = π(A(ω)+A(-ω))  (a.e.)

です( a.e. は、ほとんど至るところのωで等式が成立することを示す)。
とくに、もし、 A(ω) が、「連続な偶関数(A(ω)=A(-ω) )」という条件も満たすなら、

[2]  ∫[-∞ to ∞]B(t)exp(-iωt)dt = 2πA(ω)

です。
[1]は、次の定理から導けます。

[3]  フーリエ逆変換の定理(or 反転公式)

「 f(x) を (-∞, ∞) で積分可能な実数値関数とし、 F(ν) をそのフーリエ変換とする:
  F(ν) = ∫[-∞ to ∞]f(x)exp(-2πiνx)dx
もし、 F(ν) が ( -∞, ∞ ) で積分可能なら、ほとんど至るところの x で次の等式が成立する。
  f(x) = ∫[-∞ to ∞]F(ν)exp(2πiνx)dν  」

なお、フーリエ変換について、工学系や物理系の人と数学系の人では、若干異なった定義を使っています(係数2πを乗ずるかどうかの違い)。ここでは、数学系の定義に従って記述します。どっちの定義を使っても、今回の計算結果は変わりません。

以下が、[1] の導出過程です。

******************

( 関数G(t) )

次の関数 G(t) を使う。 A(ω) が ( -∞, ∞ ) で積分可能との仮定があるので、 G(t) は、-∞ < t < ∞で定義された関数として確定する。

  G(t) = ∫[-∞ to ∞]A(ω)exp(-iωt)dω

A(ω) が実数値だから、

[4]  conj(G(t)) = G(-t)

である( conj は複素共役を表す)。
また。 s = t/(2π) とすれば、

  G(2πs) = ∫[-∞ to ∞]A(ω)exp(-2πiωs)dω

だから、 G(2πs) は、 A(ω) のフーリエ変換である。よって、 [3] により、次が成立する。

  A(ω) = ∫[-∞ to ∞]G(2πs)exp(2πiωs)ds  (a.e.)

さらに積分変数を s から t に置換して、次を得る。

[5]  2πA(ω) = ∫[-∞ to ∞]G(t)exp(iωt)dt  (a.e.)

ωの代わりに -ωを代入して、次を得る。

[6]  2πA(-ω) = ∫[-∞ to ∞]G(t)exp(-iωt)dt  (a.e.)

また、 [5] の両辺の複素共役をとれば、 [4] を考慮し、次を得る。

[7]  2πA(ω) = ∫[-∞ to ∞]G(-t)exp(-iωt)dt  (a.e.)

( B(t)exp(-iωt) の積分)

Re[A(ω)exp(iωt)] = (1/2)(A(ω)exp(iωt) + conj(A(ω)exp(iωt))) = (1/2)(A(ω)exp(iωt) + A(ω)exp(-iωt)) である。よって、次を得る。

  B(t) = ∫[-∞ to ∞]Re[A(ω)exp(iωt)]dω
     = (1/2)∫[-∞ to ∞](A(ω)exp(iωt) + A(ω)exp(-iωt))dω
     = (1/2)(G(-t) + G(t))

よって、次のようになる。

  ∫[-∞ to ∞]B(t)exp(-iωt)dt
  = (1/2)∫[-∞ to ∞](G(-t) + G(t))exp(-iωt)dt
  = (1/2)∫[-∞ to ∞](G(-t)exp(-iωt) + G(t)exp(-iωt))dt
  = (1/2)(2πA(ω) + 2πA(-ω))  (a.e.) ( [6] と [7] より)
  = π(A(ω) + A(-ω))

ご質問の B(t) の式
  B(t) = ∫[-∞ to ∞]Re[A(ω)exp(iωt)dω]
が意味不明なので、
  B(t) = ∫[-∞ to ∞]Re[A(ω)exp(iωt)]dω
と解することにします。

A(ω) が ( -∞, ∞ ) で積分可能であり、かつ、 A(ω) のフーリエ変換も ( -∞, ∞ ) で積分可能なら、

[1]  ∫[-∞ to ∞]B(t)exp(-iωt)dt = π(A(ω)+A(-ω))  (a.e.)

です( a.e. は、ほとんど至るところのωで等式が成立することを示す)。
とくに、もし、 A(ω) が、「連続な偶関数(A(ω)=A(-ω) )」という条件も満たすなら、

[2]  ∫[-∞ to ∞]B(t)exp(-iωt...続きを読む

Q逆高速フーリエ変換

二つの式の積を高速・逆高速フーリエ変換を使って出したいのですが、最後の逆高速フーリエ変換が分かりません。
f=2+(1-3i)x
g=-(1+i)+2ix+(3-i)x^2
これらの高速フーリエ変換は
FFT(4; (6-6i,-36-6i,14+2i,2+2i))
になると思うのですが、
この後、逆高速フーリエ変換はどのようにするのでしょうか?

Aベストアンサー

御質問内容の細かいことは吟味していませんが、原理だけ述べます。
逆高速フーリエ変換(高速で計算する逆フーリエ変換)は高速フーリエ変換と同じです。
高速フーリエ変換で得られた結果の共役複素数を取り、高速フーリエ変換を行えば逆変換が得られます。ただし、サンプル数Nで割る必要があります。

Q高速フーリエ変換

高速フーリエ変換で出力される実数部と虚数部は何を意味しているのでしょうか?

Aベストアンサー

絶対値が、振幅
atan(虚/実)が、位相
を表します。


人気Q&Aランキング

おすすめ情報