一、基2FFT算法

1.直接计算DFT的特点

• 对于N点DFT的乘法和加法运算次数均为N^2(运算量较大)
• 减少运算量的基本途径：将N点DFT分解成多个较短的DFT
• 旋转因子具有

        周期性：=

        对称性：或又或者

2.时域抽取法基2FFT基本原理

• 分类：基2FFT分为时域抽取法FFT（DIT-FFT）和频域抽取法FFT（DIF-FFT）
• 设x(n)长度为N且满足N=2^M（M为自然数），按n的奇偶数把x(n)分解为两个N/2点的子序列（时域不断奇偶分组）

         （注意X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即以N/2为周期）

• 蝶形运算符

•  若N=8则8点DFT一次时域抽取分解运算流程图（输入倒序输出正序）

        输入时上半部分是偶序列号，下半部分是奇序列号（对应x(n)分为奇偶序列），乘法和加法的次数变为

•  DIT-FFT算法与直接计算DFT的运算量比较（N=2^M）

        a)DIT-FFT的M级运算总复加次数 , 总复乘次数

        b)直接DFT算法总复加次数为N(N-1)次，总复乘次数为N^2次

• DIT-FFT的运算规律

        a)N点DIT-FFT包含M级蝶形运算，每一级包含N/2个蝶形单元

        b)用L表示从左到右的运算级数（L=1，2，3，，M），第L级共有个不同的旋转因子

        c)第M级蝶形运算(L=M)旋转因子为，，，，，，蝶形节点间距为N/2（所谓蝶形节点间距是指蝶形运算符交叉点延长出来的两条横线中间的空格数，有几个空格蝶形间距就为多少）

        d)关于输入序列的倒序，输出序列的正序

（8点DIT-FFT运算流图）

 3.频域抽取法(DIF-FFT)[设序列x(n)的长度N=2^M]

• 将x(n)的DFT,即X(k)分为奇数组X(2m+1)和偶数组X(2m),令

        则有

        偶数组是x1(n)的N/2点DFT，奇数组则是x2(n)的N/2点DFT

• DIF-FFT蝶形运算流图符号

•  DIF-FFT的运算规律

        a)对于长度为N=2^M的序列，需要经过M-1次分解，最后分解为2^(M-1)个两点DFT（两点DFT就是一个基本DIF-FFT蝶形运算符）

        b)DIF-FFT算法与DIT-FFT算法类似，可以原位计算，共有M级运算，每级共有N/2个蝶形单元，所以两种算法的运算次数相同，不同的是DIF算法输入序列为自然序列，输出为倒序。

 （8点DIF-FFT运算流图）

4.IDFT的高效算法

• DIF-IFFT或DIT-IFFT算法：将上述DIT-FFT算法与DIF-FFT算法中的旋转因子改为,最后的输出再乘以1/N即可,要注意IFFT的流图输入的是X(K)输出的是x(n)
• 直接调用FFT算法计算IFFT：先将X(k)取复共轭，然后调用FFT，最后再取复共轭并乘以1/N

二、进一步减少运算量的措施

1.多类蝶形单元计算

• 无关紧要的旋转因子：值为±1和±j的旋转因子，如等
• 基2FFT程序中，包含以下几种蝶形运算：

        a)一类蝶形单元运算：包含所有旋转因子

        b)二类蝶形单元运算：去掉=±1的旋转因子

        c)三类蝶形单元运算：去掉=±1和=±j的旋转因子

        d)四类蝶形单元运算： 去掉=±1和=±j的旋转因子并判断处理=(1-j)/2

2.实序列的FFT算法

• 处理实序列的FFT算法的三种方法：

        a)一个实序列作为作为x(n)的实部，另一个作为虚部，计算完FFT后，根据DFT的共轭对称性，由X(k)分别得到两个实序列的N点DFT

        b)用N/2点FFT计算一个N点实序列的DFT

        c)用离散哈特莱变换（DHT）

• 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即x1(n)=x(2n),x2(n)=x(2n+1),y(n)=x1(n)+jx2(n)
• 对y(n)进行N/2点FFT，输出Y(k)则

• 根据上述可得X(k)=X1(k)+X2(k),又根据x(n)为实序列可得X(N-k)=
• 该算法所需复数乘法次数为N(M+1)/4