高速フーリエ変換（FFT）

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

離散フーリエ変換では、離散時間信号の要素数が\(N\)の場合、離散時間信号\(x[n]\)と回転因子の掛け算を\(N^2\)回行う必要があります。FFTは、この\(N^2\)回の計算を大幅に減らすことを目的にしています。

FFTには、様々な手法があります。FFTの具体例は、応用例を確認してください。