離散フーリエ変換を高速に計算する手法を高速フーリエ変換(FFT)といいます.コンピュータでフーリエ変換を行うには,フーリエ変換を離散化した離散フーリエ変換(DFT)を実行する必要があります.しかし,DFT は元データがN点の場合,その計算量がN2 に比例して増加してしまいます.FFTDFT の周期性を利用することで演算の冗長性を省き,計算量をN log Nにまで減らすことができる手法です.