メモ帳ブログ @ wiki

高速フーリエ変換

最終更新：2009年01月06日 14:17

nina_a

- view

管理者のみ編集可

高速フーリエ変換

このページを編集

概要

　高速フーリエ変換（FFT、Fast Fourier Transform）とは、離散フーリエ変換を計算機上で高速に計算するアルゴリズムである。

解説

　離散フーリエ変換の定義式は、
$X(k)=\sum_{n=0}^{N-1}x(n)W_N^{nk}$
　信号系列x(n)を偶数番目のデータx(2n)と奇数番目のデータx(2n+1)に分ける。
$X(k)=\sum_{N=0}^{\frac{N}{2}-1}x(2n)W_N^{2nk}+\sum_{N=0}^{\frac{N}{2}-1}x(2n+1)W_N^{(2n+1)k}$
　ここで、 $W_N^{2nk}=\mathrm{exp}(-i\frac{2\pi}{N}2nk)=\mathrm{exp}(-i\frac{2\pi}{\frac{N}{2}}nk)=W_{\frac{N}{2}}^{nk}$ 、 $W_N^{(2n+1)k}=W_N^kW_N^{2nk}=W_N^kW_\frac{N}{2}^{nk}$ であるから、
$X(k)=\sum_{N=0}^{\frac{N}{2}-1}x(2n)W_{\frac{N}{2}}^{nk}+W_N^k\sum_{N=0}^{\frac{N}{2}-1}x(2n+1)W_{\frac{N}{2}}^{nk}$

　偶数番目のデータx(2n)のフーリエ変換をG(k)、奇数番目のデータx(2n+1)のフーリエ変換をH(k)と表すと、
$X(k)=G(k)+W_N^kH(k)$
となる。このようにN点DFTは2つのN/2点DFTに分解される。さらに、G(k)、H(k)も分解することが可能であるから、N点DFTはN/2個の2点DFTに分解することが可能であることがわかる。