フーリエ変換を高速で行える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と関連する良く見られている質問

Q高速道路の料金計算方法について

高速道路を使っていて、疑問に思ったことがあります。

JH(道路公団)の運営している高速道路・有料道路を通行するとき、道路の名前が変わっても料金は通算して計算されますよね。たとえば、東名→名神と走った場合、料金は通算して計算されます。高速道路と有料道路を介した場合でも、東名高速→東海環状自動車道→中央道と通行した場合は、料金は一括して計算されます。

しかし、外環を介して関越道→外環→常磐道と通行した場合は、料金が別々に計算されます。これは、外環が均一料金だからということなんでしょうか?料金計算が一旦切られてしまうと、利用者が損をする気がするのですが。他にもこのような例はあるのでしょうか?

よろしくお願いします。

Aベストアンサー

関越道・東京外環道・常磐道ともJHが管理する高速自動車国道ですが、他の方がおっしゃっているように東京外環道だけ均一料金制のため必ず料金所をとおることになります。

こういう風になったのは、東京外環道は他の高速道路より完成したのが遅かったからともいえます。もし、料金一括精算のために関越・新座、常磐・三郷の各本線料金所を撤去するとなるとそのための費用が余計にかかり余りにも非効率です。
また、一括で精算するためには外環の内側に料金所を設ける必要があります。常磐道、東北道の場合は首都高速の料金所に料金収受を依頼する方法も考えられますが関越道の場合、直結する首都高速の路線がなく大泉JCT-練馬IC間の1kmほどの距離に料金所を設置する必要が生じるため、そんなことしたら渋滞がますますひどくなることは火を見るより明らかです。

他では、京葉道路(一般有料道路)は船橋・千葉西の各料金所で2回料金を払います。これは篠崎-船橋、船橋-宮野木間がそれぞれゾーン料金(均一)になっているからなのです。宮野木から西は他の高速道路と一緒で対距離制です。

Qフーリエ変換について質問です フーリエ変換(3.1)から逆フーリエ変換(3.3)を導く方法を教えてく

フーリエ変換について質問です

フーリエ変換(3.1)から逆フーリエ変換(3.3)を導く方法を教えてください

フーリエ変換
F(ω)=∮(-∞→∞)f(t) e^(-jωt) dt (3.1)

逆フーリエ変換
f(t)=∮(-∞→∞)1/2π F(ω) e^(jωt) dω (3.3)

Aベストアンサー

いきなり(3.1)から(3.3)を導くのは難しいため、複素フーリエ級数から始めるとよいと思います。

その方式で説明しているサイトがあったのそちらを見た方が早いと思います。
http://eman-physics.net/math/fourier05.html

Q高速道路料金無料化

「世界一高い」と評判の悪い日本の高速道路料金の無料化が国会で審議されようとしている。
皆さんは、高速道路料金の無料化は、賛成・反対どちらでしょうか?

Aベストアンサー

財源確保がどうなっているやら。
消費税増税等の一派財源でまかなった場合に、一気に不況になります。
2ちゃんねるの情報ですが、必要な財源が国民1名あたり2-3万円で、これ以上の使用する人以外は増税になります。都内から日帰り観光の範囲が大体栃木県・群馬県として、往復6000円、年10回の利用なんて、考えられません。
つまり、大多数の国民にとっては増税になります。

http://news.goo.ne.jp/hatake/20071127/kiji359.html
10年で68兆円。年7兆円、1億で割って、年7万円。
だから、大きな間違いをしていないと思います。

しかも、補修の費用がかなり多いのですが、原因は、過積載であり、大型車の通行に限られます。

利益を得るのは、運送業者だけ。運送業者の利益確保のためだけに税金が使われることになります。

財源確保が、利益を得るであろう運送業者に対して課税するのであれば、認めますが、一般財源からですと、大多数の国民は負担増にしかなりませんので、反対です。

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

Q高速道路の料金の払い方。

今度、高速道路(ルートは東関東自動車道(成田)~首都高速(浦安)です)を使ってTDLに行こうと思ってます。しかし高速道路の料金の払い方(何回料金を払う場所があるなど)がよくわかりません。それとICやJCってなんですか?できるだけ詳しくご説明のほう宜しくお願い致します。

Aベストアンサー

東関東自動車道を走ってくると、湾岸習志野ICのところに本線料金所があるので、習志野で降りるにしても首都高に向かうにしても、全車料金を払うことになります。
首都高に向かう場合は、料金を払ってそのまま走っていくと、湾岸市川ICの先で首都高の市川本線料金所があるのでそこで首都高の料金を払います。

なお、京葉道路を経由すると一見安いように見えますが、京葉道路市川IC→首都高小松川線から首都高で浦安に向かうには都心まで入ってこないと行けませんので、現実的ではないことにご注意下さい。

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高速道路の料金 エスティマ クラスユーザの方にお聞きします

高速道路の料金ですけど、エスティマクラスの車種の場合、中型車になるのでしょうか?高速道路の料金体系について教えてください

Aベストアンサー

JHの説明の所です。

参考URL:http://www.jhnet.go.jp/faq/01/toll/ryo.htm

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山形から栃木県宇都宮までの高速道路の料金を教えて下さい

山形から栃木県宇都宮までの高速道路の料金を教えて下さい

8月29日(日)に山形から宇都宮に高速で行こうと考えているのですが、
ドラぷらなどネットで料金をしらべると5,750円とでます。
高速道路の上限金額が2,000円と聞いたのですがちがうのですか?

車は普通乗用車でETCは付いていません。

Aベストアンサー

「高速道路の上限金額が2,000円」

というのは、確かに、6月から実施されるとの計画がありました。
http://car.watch.impress.co.jp/docs/news/20100409_360130.html

が、今までの割引が適用しないとのことから、反対が多く、撤回されマシした。
つまり、「上限金額が2,000円」ではありません。

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ランキング