《数字信号处理及应用 工业和信息化普通高等教育“十二五”规划教材立项项目 新教学课件 ppt 作者 卢光跃 黄庆东 包志强 第4章 快速傅里叶变换(FFT)》由会员分享，可在线阅读，更多相关《数字信号处理及应用 工业和信息化普通高等教育“十二五”规划教材立项项目 新教学课件 ppt 作者 卢光跃 黄庆东 包志强 第4章 快速傅里叶变换(FFT)（88页珍藏版）》请在金锄头文库上搜索。
1、第4章 快速傅里叶变换,通信与信息工程学院 数字信号处理教学团队,第4章 快速傅里叶变换,4.1 引言 4.2 直接计算DFT的问题及改进的途径 4.3 按时间抽取（DIT）的基2-FFT算法 4.4 按频率抽取（DIF）的基2-FFT算法 4.5 IDFT的高效算法 4.6 FFT的其他应用快速卷积,学习目标,理解按时间抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点； 理解按频率抽取的基-2FFT算法的原理、运算流图、所需计算量和算法特点； 理解IFFT算法；,4.1 引 言,快速傅里叶变换（FFT）并不是一种新的变换，而是离散傅里叶变换（DFT）的一种快速算法。 在信号的频谱
2、分析、 系统的分析、 设计和实现中都会用到DFT的计算。 DFT的计算量太大，很难对问题进行实时处理，难以实用。 1965年首次发现了DFT运算的一种快速算法以后，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法， 这就是快速傅里叶变换（FFT）的算法。 FFT出现后使DFT的运算大大简化，运算时间一般可缩短一二个数量级之多，使DFT的运算在实际中真正得到了广泛的应用。,4.2 直接计算DFT的问题及改进的途径,一、 直接计算DFT的运算量问题设x(n)为N点有限长序列，其DFT为,k=0, 1, , N-1,反变换（IDFT）为,n=0, 1, , N-1
3、,运算量,一个X(k),复数乘法,复数加法,N,N-1,N2,N(N-1),N个X(k),一次复数乘法需用四次实数乘法和二次实数加法； 一次复数加法需二次实数加法。,二、 改进的途径,x(n) 长序列短序列 WNkn,4.3 按时间抽取（DIT）的基 -2 FFT算法,一、 算法原理 1. 一次分解 NN/2 设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列：,k=0,1,N/2-1,利用周期性求X(k)的后半部分,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),-1,-1,-1,-1,WN0,WN1,WN2,W
4、N3,N/2点 DFT,N/2点 DFT,2. 二次分解 N/2N/4,X2(k)也可进行同样的分解：,-1,-1,-1,-1,WN0,WN1,WN2,WN3,N/2点DFT分解为两个N/4点DFT,一个N=8点DFT分解为四个N/4点DFT,N=8，四个N/4点DFT即四个2点DFT，其输出分别为： X3(k)，X4(k)，X5(k)，X6(k)，k=0, 1,二、 按时间抽取的FFT算法与直接计算DFT运算量的比较 N=2M时，共有M级蝶形， 每级都由N/2个蝶形运算组成； 每个蝶形需要一次复乘、 二次复加； 每级运算都需N/2次复乘和N次复加； M级运算总共需要：,复乘数,复加数,以乘法
5、为例，直接DFT复数乘法次数是N2，FFT复数乘法次数是(N/2) log2N； 直接计算DFT与FFT算法的复数乘法计算量之比为 ：,当N=2048时，这一比值为372.4，即直接计算DFT的运算量是FFT运算量的372.4倍； 当点数N越大时，FFT的优点更为明显。,对一个连续时间信号xa(t)采样1秒得到一个4096个采样点的序列，若计算采样信号的4096点DFT。 假定仅对200f300Hz频率范围所对应的DFT采样点感兴趣。 （1）若直接用DFT，要计算这些值需要多少次复乘？ MN=1014096=413696 （2）若用基2的DIT-FFT计算，则需要多少次复乘？ N/2log2N
6、=4096/2log24096=24576,思考题,N点x(n)序列，构造新序列 y(n)=x(n/2),n为偶数时， y(n)=0，n为奇数时， n=0,1,2,2N-1， 求：Y(K)与X(K)的关系，K=0,1,2,. 2N-1,例 题：,解：由DIT-FFT可得 y(2n)= y1(n)=x(n), Y1(K)=X(K) y(2n+1)= y2(n)= 0, Y2(K)=0 n=0,1,.,N-1,已知x(n)长度为N（N为偶数）。定义两个长度为N/2的序列如下: 其中，G(k)=DFTg(n), H(k)=DFTh(n),分别为N/2长。 试利用G(k)和H(k)表示出X(k)=DF
7、Tx(n)，k=0,1,N-1。,补充题,提示,提示,三、 按时间抽取的FFT算法的特点,1. 原位运算（同址运算）,第一级蝶形运算,第二级蝶形运算,第三级蝶形运算,m表示第m级迭代，k, j为数据所在行数；,某一级的两个节点k和j的节点变量进行蝶形运算后，得到结果为下一级k, j两节点的节点变量，即每个蝶形的输入、输出数据节点同在一条水平线上； 与其他节点变量无关，即蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中； 每级的N/2 个蝶形运算全部完成后，再开始下一级的蝶形运算； 这样经过M级运算后，原存放输入数据的N个存储单元中依次存放输出的N个值； 这种利用同一存储单元存放蝶形计算输入、
8、输出数据的方法称为原位运算。可以节省存储单元,降低设备成本。,2. 倒位序规律 基2的DIT-FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，X(7)的顺序排列； 输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存储单元，看起来好像是“混乱无序”的； 实际上是有规律的，我们称之为倒位序。,n用二进制数表示为(n2n1n0)2（当N=8=23时，二进制为三位） 第一次分组，n为偶数（相当于n的二进制数的最低位n0=0）在上半部分，n为奇数（相当于n的二进制数的最低位 n0=1）在下半部分。 下一次则根据次最低位n1为“0”或是“1”来
9、分偶奇（而不管原来的子序列是偶序列还是奇序列）， 如此继续分下去，直到最后N个长度为1的子序列。,倒位序,N=8时的自然顺序二进制数和相应的倒位序二进制数,先按自然顺序将输入序列存入存储单元， 为了得到倒位序的排列，我们通过变址运算来完成； 如果输入序列的自然顺序号I用二进制数（例如n2n1n0）表示，则其倒位序J对应的二进制数就是（n0n1n2），这样，在原来自然顺序时应该放x(I)的单元，现在倒位序后应放x(J)。,顺序数I的起始、终止值分别为1和N-2； 倒序数J的起始值为N/2； 为避免重复调换，只对IJ的情况进行交换。,3. 蝶形运算两节点的“距离”,两节点“距离”,第一级蝶形 两节
10、点间 “距离”为1,第二级蝶形 两节点 间“距离”为2,第三级蝶形 两节点 间“距离“为4,N=2M点DIT-FFT，其第m级运算，每个蝶形的两节点“距离”为2m-1。,2m-1,系数Nr的变换规律： 其中N=2M，m=1,2,M，当N=8时，M=3,4. WNr的确定,令k=(n2n1n0)2 ； 将k= (n2n1n0)2左移(M-m)位,右边位置补零； 就可得到(r)2 的值，(r)2 =(k)22M-m 。,m=2， k=5 k=5=(101)2 左移M-m=1位 右边位置补零 r=(010)2 =2,4.4 按频率抽取（DIF）的基 -2 FFT算法,一、 算法原理,k=0, 1,
11、, N-1,当k=2r时，(-1)k=1；k=2r+1时，(-1)k=-1。,频率抽取法蝶形运算单元,N点 （N=8） DFT,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),按频率抽取的第一次分解,按频率抽取的第二次分解,x3(0),x3(1),X3(0),X3(1),按频率抽取的FFT（N=8）信号流图,N点x(n)序列，构造新序列 y(n)=x(n)NR2N(n), 试求：Y(K)与X(K)的关系，K=0,1,2,. 2N-1,例 题：,解：由DIF-FFT可得 y1(n)=x
12、(n)+x(n+N)=2x(n), y2(n)=x(n)-x(n+N)W2Nn=0,二、DIF-FFT的运算特点,频率抽取法蝶形运算单元,1、原位运算,2、蝶形运算 基2的DIF-FFT，输入为自然顺序，输出为位倒序； 两节点“距离”为2M-m=2M/2m=N/2m; 第m级运算：,系数Nr的变换规律： 其中N=2M，m=1,2,M，当N=8时，M=3,令k=(n2n1n0)2 ； 将k= (n2n1n0)2左移(m-1)位,右边位置补零； 就可得到(r)2 的值，(r)2 =(k)22m-1 。,3、 WNr的确定,4. 5 IDFT的高效算法,DIF-FFT信号流图,DIT-IFFT信号流
13、图,DITIFFT运算流图(防止溢出),直接调用FFT子程序计算IFFT，则可用下面的方法：,对上式两边同时取共轭，得,进一步减少运算量的措施：,多类蝶形单元运算 利用旋转因子的特殊值 旋转因子的生成 预先计算出旋转因子的数值存为表格，程序执行中直接查表得到所需旋转因子 实序列的FFT算法 利用DFT的共轭对称性,设x(n)是2N点实数序列， 试用一次N点DFT来计算x(n)的 2N点DFT：X(k), k=0,1,2N-1。,例 题,根据DITFFT的思想可得到,由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N点的值为,4.6 FFT的应用,线性卷积的FFT算法快速卷积,1
14、. FFT的快速卷积法 有限长单位脉冲响应h(n)与有限长输入信号x(n)的离散线性卷积。 设x(n)为M点，h(n)为N点， 输出为,y(n),=yc(n),=yl (n),LM+N-1,讨论： （1）M N，则L2M-12M，则,当M=512 时，运算速度可快16倍； 当M=4096 时， 约快100倍； M越长， 好处越明显。,（2） MN L=M+N-1M,短序列补很多零，长序列需全部输入后才能计算 存储容量大 运算时间长，处理延时很大，难于实时处理 怎么解决？块卷积（重叠相加和重叠保留法）,2重叠相加法 设h(n)的点数为N，将x(n)分解为很多段，每段为m点，各段互不重叠，m和N的
15、数量级相同，用xi(n)表示x(n)的第i段：,xi(n)为m点，yi(n)为（m+N-1）点； 相邻两段输出序列必然有（N-1）个点发生重叠，即前一段的后（N-1）个点和后一段的前（N-1）个点相重叠； 将重叠部分相加再和不重叠的部分共同组成输出。,特点： x(n)分段各数据子段互不重叠； h(n)与xi(n)各子段所作为线性卷积得yi(n)； yi(n)数据间有N-1点重叠； 最后的卷积结果y(n)为各子段线性卷积yi(n) 之和。,3 重叠保留法 将x(n)分段，每段L个点，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值， 组成N=L+M-1点序列xi(n
16、)； 如果L+M-12m， 则可在每段序列末端补零值点，补到长度为2m； 用DFT实现h(n)和xi(n)的N点圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。,重叠保留法示意图,重叠保留法示意图,用保留信号代替补零后的局部混叠现象,用保留信号代替补零后的局部混叠现象,为了说明以上说法的正确性，我们来看一看图3-29。任一段xi(n)（为N点）与h(n)（原为M点，补零值后也为N点）的N点圆周卷积,由于h(m)为M点，补零后作N点圆周移位时，在n=0,1,M-2的每一种情况下，h(n-m)NRN(m)在0mN-1范围的末端出现非零值， 而此处xi(m)是有数值存在的，图4-27（c），（d）为n=0, n=M-2的情况，所以在,0nM-2,这
