高速フーリエ変換（FFT)高速フーリエ変換（FFT) 信州大学工学部 井澤裕司 １． 高速フーリエ変換とは ここでは、高速フーリエ変換について解説します。 高速フーリエ変換（Fast Fourier Transform; FFT）は、離散フーリエ変換の対称性に着目して、 その演算量を減らし高速に変換を行う手法であり、1965年、CooleyとTukeyにより発表されました。 周期 N の離散フーリエ変換（DFT)では、複素数の乗算を N2 回行う必要があります。 高速フーリエ変換では、その乗算回数を N・log2N /2 回に減らすことができます。 なお、乗算では加算を複数回行うので、加算より複雑な処理になります。 例えばNが2のべき乗、すなわち N=2m のとき、その比率を求めると、 ［FFT] / [DFT] = m・2m-1/22m = m/2m+1 となり、ｍ（すなわちN）が大きいほど、その効果がはっきり現
