高速フーリェ変換

高速フーリェ変換(FFT:Fast Fourier Transform)は，離散フーリェ変換の対称性 に着目して，その演算量を減らし，高速に変換を行う手法である．1965年に CooleyとTukeyによって，発表された．

周期NのDFTでは，複素数の乗算を$N^2$ 回行う必要があるが，FFTでは，DFTの乗 算回数をN× $\frac{\log_2}{2}$ 回減らすことができる．しかし，乗算は加算を 複数回行うので，加算より複雑な処理になる．

例えば，Nが2のべき乗，すなわちN = $2^m$ のとき，その比率を求めると，

$$\frac{[FFT]}{[DFT]} = \frac{m×2^{m-1}}{2^{2m}} = \frac{m}{2^{m+1}}$$ (15)

となり，m(すなわちN)が大きいほど，計算速度の違いがはっきりと現れる．

入力信号をx(n)，単位円をN分割した点をWと定義すると，

$$W_N^{m + N} = W_N^{m}$$ (16)

(10)式より， $W_N^{0},W_N^{1},...,W_N^{N - 1}$ のN点のみを計算すると，$W_N^{kn}$ が求まる． 複素平面上において， $W_N^k$ は点( $\cos(2\pi k/N$ ), $\sin(2\pi k/N$ ))を取る．原点からの距離は， ( $\cos^2(2\pi k/N$ )+ $\sin^2(2\pi k/N$ )=1なので，原点を中心とする単位円上で は，$W_N^k$ は必ず単位円周上に位置する．その位置は，実軸から $2\pi k/N$ の角度を取るので，$W_N$ のべき乗は，原点を中心とする複素 平面上の単位円を（1,0）から始めてN等分した位置に並ぶ．

次に，複素平面の単位円周上に並んだ$W_N^k$ を示す．

図 8: N=1のとき 図 9: N=2のとき

図 10: N=3のとき 図 11: N=4のとき

上で説明した$W_N^k$ を使ったFFTの式を次に示す．

$$X(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn} (k = 0,...,N - 1)$$ (17)

$$W_N = e^{-j (2\pi /N)}$$ (18)

Nが偶数の時は，x(n)を $x_0(n) = x(2n),x_1(n) = x(2n + 1)$ に分割して，

$$X(k) = \sum_{n=0}^{\frac{N}{2} -1} \left\{x(2n) W_N^{2nk} + x(2n + 1) W_N^{(2n + 1)k} \right\}$$ (19)

$$= \sum_{n=0}^{\frac{N}{2} -1} \left\{x_0(n) W_N^{2nk} + x_1(n) W_N^{(2n + 1)k} \right\}$$ (20)

$$= \sum_{n=0}^{\frac{N}{2} -1} \left\{x_0(n) W_{N/2}^{nk} + x_1(n) W_{N/2}^{nk}W_N^k \right\}$$ (21)

$$= X_0(k) + W_N^{k}X_1(k)~~~~~~~~~~~~~~~~~~~~~~~~~~~(k = 0,...,N - 1)$$ (22)

ただし $X_0(k),X_1(k)$ は部分列 $x_0(n),x_1(n)$ のDFTは，

$$X_0(k) = X_0(k \pm \frac{N}{2}),X_1(k) = X_1(k \pm \frac{N}{2})$$ (23)

$$W_{N}^{k \pm \frac{N}{2}} = - W_N^k~~~~~~~~~~~より,$$ (24)

$$X(k) = \begin{cases} X_0(k) + W_N^k X_1(k)~~~~~~~~~~~0\leq k ... ... -\frac{N}{2})~~~~~~~~\frac{N}{2} \leq k \leq N - 1 \end{cases}$$ (25)

と表せる．

FFTは，信号長Nが2のべき乗の場合，逐次的に信号を2分割して乗算する手法であ る．複素乗算回数はDFTの$N^2$ 回に対して，FFTは $\frac{N}{2}\log_2N$ 回であ る．よって，FFTはDFTよりも高速な計算ができる．

以下にFFTの計算例 $\frac{N}{2}\log_2N$ (N = 8)を示す．

図: $\frac{N}{2}\log_2N$ (N = 8)の計算例