FFT基本原理
FFT是一種DFT的高效算法,稱為快速傅立葉變換(fast Fourier transform)。FFT算法可分為按時間抽取算法和按頻率抽取算法,先簡要介紹FFT的基本原理。從DFT運算開始,說明FFT的基本原理。
DFT的運算為:


由這種方法計算DFT對於X(K)的每個K值,需要進行4N次實數相乘和(4N-2)次相加,對於N個k值,共需N*N乘和N(4N-2)次實數相加。改進DFT算法,減小它的運算量,利用DFT中

時間抽取(DIT)基2FFT算法
設N點序列x(n),
N=


改寫為:

一個N點DFT分解為兩個 N/2點的DFT,


頻率抽取(DIF)2FFT算法
頻率抽取2FFT算法是按頻率進行抽取的算法。設N=

將x(n)按前後兩部分進行分解,


任意整數的FFT

