第四章快速傅立叶变换FastFourierTransform第一节直接计算DFT的问题及改进途径2.DFT的运算量计算机运算时（编程实现）：例：计算一个N点DFT，共需N2次复乘。以做一次复乘1μs计，若N=4096，所需时间为由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。长期以来，人们一直在寻求一种能提高DFT运算速度的方法。第二节改善DFT运算效率的基本途径2、将长序列DFT利用对称性和周期性分解为短序列DFT的思路N点DFTFFT算法的基本思想：利用DFT系数的特性，合并DFT运算中的某些项把长序列DFT→短序列DFT，从而减少运算量。第三节按时间抽选的基2-FFT算法先将x(n)按n的奇偶分为两组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;带入DFT中所以X1(k)、X2(k)只有N/2个点，以N/2为周期；而X(k)却有N个点，以N为周期。要用X1(k)、X2(k)表达全部的X(k)值，还必须利用WN系数的周期特性。后半部分先将N=8点的DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列x(1),x(3),x(5),x(7)为奇子序列频域上：X(0)~X(3)，由X(k)给出X(4)~X(7)，由X(k+N/2)给出N=8点的直接DFT的计算量为：复乘：N2次=64次复加：N(N-1)次=8×7=56次N点DFT的一次时域抽取分解图(N=8)因为4点DFT还是比较麻烦，所以再继续分解。那么，X1(k)又可表示为X2(k)也可以进行相同的分解：N点DFT的第二次时域抽取分解图(N=8)8N点DIT―FFT运算流图(N=8)3、DIT―FFT算法与直接计算DFT运算量的比较FFT算法与直接计算DFT所需乘法次数的比较曲线x(0)如上所述，N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WNP，称其为旋转因子，p称为旋转因子的指数。对N=2M的一般情况，第L级的旋转因子为：设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点(B=2L-1)，应用原位计算，则蝶形运算可表示成如下形式：3)编程思想及流程图4）码位倒序自然顺序n倒序规律对于数N，在其二进制最高位加1，等于加N/2。倒序排列算法的流程图第四节按频率抽选的基2-FFT算法DIF―FFT一次分解运算流图(N=8)DIF―FFT二次分解运算流图(N=8)DIF―FFT运算流图(N=8)时间抽取算法与频率抽取算法的比较第五节IDFT的快速算法－IFFTDIT―IFFT运算流图DIT―IFFT运算流图(防止溢出)如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：例1、如果通用计算机的速度为平均每次复乘需要5s，每次复加需要0.5s，用它来计算512点的DFT[x(n)]，问：2）用FFT进行运算：例2、对一个连续时间信号xa(t)采样1秒得到4096个采样点的序列，求：2）若计算采样信号的4096点DFT，DFT系数之间的频率间隔是多少？例3、长度为240点的序列x(n)与长度为N点的h(n)卷积。当N=10和240时，直接进行卷积x(n)*h(n)和用IFFT[X(K)·H(K)]的方法相比，那种方法求解y(n)的效率更高？直接进行卷积（N=10）：直接进行卷积（N=240）：