FFT基本原理

时间抽取（DIT）基2FFT算法

频率抽取（DIF）2FFT算法

任意整数的FFT

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中

的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。

时间抽取（DIT）基2FFT算法

设N点序列x(n),

N=

,将x(n)按奇偶分组，有

，

改写为：

。

一个N点DFT分解为两个 N/2点的DFT，继续分解，迭代下去，其运算量约为

。

频率抽取（DIF）2FFT算法

频率抽取2FFT算法是按频率进行抽取的算法。设N=，

将x(n)按前后两部分进行分解，

按K的奇偶分为两组，即

得到两个N/2 点的DFT运算。如此分解，并迭代，总的计算量和时间抽取（DIT）基2FFT算法相同。

任意整数的FFT

时，可采取补零使其成为

，或者先分解为两个p,q的序列，其中p+q=N，然后进行计算。