3-1. 離散フーリエ変換

離散フーリエ変換 (Discrete Fourier Transform,DFT) とは離散群上のフーリエ変換であり、信号処理などで離散化されたディジタル信号の周波数解析などによく使われる。 今、時間信号 (複素数) x[n] の周波数解析を行う。

N 個の時間信号 x[0],...,x[N-1] に対してDFTを行うと、N 個の周波数信号 (複素数) X[0],...,X[N-1] が得られる。

(1.1)

離散フーリエ係数は、回転因子を用いて表すと(1.2)式のように表すことができる。

(1.2)

行列表現によってN=4の場合を例示すれば、(1.3)式のように表され、

(1.3)

これを計算すると、(1.4)〜(1.7)式で表すことが出来る。

(1.4)

(1.5)

(1.6)

(1.7)

この演算について考える。(1.4)〜(1.7)式から N=4 の場合、16回の複素乗算と12回の複素加算が必要である。 このように N 点のDFTを実行には 回の複素乗算と N(N-1) 回の複素加算が必要となる。 電子計算機によってDFTを計算するとき、複素乗算によって処理時間のかなりの部分が費やされてしまうため、 複素乗算を大きく減らすことができるならば、DFTの計算速度を大幅に増大させることが期待される。