第4章快速傅里叶变换FFT

第四章

快速傅里叶变换(FFT)

主要内容引言

直接计算DFT的特点时间抽取基2FFT算法频率抽取基2FFT算法4.1引言DFT是信号分析与处理中的一种重要变换.直接计算DFT的计算量与变换区间长度N2成正比，当N较大时，计算量太大.在快速傅里叶变换(FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的.1965年发现了DFT的一种快速算法以后，情况发生了根本的变化.4.2直接计算DFT的特点长度为N的有限长序列x(n)的DFT为：其周期性表现为：其对称性表现为：N点DFT的复乘次数等于N2.显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少.另外，旋转因子具有明显的周期性和对称性.FFT算法就是不断把长序列的DFT分解成几个短序列的DFT，利用上述周期性和对称性来减少DFT的运算次数.FFT算法基本上分为两大类：

(1)时域抽取法FFT(DecimationInTimeFFT,简称DIT—FFT).(2)频域抽取法FFT(DecimationInFrequencyFFT,简称DIF—FFT).1、算法原理设输入序列长为N=2M(M为正整数)，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法.若序列长度不满足条件N=2M，可以加零补长使其达到N=2M.4.3时域抽取基2FFT算法要点：2、算法步骤要点：结论：只要求出(0~N/2-1)区间内的各个整数k值所对应的X1(k)和X2(k)值，即可求出(0~N-1)整个区间内全部X(k)值，这就是FFT节省计算量的关键.N=2M→N/2仍为偶数→可以进一步把每个N/2点子序列再按输入n的奇偶分解为两个N/4点的子序列→按这种方法不断划分，直到最后剩下2点DFT，两点DFT实际上只是加减运算.3、蝶形运算符号求N=23=8点FFT.(1)将N=8的DFT分解成2个4点DFT【例题】N点DFT的一次时域抽取分解图(N=8)⑵将4点DFT分解成2点的DFT将N/2(4点)子序列按奇/偶分解成两个N/4点(2点)子序列。即将x1(r)和x2(r)分解成奇/偶两个N/4点(2点)点的子序列。N点DFT的第二次时域抽取分解图(N=8)⑶将2点DFT分解成2个1点DFT两点DFT可分解成两个1点DFT，而1点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示.N点DIT-FFT运算流图(N=8)每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法).M级运算总共需要的复数乘次数为：4、DIT―FFT与直接DFT运算量的比较M级运算总共需要的复数加次数为：直接计算DFT的复数乘为N2次，复数加为N(N-1)次数。当N>>1时，N2>>(N/2)log2N。所以DIT-FFT算法比直接计算DFT的运算次数大大减少。例如：N=210=1024时：FFT算法与直接计算DFT所需乘法次数的比较曲线1、算法原理设输入序列长度为N=2M(M为正整数)，将该序列的频域输出序列X(k)按其频域顺序的奇偶分解为越来越短的子序列，称基2按频率抽取FFT算法.若序列长度不满足条件N=2M，可以加零补长使其达到N=2M.4.4频域抽取基2FFT算法2、算法步骤结论：3、蝶形运算符号求N=23=8点FFT.⑴先将N=8的DIF分解成2个4点DIF时域上：x(0)，x(1)，x(2)，x(3)为偶子序列；

x(4)，x(5)，x(6)，x(7)为奇子序列。频域上：X(0)，X(2)，X(4)，X(6)由x1(n)给出.

X(1)，X(3)，X(5)，X(7)由x2(n)给出.【例题】其中:DIF-FFT一次分解运算流图(N=8)⑵再将N=4的DIF分解成2个2点DIFDIF-FFT二次分解运算流图(N=8)⑶再将N=2的DIF分解成2个1点DIF最后剩下两点DFT，它可分解成两个1点DFT，但1点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示.DIF-FFT运算流图(N=8)4.5IDFT的高效算法比较DFT和IDFT的运算公式：将DFT中的系数改为，最后乘