DSPFFT_深入浅出,详细讲解快速傅里叶变换.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章快速付里叶变换(,FFT)Fast FourierTransforming,第一节 引 言,一、快速付里叶变换,FFT,有限长序列通过离散傅里叶变换(,DFT),将其频 域离散化成有限长序列.但其计算量太大(与,N,的平方成正比）,很难 实时地处理问题 ,因 此 引 出 了 快 速 傅 里 叶 变 换(,FFT).,FFT,并 不 是 一 种 新 的 变 换 形 式,它 只 是,DFT,的 一 种,快 速 算 法,.并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了,FFT,的 多 种 算 法.,FFT,在 离 散 傅 里 叶 反 变 换 、线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用.。,二、,FFT,产生故事,当时加文(,Garwin),在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(,J.W.Turkey),正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(,Cooley J.W),图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利-图基在、,Mathematic of Computation,杂志上发表了著名的“机器计算付里级数的一种算法”文章，提出一种快速计算,DFT,的方法和计算机程序-揭开了,FFT,发展史上的第一页，促使,FFT,算法产生原因还有1967年至1968年间,FFT,的数字硬件制成，电子数字计算机的条件，使,DFT,的运算大简化了。,三、本章主要内容,1.直接计算,DFT,算法存在的问题及改进途径。,2.多种,DFT,算法(时间抽取算法,DIT,算法，频率抽取算法,DIF,算法，线性调频,Z,变换即,CZT,法),3.,FFT,的应用,第二节直接计算,DFT,算法存在的问题及改进途径,一、直接计算,DFT,计算量,问题提出：设有限长序列,x(n),非零值长度为,N,计算对,x(n),进行一次,DFT,运算，共需多大的运算工作量?,1.比较,DFT,与,IDFT,之间的运算量,其中,x(n),为复数，也为复数,所以,DFT,与,IDFT,二者计算量相同。,2.以,DFT,为例，计算,DFT,复数运算量,计算一个,X(k)(,一个频率成分)值，运算量为,例,k=1,则,要进行,N,次复数乘法+(N-1)次复数加法,所以，要完成整个DFT运算，其计算量为：,N*N,次复数相乘和,N*(N-1),次复数加法,3.一次,复数乘法换算成实数运算量,复数运算要比加法运算复杂，需要的运算时间长。,一个复数乘法包括,4个实数乘法和2个实数相法,。,(,a+jb)(c+jd)ac-bd)+j(bc+ad),4,次实数乘法,2,次实数加法,4.计算,DFT,需要的实数运算量,每运算一个,X(k),的值，需要进行,4,N,次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加.,整个,DFT,运算量为：,4,N,2,次实数相乘和2,N(2N-1),次实数相加.,由此看出：直接计算,DFT,时，乘法次数与加法次数都是和,N,2,成比例的。当,N,很大时，所需工作量非常可观,。,例子,例,1:,当,N=1024,点时，直接计算,DFT,需要：,N,2,=2,20,=1048576,次，即一百多万次的复乘运算,这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求-迫切需要改进,DFT,的计算方法，以减少总的运算次数。,例,2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点,/,秒，,每道总抽样点数=500*5=2500点,24道总抽样点数=24*2500=6万点,DFT,运算时间=,N,2,=(60000),2,=36*10,8,次,作业,二、改善,DFT,运算效率的基本途径,利用,DFT,运算的系数 的固有对称性和周期性，改善,DFT,的运算效率。,1.合并法：合并,DFT,运算中的某些项。,3.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。,利用,DFT,运算的系数 的固有对称性和周期性，改善,DFT,的运算效率,的对称性：,的周期性：,因为：,由此可得出：,例子,例:,利用以上特性,得到改进,DFT,直接算法的方法.,(,1)合并法：步骤1分解成虚实部,合并,DFT,运算中的有些项,对虚实部而言,所以带入,DFT,中：,(1)合并法：步骤2代入,DFT,中,展开：,(1)合并法：步骤3合并有些项,根据：,有：,(1)合并法：步骤4结论,由此找出其它各项的类似归并方法：乘法次数可以减少一半。,例：,2、将长序列,DFT,利用对称性和周期性分解为短序列,DFT-,思路,因为,DFT,的运算量与,N,2,成正比的,如果一个大点数,N,的,DFT,能分解为若干小点数,DFT,的组合，则显然可以达到减少运算工作量的效果。,2、将长序列,DFT,利用对称性和周期性分解为短序列,DFT-,方法,把,N,点数据分成二半：,其运算量为：,再分二半：,+,=,+,+,+,=,这样一直分下去，剩下,两点的变换,。,2、将长序列,DFT,利用对称性和周期性分解为短序列,DFT-,结论,快速付里时变换(,FFT),就是在此特性基础上发展起来的，并产生了多种,FFT,算法，其基本上可分成两大类：,按抽取方法分：,时间抽取法(DIT);频率抽取法(DIF),按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法,其它方法：线性调频Z变换,(,CZT,法),第三节基-2按时间抽取的,FFT,算法D,ecimation-in-Time(DIT)(Coolkey-Tukey),一、算法原理,设输入序列长度为N=2,M,(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。,其中基数2-N=2,M,，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2,M,例子,设一序列,x(n),的长度为L=9,应加零补长为,N=2,4,=16,应补7个零值。,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,n,x(n),二、算法步骤,1.分组，变量置换,DFT,变换：,先将,x(n),按n,的奇偶分为两 组，作变量置换,:,当n=偶数时，令n=2r;,当n=奇数时，令n=2r+1;,得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0N/2-1;,则可得其DFT为两部分：,前半部分,：,后半部分,：,2.代入,DFT,中,生成两个子序列,x(0),x(2)x(2r),偶数点,x(1),x(3)x(2r+1),奇数点,代入,DFT,变换式：,3.求出子序列的,DFT,上式得：,4.结论1,一个,N,点的DFT被分解为两个N/2点DFT。X,1,(k),X,2,(k)这两个N/2点的DFT按照：,再应用,W,系数的周期性，求出用X,1,(k),X,2,(k)表达的后半部的X(k+N/2)的值。,5.求出后半部的表示式,看出：后半部的,k,值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。,6.结论2,频域中的,N,个点频率成分为：,结论：只要求出（0,N/2-1）,区间内的各个整数k值所对应的X,1,(k),X,2,(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。,7.结论3,由于,N=2,M,，,因此,N/2,仍为偶数，可以依照上面方法进一步把每个,N/2,点子序列，再按输入,n,的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是,加减运算,。,三、蝶形结,即蝶式计算结构也即为蝶式信号流图,上面,频域,中前/后半部分表示式可以用蝶形信号流图表示。,X,1,(k),X,2,(k),作图要素：,(1)左边两路为输入,(2)右边两路为输出,(3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出),(,4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。,(,5)当支路上没有箭头及系数时，则该支路的传输比为1。,例子：求,N=2,3,=8,点,FFT,变换,（1）先按,N=8-N/2=4，,做4点的DFT,：,先将N=8DFT分解成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)给出,(a)比较,N=,8,点直接DFT与分解2个4点DFT的FFT运算量,N=8,点的,直接DFT,的计算量为：N,2,次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。,（b)求 一个蝶形结需要的运算量,要运算一个蝶形结，需要一次乘法 ，两次加法。,（,c）,分解为两个,N/2=4,点的,DFT,的运算量,分解2个N/2点（4点的DFT：,偶数,其复数相乘为,复数相加为,奇数,其复数相乘为,复数相加为,(,d),用2个4,点来求N=8点的FFT所需的运算量,再将,N/2,点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算,还需,N/2,次（4次）乘法 及 次(8次）加法运算。,(,e),将,N=8,点分解成2个4点的DFT的信号流图,4,点,DFT,x(0),x(2),x(4),x(6),4,点,DFT,x(1),x(3),x(5),x(7),X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),X,1,(0),X,1,(1),X,1,(2),X,1,(3),X,2,(0),X,2,(1),X,2,(2),X,2,(3),偶数序列,奇数序列,X(4)X(7),同学们自已写,x1(r),x2(r),(2),N/2(4,点)-,N/4(2,点),FFT,(a),先将4点分解成2点的,DFT：,因为4点,DFT,还是比较麻烦，所以再继续分解。,若将,N/2(4,点)子序列按奇/偶分解成两个N/4点（2点）子序列。即对将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。,(,b),求2点的,DFT,（,c),一个2点的,DFT,蝶形流图,2点,DFT,2点,DFT,x(0),x(4),x(2),x(6),X3(0),X3(1),X4(0),X4(1),X,1,0),X,1,(1),X,1,(2),X,1,(3),（,d),另一个2点的,DFT,蝶形流图,2点,DFT,2点,DFT,x(1),x(5),x(3),x(7),X5(0),X5(1),X6(0),X6(1),X,2,(0),X,2,(1),X,2,(2),X,2,(3),同理：,(3)将,N/4（2,点）DFT再分解成2个1点的DFT,(a)求2个一点的DFT,最后剩下两点,DFT,它可分解成两个一点,DFT，,但一点,DFT,就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。,(,b)2,个1点的,DFT,蝶形流图,1点,DFT,x(0),1点,DFT,x4),X3(0),X3(1),进一步简化为蝶形流图：,X3(0),X3(1),x(0),x(4),(4,),一个完整,N=8,的按时间抽取FFT的运算流图,x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7),X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),m=0,m=1,m=2,四、,FFT,算法中一些概念,（,1）“级”概念,将,N,点,DFT,先分成两个,N/2,点,DFT，,再是四个N/4点DFT直至N/2个两点DFT.每分一次称为“一”级运算。,因为N=2,M,所以N点DFT可分成M级,如上图所示依次m=0,m=1.M-1共M级,（2）“组”概念,每一级都有,N/2,个蝶形单元，例如：N=8,则每级都有4个蝶形单元。,每一级的,N/2,个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：,例：,N=8=2,3,，,分3,级。,m=0,级,分成四组,每组系数为,m=1,级,分成二组,每组系数为,m=2,级,分成一组,每组系数为,(3)因子的分布,结论：每由后向前（,m,由,M-1-0级）推进一级，则此系数为后级系数中偶数序号的那一半。,（,4）按时间抽取法,2点,DFT,2点,DFT,2点,DFT,2点,DFT,2点,DFT,2点,DFT,2点,DFT,2点,DFT,两个2点,DFT,两个2点,DFT,两个2点,DFT,两个2点,DFT,两个,4点,DFT,两个,4点,DFT,两个,N/2,点,DFT,X,1,(k),.,X,2,(k),X(k),由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法”.,x(n),五、按时间抽取的,FFT,算法与直接计算DFT运算量的比较,由前面介绍的按时间抽取的,FFT,运算流图可见：,每级都由,N/2,个蝶形单元构成，因此每一级运算都需要,N/2,次复乘和,N,次复加（每个结加减各一次）。这样（N=2,M,)M级运算共需要：,复乘次数：,复加次数：,可以得出如下结论：,按时间抽取法所需的复乘数和复加数都是与,成正比。而直接计算DFT时所需的复乘数与复加数则都是与N,2,成正比.(复乘数md=N,2,复加数ad=N(N-1)N,2,),例子,看,N=8,点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。,看出：当,N,较大时，按时间抽取法将比直接法快一、二个数量级之多。,作业,六、按时间抽取,FFT,算法的特点,根据,DIT,基,2-FFT算法原理，能得出任何N=2,m,点的FFT信号流图，并进而得出FFT计算程序流程图。最后总结出按时间抽取法解过程的规律。,1.原位运算（in-place),2.码位倒读规则,1.原位运算（,in-place),原位运算的结构，可以节省存储单元，降低设备成本。,定义：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出。,x(0),x(4),X3(0),X3(1),例子,例：,N=8 FFT,运算,输入:,x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7),A(0),A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(0),A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(0),A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(0)=x(0),A(1)=x(1),A(2)=x(2),A(3)=x(3),A(4)=x(4),A(5)=x(5),A(6)=x(6),A(7)=x(7),R1,R1,R1,R1,R1,R2,R1,R1,R2,R2,R3,R4,看出：用原位运算结构运算后，,A(0)A(7),正好顺序存放X(0)X(7),可以直接顺序输出。,2.码位倒读规则,我们从输入序列的序号及整序规律得到码位倒读规则。由,N=8,蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2),x(6).的顺序存入存储单元即为,乱序输入,，,顺序输出,。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。,例子,以,N=8,为例：,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,自然顺序,二进制码表示,码位倒读,码位倒置顺序,000,100,010,110,001,101,011,111,0,4,2,6,1,5,3,7,看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。,整序重排子程序,具体执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一个中间存储单元。,n,0,1,2,3,4,5,6,7,n,0,4,2,6,1,5,3,7,在实际运算时，先按自然顺序将输入序列存入存储单元再通过变址运算将自然顺序变换成按时间抽取的,FFT,算法要求的顺序。,变址的过程可以用程序安排加以实现-称为“整序”或“重排”（采用码位倒读）且注意：,(1)当,n=n,时，数据不必调换；,(2)当,nn,时，必须将原来存放数据x(n)送入暂存器R，再将x(n)送入x(n),R中内容送x(n).进行数据对调。,(3)为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。nn时，调换。,作业,编写,N=128,点的基2-按时间抽取的,FFT,算法。要求用C语言编写，并将输入数据放在文件inputdata.dat中，输出数据放在outputdata.dat文件中。,七、按时间抽取的,FFT,算法的若干变体,1.思路,对于任何流图，只要保持各节点所连续的支路及其传输系数不变，则不论节点位置怎么排列所得流图总是等效的，最后所得结果都是,x(n),的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。,(,2)输入是自然顺序而输出是乱序,将原先中与,x(4),水平相邻的所有节点跟x(1)水平相邻的所有节点位置对调；将原先中与x(6)水平相邻的所有节点跟x(3)水平相邻的所有节点位置对调，其余诸节点保持不变，则可得：,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),X(0),X(4),X(2),X(6),X(1),X(3),X(5)X(7),它与输入是乱序，输出顺序比较，看出：相同点：运算量一样；不同点：第一是数据存入方式不同；第二是取用系数的顺序不同。,(,2)输入和输出都是自然顺序,对输入自然顺序，输出乱序的第二级，第三级节点作调整，可得输入输出都是顺序，无需数据重排,：,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),（1）它失掉了“原位运算”的性质。（2）为了变换,N,点数据，至少需要2N个复数单元。在内存比较紧张时，而对输入数据整序并不困难时一般不用。为了争取速度，才采取这种变体。,第四节基-2按频率抽取的,FFT,算法D,ecimation-in-Frequency(DIF,)(Sander-,Tukey,),一、算法原理,设输入序列长度为N=2,M,(M为正整数，将该序列的频域的输出序列X(k)(也是M点序列，按其,频域,顺序的,奇偶分解,为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。,二、算法步骤,1.分组,DFT,变换：,已证明频域上,X(k),按k的奇偶分为两组，在时域上x(n)按n的顺序分前后两部分，现将输入x(n)按n的顺序分前后两部分,:,前半子序列x(n),0,nN/2-1,;,后半子序列x(n+N/2),0,nN/2-1,;,例：N=8时，前半序列为：x(0),x(1),x(2),x(3);,后半序列为：x(4),x(5),x(6),x(7);,则由定义输出（求DFT）,2.代入,DFT,中,3.,变量置换-1,3.,变量置换-2,3.,变量置换-3,3.,变量置换-4,4.结论1,一个,N,点的DFT被分解为两个N/2点DFT。X,1,(k),X,2,(k)这两个N/2点的DFT按照：,可见：如此分解，直至分到2点的,DFT,为止。,4.结论2,三、蝶形流图表示,蝶形单元：,时域,中，前后半部表示式用蝶形结表示。,x(n),x(n+N/2),与时间抽取法的推演过程一样，由于,N=2,L,N/2,仍为偶数，所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。,例子：求,N=2,3,=8,点,DIF,（1）先按,N=8-N/2=4，,做4点的DIF,：,先将N=8DFT分解成2个4点DFT,：,可知：时域上：,x(0),x(1),x(2),x(3),为前半,序列,x(4),x(5),x(6),x(7),为后半序列,产生新的子序列：x,1,(n)、x,2,(n),频域上：X(0),X(2),X(4),X(6)由x,1,(n)给出,X(1),X(3),X(5),X(7),由x,2,(n)给出,将,N=8,点分解成2个4点的DIF的信号流图,4点,DFT,x(0),x(1),x(2),x(3),4点,DFT,x(4),x(5),x(6),x(7),X(0),X(2),X(4),X(6),X(1),X(3),X(5),X(7),X,1,(k),前半部分序列,后半部分序列,x1(n),x2(n),X,2,(k),(2),N/2(4,点)-,N/4(2,点),FFT,(a),先将4点分解成2点的,DIF：,因为4点,DIF,还是比较麻烦，所以再继续分解。,（b,),一个2点的,DIF,蝶形流图,2点,DFT,2点,DFT,x1(0),x1(1),x1(2),x1(3),x3(0),x3(1),x4(0),x4(1),X(0),X(4),X(2),X(6),(c)另,一个2点的,DIF,蝶形流图,2点,DFT,2点,DFT,x2(0),x2(1),x2(2),x2(3),x5(0),x5(1),x6(0),x6(1),X(1),X(5),X(3),X(7),(3)将,N/4（2,点）DFT再分解成2个1点的DFT,(a)求2个一点的DFT,最后剩下两点,DFT,它可分解成两个一点,DFT，,但一点,DFT,就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。,(,b)2,个1点的,DFT,蝶形流图,1点,DFT,x30),1点,DFT,x3(1),X(0),X(4),进一步简化为蝶形流图：,X(0),X(4),x3(0),x3(1),(4,),一个完整,N=8,的按频率抽取FFT的运算流图,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),X(0),X(4),X(2),X(6),X(1),X(5),X(3),X(7),m=0,m=1,m=2,(5),DIF,的特点,(,a),输入自然顺序，输出乱序且满足码位倒置规则。,(b)根据时域、频域互换，可知：,输入乱序，输出自然顺序。,（6）,DIF,与DIT比较1,相同之处：,（1）,DIF,与DIT两种算法均为原位运算。,（2）DIF与DIT运算量相同。,它们都需要,（6）,DIF,与DIT比较2,不同之处：,（1）,DIF,与DIT两种算法结构倒过来。,DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。,DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。,（2）DIF与DIT根本区别：在于蝶形结不同。,DIT的复数相乘出现在,减法之前,。,DIF的复数相乘出现在,减法之后,。,作业,第五节,IFFT,运算方法,以上所讨论的,FFT,的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算FFT的方法。,一、利用,FFT,计算IFFT的思路1,将下列两式进行比较,二、利用,FFT,计算IFFT的思路2,利用,FFT,计算IFFT时在命名上应注意：,(1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k),原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了。,（2）同样，频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。,三、改变,FFT,流图系数的方法1.思路,在,IFFT,的运算中，常常把1/N分解为(1/2),m,，并且在M级运算中每一级运算都分别乘以1/2因子，就可得到IFFT的两种基本蝶形运算结构。并不常用此方法）,2.,IFFT,的基本蝶形运算,A,B,A,B,(,a),频率抽取IFFT的蝶形运算,(,b),时间抽,取IFFT的蝶形运算,四.直接利用,FFT,流图的方法1.思路,前面的两种,IFFT,算法，排程序很方便，但要改变FFT的程序和参数才能实现。,现介绍第三种IFFT算法，则可以完全不必改动FFT程序。,2.直接利用,FFT,流图方法的推导,可知：只须将频域成份一个求共轭变换，即（1）将,X(k),的虚部乘以-1，即先取,X(k),的共轭，得X,*,(k)。(2)将X,*,(k)直接送入FFT程序即可得出Nx,*,(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。,此为,DFT,可用FFT程序,3.直接利用,FFT,流图方法的注意点,（1）,FFT,与IFFT连接应用时，注意输入输出序列的排列顺序，即应注意是自然顺序还是倒序。,（2）FFT和IFFT共用同一个程序时，也应注意利用FFT算法输入输出的排列顺序，即应注意自然顺序还是例位序,（3）当把频率抽取FFT流图用于IDFT时，应改称时间抽取IFFT流图。,（4）当把时间抽取FFT流图用于IDFT时，应改称频率抽取IFFT流图。,作业,用,C,语言完成N=1024点的IDIT，IDIF。,第六节线性调频,Z,变换,一、引入,以上提出,FFT,算法，可以很快地求出全部DFT值。即求出有限长序列x(n)的z变换X(z)在单位园上N个等间隔抽样点z,k,处的抽样值。它要求N为高度复合数。即N可以分解成一些因子的乘积。例N=2,L,实际上：（1）也许对其它围线上,z,变换取样发生兴趣。如语音处理中，常常需要知道某一围线z变换的极点所处的复频率。,（2）只需要计算单位圆上某一段的频谱。如窄带信号，希望在窄带频率内频率抽样能够非常密集，提高分辨率，带外则不考虑。,（3）若N是大素数时，不能加以分解，又如何有效计算这种序列DFT。例N=311，若用基2则须补N=2,8,=512点，要补211个零点。,二、问题提出,由上面三个问题提出：,为了提高,DFT,的灵活性须用新的方法。,线性调频z变换(CZT)就是适用这种更为一般情况下，由x(n)求X(z,k,)的快速变换,CZT：来自于雷达专业的专用词汇。,三、算法原理1.定义,Z,变 换 采 用,螺 线 抽 样,可 适 用 于 更 一 般 情 况 下 由,x(n,),求,X(z,k,),的 快 速 算 法,这 种 变 换 称 为 线 性 调 频,Z,变 换(简 称,CZT).,2.,CZT,公式推导1,为适应,z,可以沿平面内更一般的路径取值，故：,沿z平面上的一段螺线作等分角的抽样，则z的取样点Zk可表示为：,已 知,x(n)，0nN-1,则它的,z,变换是：,其中M：表示欲分析的复频谱的点数。M不一定等于N。A，都为任意复数。,2.,CZT,公式推导2,2.,CZT,公式推导3,3.用,CZT,求解DFT的流图,4.,CZT,变换各点的值,5、图形,6、说明1,（1）,A,为起始样点位置,6、说明2,（2）,z,k,是z平面一段螺线上的等分角上某一采样点。,6、说明3,6、说明4,6、说明5,7、,CZT,的实现步骤,1,7、,CZT,的实现步骤2,7、,CZT,的实现步骤3,7、,CZT,的实现步骤4,7、,CZT,的实现步骤5,7、,CZT,的实现步骤6,7、,CZT,的实现步骤7,8、,CZT,变换运算流程图,9、,CZT,运算量的估算1,9、,CZT,运算量的估算2,10、,CZT,运算量与直接运算量比较,当,M、N,足够小时，直接算法运算量少。,但M、N值比较大时（大于50），CZT算法比直接算法的运算量少得多。,例M=50，N=50，N*M=2500次,而CZT1600次。,11、,CZT,算法的特点,与标准,FFT,算法相比，CZT算法有以下特点：,（1）输入序列长N及输出序列长M不需要相等。,（2）N及M不必是高度合成数，二者均可为素数。,（3）Z,k,的角间隔 是任意的，其频率分辨率也是任意的。,（4）周线不必是z平面上的圆，在语音分析中螺旋周线具有某些优点。,（5）起始点z,0,可任意选定，因此可以从任意频率上开始对输入数据进行窄带高分辨率的分析。,（6）若A=1,M=N,可用CZT来计算DFT，即使N为素数时，也可以。,总之，CZT算法具有很大的灵活性，在某种意义上说，它是一个一般化的DFT。,12、,CZT,变换的应用1,（1）利用,CZT,变换计算DFT。,12、,CZT,变换的应用2,（2）对信号的频谱进行细化分析。其中对窄带信号频谱或对部分感兴趣的频谱进行细化分析。,这样,CZT,只对感兴趣的频率区段进行采样。计算量小很多，有利于实时处理。或在保证实时处理的情况下，可大提高频率分辨率。,12、,CZT,变换的应用3,（3）求解z变换X(z)的零、极点。,用于语音信号处理过程中。,具体方法：利用不同半径同心圆，进行等间隔的采样。,作业,第七节 分裂基,FFT,算法,一、发展史,自从基2快速算法出现以来，人们仍在不断寻求更快的算法。基4,FFT,算法就比最初的基2FFT算法更快。,从理论上讲，用较大的基数还可以进一步减少运算次数，但要以程序（或硬件）变得更为复杂为代价。甚至得不偿失。,1984年，法国的杜梅尔(P.Dohamel)和霍尔曼(H.Hollmann)将基2分解和基4分解糅合在一起，提出了分裂基FFT算法。其运算量比前几种算法都有所减少，运算流图却与基2FFT很接近，运算程序也很短。它是目前一种实用的高效新算法。,二、分裂基,FFT,算法原理,结论1,N/2,点,DFT,N/4,点,DFT,.,.,.,N/4,点,DFT,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,-,j,结论2,结论3,例子,下面以,N=16,为例，说明完整的分裂基FFT运算流图的画法和排列形式。,N/2,点,（8点）,DFT,N/4,点,（4点）,DFT,N/4,点,（4点）,DFT,-,j,-,j,-,j,-,j,N/4,点,（4点）,DFT,-,j,-,j,-,j,同理，用同样方法可以画出4点分裂基,FFT,算法L形运算流图.,-,j,-,j,-,j,-,j,-,j,-,j,-,j,-,j,-,j,结论,由图可看出，分裂基,FFT,算法结构同基2FFT算法结构相似，适用于N=2,M,的场合，并由M级运算实现。,运算流图输入为顺序，输出为倒序。,分裂基,FFT,算法的运算量,作业,第八节,FFT,的应用,凡是利用付里叶变换来进行分析、综合、变换的地方，都可以利用,FFT,算法来减少其计算量。,FFT主要应用在,（1）快速卷积,（2）快速相关,（3）频谱分析,一、快速卷积,设,x(n,),的长度为N点，h(n)的长度为M点，则：,y(n)的长度为N+M-1点。所以直接计算y(n)线性卷积运算量为NM。,1.利用圆周卷积代替线卷积,用圆周卷积（,FFT）,代替线卷积的必要条件：x(n)、h(n)补零加长至L=N+M-1.,然后计算圆卷积。求出y(n)代表线卷积。,2、用,FFT,计算,y(n,),的步骤,(1)求,H(k,)=,DFTh(n,)(L,点）,(2)求X(k)=DFTx(n)(L点）,(3)计算Y(k)=X(k)H(k)(L点）,(4)求y(n)=IDFTY(k)(L点）,2、用,FFT,计算,y(n,),与直接计算y(n)的运算量比较,3、分段卷积的方法,（1）重叠相加法,（2）重叠保留法,设,x(n,),的长度为长序列,N，h(n,),为短序列列,M。,（1）重叠相加法1,（1）,x(n,),为分段，每段长为,p,点，,p,选择与M数量组相同。用x,i,(n)表示x(n)的第i段.,（1）重叠相加法2,（1）重叠相加法例子,（2）重叠保留法1,（2）重叠保留法2,（2）重叠保留法例子,二、快速相关1.方法,2.步骤,三、频谱分析,这里我们仅介绍,FFT,的仪器设备：快速付里叶分析仪。,其功能为：,（1）能分析确定性信号的频谱。,（2）估计随机信号的功率谱,（3）并对信号进行快速卷积滤波,（4）计算相关函数,1.频谱分析仪的框图,数据选择器,A/D,保护滤波器,输入电路,输入,数据存储器,运算器,数据选择器,控制器,变址单元,函数发生器,输出缓冲器,D/A,输出,2.部件说明,（1）保护滤波器：对输入信号进行模拟滤波，滤掉噪声，提取感兴趣的有用信号，以便分析频谱2）运算器：完成时间抽取,FFT,或,Chirp-Z,变换所要求运算。,（3）,RAM:,存储输入数据。,（4）,ROM(,函数发生器）。以表格形式存放蝶形运算因子,W.,(5),变址单元：根据输入数据，进行码位倒置排序。,总结,直接用,DFT,计算运算量与用,FFT,计算的运算量比较，,及减少运算量的改进途径。,2.多种,DFT,算法(时间抽取算法,DIT,算法，频率抽取算法,DIF,算法，线性调频,Z,变换即,CZT,法),3.,FFT,的应用,直接用,DFT,计算的运算量与用,FFT,计算的运算量比较，减少运算量的,途径,复习,DFT,的运算量,基2-按时间抽取算法,基2-按频域抽取算法,基2-,FFT,的运算量,CZT变换,