第四章 快速傅里叶变换(FFT)PPT学习课件.ppt

第四章快速傅里叶变换（FFT）,1,主要内容,DIT-FFT算法DIF-FFT算法IFFT算法Chirp-FFT算法线性卷积的FFT算法,学习目标理解按时间抽选的基-2FFT算法的算法原理、计算量和运算流图的特点理解按频率抽选的基-2FFT算法的算法原理、计算量和运算流图的特点理解IFFT算法了解CZT算法理解线性卷积的FFT算法及分段卷积方法,4.1直接计算DFT的运算量、减少运算量的途径,同理：IDFT运算量与DFT相同。,（1）DFT的运算量,（2）减少DFT运算量的途径,a.由的性质，合并DFT中的某些项,周期性：,共轭对称性：,可约性：,基于以上特性，得出一些特殊值：,b.由于运算量和成正比，因而可将N点的DFT分解成小点数的DFT,以减少运算量,4.2按时间抽取（DIT）的基-2FFT算法（库利-图基算法）,按时间抽取（DecimationInTime，DIT）,（1）算法原理设序列x(n)点数为N=2L，L为正整数。,将序列x(n)按n的奇偶分成两组：,N为2的整数幂的FFT算法称基-2FFT算法。,将N点DFT定义式分解为两个长度为N/2的DFT,记：（1）,再利用周期性求X(k)的后半部分,将上式的运算用一个专用蝶形运算流图表示。,a.乘法支路,标箭头表示b.当支路上没有标出系数时，则该支路的传输系数为1,将一个N点的DFT分解为两个2个N/2的DFT(N=8),分解后的运算量：,运算量减少了近一半,进一步分解,由于，仍为偶数，因此，两个点DFT又可同样进一步分解为4个点的DFT。,由两个N/4点的DFT组合成一个N/2点的DFT,同理：,其中：,将一个N点DFT分解为四个N/4点的DFT（N=8）,这样逐级分解，直到2点DFT当N=8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1,按时间抽取，N=8点FFT算法流图,（2）若不满足N=2L时，则在序列x(n)后补上零值点，使达到这一要求,（3）共有L=log2N级运算，每一级有N/2个蝶形结,m=1表示第一级蝶形运算，为输入序列,m=L表示最后一级蝶形运算，为输出序列,i,j表示本级蝶形运算中的两个节点符号,（4）同（原）址运算基本蝶形满足同址运算,蝶形输出的两节点值放到原输入的两节点的存储器中。,（5）输入倒位序，输出自然序,（5）输入倒位序，输出自然序,（5）输入倒位序，输出自然序,例计算，。计算点FFT。用时间抽取输入倒序算法，问倒序前寄存器的数和倒序后的数据值？,解：倒序前倒序倒序为倒序后,（6）蝶形结的运算公式,第m级运算每个蝶形结的两节点距离为2m1,a.蝶形结两节点间的距离,b.第m级蝶形结计算公式,蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移Lm位，把右边空出的位置补零，结果为r的二进制数。,c.的确定：第m级的r取值：,（7）DITFFT与DFT相比的运算效率,复数乘法：,复数加法：,比较DFT,DIT-FFT的运算量为(),(8)、DIT-FFT算法的其他形式流图,输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序,时间抽取、输入自然顺序、输出倒位序的FFT流图,时间抽取，输入、输出皆为自然顺序的FFT流图,时间抽取，各级具有相同集合形状，输入倒位序、输出自然序,时间抽取，各级具有相同集合形状，输入自然序、输出倒位序,例用FFT算法处理一幅NN点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为次，仅为直接计算DFT所需时间的10万分之一。即原需要3000小时，现在只需要2分钟。,4.3按频率抽取（DIF）的基-2FFT算法（桑德-图基算法）,按频率抽取（DecimationInFrequency，DIF),（1）算法原理设序列x(n)点数为N=2L，L为正整数。,与DIT-FFT算法类似分解，但是抽取的是X(k)。即分解X(k)成奇数与偶数序号的两个序列。设：N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：,下面讨论,按k的奇偶将X(k)分成两部分：,显然：,令：,用蝶型结构图表示为：,按频率抽取，将N点DFT分解成两个N/2点DFT的组合,N/2仍为偶数，进一步分解：N/2N/4,按照以上思路继续分解，即一个N/2的DFT分解成两个N/4点DFT，直到只计算2点的DFT，这就是DIF-FFT算法。,N=8基-2DIF-FFT流图,（2）若不满足N=2L时，则在序列x(n)后补上零值点，使达到这一要求,（3）输出序列按X（k）按k分成两组，等价于将输入x(n)按n的顺序分成前后两半,（4）输入自然循序、输出倒位序，变址运算方法有DIT相同,m=1表示第一级蝶形运算，为输入序列,m=L表示最后一级蝶形运算，为输出序列,i,j表示本级蝶形运算中的两个节点符号,（6）同（原）址运算,（5）有L级蝶形运算,对N=2L点FFT，输入自然序，输出倒位序,b.第m级运算：,（7）蝶形结的运算公式,a.第m级蝶形结两点间的距离,c.的确定：第m级的r取值：,蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移m-1位，把右边空出的位置补零，结果为r的二进制数。,存储单元,输入序列x(n):N个存储单元,系数：N/2个存储单元,4.4DIT-FFT与DIF-FFT的异同,基本蝶形不同,DIT:先复乘后加减,DIF:先减后复乘,运算量相同,都可原位运算,DIT和DIF的基本蝶形互为转置,4.5傅立叶反变换（IDFT）的快速算法IFFT算法,一、从定义比较分析,与DFT的比较：1）、旋转因子WN-kn的不同；2）、结果还要乘1/N。,二、实现算法直接使用FFT程序的算法,直接调用FFT子程序计算IFFT的方法：,1.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。,复乘所需时间,复加所需时间,所以直接利用DFT计算所需时间：,复乘所需时间,复加所需时间,所以用FFT计算所需时间,(2)利用计算：复乘次数为，复加次数为。,2.已知，是两个N点实序列，的值，今需要从，求，的值，为了提高运算效率，试用一个N点运算一次完成。,例：设x1(n)和x2(n)都是N点的实数序列，试用一次N点DFT运算来计算它们各自的DFT:,构造序列,对作一次N点IFFT可得序列,又根据DFT的线性性质,而，都是实序列,3.N=16时，画出基-2按时间抽取法及按频率抽取法的FFT流图（时间抽取采用输入倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。,解：,(1)按时间抽取的基-2FFT流图,共有L=4级蝶形运算，每级N/2=8个蝶形运算,每个蝶形的两节点距离为，即从第一级到第四级两节点距离分别为1，2，4，8。,(2)按频率抽取的基-2FFT流图,基本蝶形是DIT蝶形的转置,同样共有L=4级蝶形运算，每级N/2=8个蝶形运算,每个蝶形的两节点距离为，即从第一级到第四级两节点距离分别为8，4，2，1。,4.9线性调频Z变换（Chirp-Z变换或CZT）算法,单位圆与非单位圆采样（a）沿单位圆采样;(b)沿AB弧采样,螺线采样,zk=AW-k,k=0,1,M-1,Chirp-Z变换的线性系统表示,由于系统的单位脉冲响应可以想象为频率随时间(n)呈线性增长的复指数序列。在雷达系统中,这种信号称为线性调频信号（ChirpSignal），因此，这里的变换称为线性调频Z变换。,一、基本算法思路,4.7线性卷积的FFT算法（FFT应用三）,若L点x(n)，M点h(n)，则直接计算其线性卷积y(n),需运算量：,若系统满足线性相位，即：,则需运算量：,FFT法：以圆周卷积代替线性卷积,N,总运算量：次乘法,比较直接计算和FFT法计算的运算量,讨论：,1）当,2）当,x(n)长度很长时，将x(n)分为L长的若干小的片段，L与M可比拟。,1、重叠相加法,则：,输出：,其中：,可以用圆周卷积计算：,选，上面圆周卷积可用FFT计算。,N,由于yi(n)长度为N，而xi(n)长度L，必有M-1点重叠，yi(n)应相加才能构成最后y(n)的。,重叠相加法图形,和上面的讨论一样，用FFT法实现重叠相加法的步骤如下:计算N点FFT，H(k)=DFTh(n)；计算N点FFT，Xi(k)=DFTxi(n)；相乘，Yi(k)=Xi(k)H(k)；计算N点IFFT，yi(n)=IDFTYi(k)；将各段yi(n)（包括重叠部分）相加，。重叠相加的名称是由于各输出段的重叠部分相加而得名的。,例已知序列xn=n+2,0n12,hn=1,2,1试利用重叠相加法计算线性卷积,取L=5。,yn=2,7,12,16,20,24,28,32,36,40,44,48,52,41,14,解:重叠相加法,x1n=2,3,4,5,6,x2n=7,8,9,10,11,x3n=12,13,14,y1n=2,7,12,16,20,17,6,y2n=7,22,32,36,40,32,11,y3n=12,37,52,41,14,2、重叠保存法,此方法与上述方法稍有不同。先将x(n)分段，每段L=N-M+1个点，这是相同的。不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值，组成L+M-1点序列xi(n)。如果L+M-12m，则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。,重叠保留法示意图,重叠保留法示意图,yk=2,7,12,16,20,24,28,32,36,40,44,48,52,41,14,x1k=0,0,2,3,4,x2k=3,4,5,6,7,x3k=6,7,8,9,10,y1k=x1khk=11,4,2,7,12,x4k=9,10,11,12,13,y2k=x2khk=23