DFTによるフィルタ計算

[←]　[↑]　[→]

---

フィルタ計算は、x(n)とh(n)をDFTしてかけ算してからIDFTで戻すことにより計算できる。

ここで、h(n)、x(n)の0≦n≦N-1以外の値は周期的に拡張する。

t軸での畳み込み積分はω軸ではかけ算になった(→フィルタ(畳み込み)と窓(かけ算))

同様に、離散信号の畳み込みもDFTのかけ算を使って計算できる。

ただし、DFTは周期関数を前提としているので、0≦n≦N-1以外の値は周期的に拡張する。

とする。

◇

長いフィルタの計算(畳み込み)は上記のDFTを使った方法の方が速いことがある。

今、入力x(n)の長さをN、フィルタ h(n)の長さをL(＜N)とすると、出力y(n)の長さはNで、このうち最初の(L-2)点は過渡応答になる。

したがってy(n)をDFTを使って計算するにはN点のDFTをすればよい。このときh(n)をゼロ詰めして長さNにそろえておく。

さてFFTのアルゴリズムを使えば、N点のDFTは、(N/2)log₂N回の複素乗算で計算でき、複素乗算は実数の乗算4回だから、結局、フィルタ計算するには、

xのFFT：                2Nlog₂N回

Hの乗算：              4N回

(H*X)のIFFT：        2Nlog₂N回

で合計4N(1+log₂N)回の乗算が必要になる。一方、フィルタを式のとおりに積和計算すると乗算はNL回になる。したがって、4(1+log₂N)＜Lとなるぐらいフィルタの長さLが長いときは、FFTを使って計算した方が乗算回数が少なくたぶん速い。

◇◇

今、h(n)をΔだけ平行移動したh(n-Δ)に置き換えると、出力y(n)も同じだけ平行移動する。実際に計算してみると、

したがって、h(n)を(L-1)点だけ左に平行移動すれば、y(n)の過渡応答を除いた部分を計算結果の先頭に持ってくることができる。

◇◇◇

入力x(n)がFFT点数より長いときは、分割して計算すればよい。

---

[←]　[↑]　[→]