第7回 高速フーリエ変換FFT

信号処理

DFTの定義式
X(k)=\sum_{n=0}^{N-1}x(n)W_N^{kn} (k=0,1,...,N-1)
より（中略）
X(k)=Y(k)+W_N^kZ(k)

  • バタフライ演算
  • ビットリバーサル
演算回数の比較
  • 複素乗算回数
    • DFT:N^2
    • FFT:{N(logN - 1)}/2
  • 複素加算回数
    • DFT:N(N-1)
    • FFT:NlogN

5.4,5.5は飛ばす

FFTの応用

スペクトル推定（何がやりたいのだろう）
循環たたみ込み

循環たたみ込み演算の計算量はDFTの計算量と変わらない
⇒DFTを利用して周波数領域の乗算に置き換えてIDFTで戻しても計算量は変わらない
変換にFFTを用いれば計算量は N^2⇒NlogN に減らすことができる。

インパルス応答から伝達関数
伝達関数からインパルス応答

フーリエ変換・フーリエ逆変換で求められる

相関関数の計算

自己相関の計算
r_{xx}=z(n)=\frac{1}{N}\sum_{k=0}^{N-1}x(k)x(k+n)
巡回相関則より
Z(k)=X(k)\bar{X(k)}
というわけでこれもたたみ込みと同じように、FFTを用いて周波数領域に変換すると計算が速く済む

ケプストラム解析

反射波があるような信号の解析なんかに使われる。