第四章快速傅氏变换

9/29/2024,河北理工大学,河北理工大学,第四章快速傅氏变换,Down,Up,Main,Return,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章,快速傅氏变换,引言：,离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。,但是，如果使用定义式来直接计算,DFT,，当,N,很大时，即使使用高速计算机，所花的时间也太多。因此，如何提高计算,DFT,的速度，便成了重要的研究课题。,1965,年,库利,(Cooley),和,图基,(,Tukey,),在前人的研究成果的基础上提出了快速计算,DFT,的算法，之后，又出现了各种各样快速计算,DFT,的方法，这些方法统称为快速傅里叶变换,(FastFourier Transform),，简称为,FFT,。,快速傅里叶变换(,FFT,)是离散傅里叶变换(,DFT,)的快速算法,它是,DSP,领域中的一项重大突破，它考虑了计算机和数字硬件实现的约束条件、研究了有利于机器操作的运算结构，使,DFT,的计算时间缩短了,12,个数量级，还有效地减少了计算所需的存储容量。,FFT,技术的应用极大地推动了,DSP,的理论和技术的发展，,成为数字信号处理强有力的工具。,其中,在导出,FFT,算法之前，先估计一下直接计算DFT所需计算量。,DFT的定义,将方程组写成矩阵形式,将DFT定义式展开成方程组,同理,用复数表示：,用向量表示：,从矩阵形式表示可以看出,每计算一个X(k)值需要N次复乘法和(N-1)次复数加法，因而计算N个X(k)值，共需N,2,次复乘法和N(N-1)次复加法。,每次复乘法包括4次实数乘法和2次实数加法，每次复加法包括2次实数加法，,因此计算N点的DFT共需要4N,2,次实数乘法和(2N,2,+2N(N-1)次实数加法。当N很大时，这是一个非常大的计算量。 例如当N=1024，N,2,=1048576。,在实际中，N往往是比较大的，因此有必要对DFT的计算予以改进。,(1),对称性,或,(2),周期性,(3),可约性,或,(4),其它,首先考察,W,N,nk,的一些特殊性质：,4.1基2时间抽选法（库里图基算法）,一、基本原理,：利用旋转因子,W,N,nk,的对称性和周期性，将一个长序列x(n)的DFT计算，在时域上按奇偶抽选分解成短序列的DFT来计算。,设,N,2,M,，,M,为正整数。为推导方便，取,N,2,3,8,，即离散时间信号为,x(n,)=x(0), x(1), x(2), x(3), x(4), x(5), x(6),x(7),将序列,x(n,),分为奇偶两组，一组序号为偶数，另一组序号为奇数，即,x(0), x(2), x(4), x(6) | x(1), x(3), x(5), x(7),分别表示为：,g(r,) = x(2r) ,偶数项,h(r,) = x(2r+1) ,奇数项,r=0, 1, , N/2-1,因为,W,N,2,=,W,N/2,1,，所以上式变为,上式中的,G(k),和,H(k),都是,N/2,点的,DFT,。,根据DFT的定义,k=0, 1, , N/2-1 (4.1),要用,G(k),和,H(k),来表达全部的,X(k),值还必须考虑后半部分项数（k+N/2）。,利用系数周期性，,因为,所以,X(k),是,N,点序列，式,4.1,计算得到的只是前一半项数的结果,k=0, 1, , N/2-1 (4.2),将式4.1 中的k用k+N/2代入，可得到,2点的DFT流程图,a,b,-1,a - bW,N,k,a + bW,N,k,W,N,k,这样就把一个,N,点的,DFT,分解成了两个,N/2,点的,DFT,，只是最后求和的符号不同。,式,4.1,与,4.2,的运算可用,蝶形信号流图,来表示,图1,N点的DFT分解成两个N/2点DFT的的时间抽选流程图,N=8,按照式,4.1,和式,4.2,可画出下图所示的信号流程图,。,N/2点,DFT,N/2点,DFT,x(0),x(2),x(4),x(6),x(1),x(3),x(5),x(7),G(1),G(2),G(3),H(1),H(2),H(9),X(1)=G(1)+W,N,1,H(1),X(2)=G(2)+W,N,2,H(2),X(3)=G(3)+W,N,3,H(3),W,N,1,W,N,2,W,N,3,-1,-1,-1,X(5)=G(1) -W,N,1,H(1),X(6)=G(2) -W,N,2,H(2),X(7)=G(3) -W,N,3,H(3),G(0),H(0),W,N,0,-1,X(0)=G(0)+W,N,0,H(0),X(4)=G(0) -W,N,0,H(0),式,4.1,和式,4.2,把原N点DFT计算分解成两个N/2点DFT计算。,照此可进一步把每个,N/2,点,DFT,的计算再各分解成两个,N/4,点,DFT,的计算。,具体说来，是把,x(0),，,x(2),，,x(4),，,x(6),和,x(1),，,x(3),，,x(5),，,x(7),分为,x(0),，,x(4) | x(2),，,x(6),和,x(1),，,x(5) | x(3),，,x(7),。,G(k,),和,H(k,),分别计算如下,:,k=0, 1, , N/4-1 (4.3),k=0, 1, , N/4-1 (4.4),k=0, 1, , N/4-1 (4.5),k=0, 1, , N/4-1 (4.6),M(0),M(1),N(0),N(1),G(0),G(1),G(2),G(3),W,N,0,W,N,2,-1,-1,N/4点,DFT,x(0),x(4),x(2),x(6),N/4点,DFT,图2,N/2点的DFT分解成两个N/4点DFT的的时间抽选流程图,N=8,这样 ，用式,(4.3)(4.6),就可计算图1中的两组N/2点DFT。,图2所示的是其中一组G(k)的计算。,x(0),x(4),x(2),x(6),W,N,0,W,N,2,-1,-1,N/4点,DFT,N/4点,DFT,x(1),x(5),x(3),x(7),N/4点,DFT,N/4点,DFT,W,N,0,W,N,2,-1,-1,将图1与图2合并，便得到,图3,所示的信号流程图。,X(0),X(1),X(2),X(3),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,X(4),X(5),X(6),X(7),G(0),G(1),G(2),G(3),H(0),H(1),H(2),H(3),将2点DFT的信号流程图移入,图3,，得到图4所示的8点时间抽选的完整的FFT流程图。,2点的DFT流程图,x(0),-1,x(0) + x(4)W,N,0,W,N,0,x(4),x(0) - x(4)W,N,0,N=8,，,图3,中N/4点的DFT就是2点的DFT。,图4,基2时间抽选法8点FFT流程图,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,W,N,0,W,N,2,-1,-1,W,N,0,W,N,2,-1,-1,x(1),x(5),x(3),x(7),x(0),x(4),x(2),x(6),W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,a,b,-1,a - bW,N,k,a + bW,N,k,W,N,k,从图4中可看出几个特点：,(1),流程图的每一级的基本计算单元都是一个蝶形；,(2),输入x(n)不按自然顺序排列，称为“,混序,”排列，而输出 X(k)按自然顺序排列，称为“,正序,”排列，因而要对输入进行“变址”；,(3),由于流程图的基本运算单元为蝶形，所以可以进行“,同址,”或“,原位”,计算。,M=log2N,由图可看出完成,一个蝶形计算,需,一次复数乘法,和,两次复数加法,二、,运算量的减少,（蝶形计算）,任何一个,N,为,2,的整数幂（即,N=2,M,）的,DFT,，都可以通过,M,次分解，最后成为,2,点的,DFT,来计算。,M,次分解构成了从,x(n,),到,X(k,),的,M,级迭代计算，每级由,N/2,个蝶形组成。,a,b,-1,a - bW,N,k,a + bW,N,k,W,N,k,下图表示了蝶形的一般形式表示。其输入和输出之间满足下列关系：,大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。,直接计算DFT需要的乘法次数为,a,D,=N,2,，于是有,即直接计算DFT所需复数乘法次数约为FFT的205倍。,显然，N越大，FFT的速度优势越大。,复数乘法次数：,例：当N=1024时，,因此，完成N点的时间抽选FFT计算的总运算量为,复数加法次数：,N,所需复数乘法次数,a,D,/,a,F,直接计算DFT,用FFT计算DFT,2,4,8,16,32,64,128,256,512,1024,2048,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,1,4,12,32,80,192,448,1024,2304,5120,11264,4.0,4.0,5.4,8.0,12.8,21.4,36.6,64.0,113.8,204.8,372.4,不同N值所对应的两种计算方法的复数乘法次数和它们的比值,a,b,-1,a - bW,N,k,a + bW,N,k,W,N,k,三、,同址(原位)计算,图4,包含M级迭代运算，每级由N/2个蝶形计算构成。蝶形计算的优点是可进行所谓,同址(原位)计算,。,首先每一个蝶形运算都需要两个输入数据，计算结果也是两个数据，与其它结点的数据无关，其它蝶形运算也与这两结点的数据无关。,因此，一个蝶形运算一旦计算完毕，原输入数据便失效了。这就意味着输出数据可以立即使用原输入数据结点所占用的内存。原来的数据也就消失了。这样,输出、输入数据利用同一内存单元的这种蝶形计算称为同址计算,。,-1,W,N,0,x(0),x(4),x(0) + x(4)W,N,0,x(0) - x(4)W,N,0,M(0),M(1),M(0),M(1),类似地，,M(2),和,M(3),中的,x(2),和,x(6),进入运算器进行蝶形运算后的结果也被送回到,M(2),和,M(3),保存，等等。,现在来考察第一级的计算规律,设将输入,x(0),，,x(4),，,x(2),，,x(6),，,x(1),，,x(5),，,x(3),，,x(7),分别存入计算机的存储单元,M(0), M(1), M(2), ,，,M(6),和,M(7),中。,首先，存储单元,M(0),和,M(1),中的数据,x(0),和,x(4),进入运算器并进行蝶形运算，运算后的结果便可送到,M(0),和,M(1),存储起来。,第二级运算与第一级类似,M(0),和,M(2),存储单元中的数 据进行蝶形运算后的结果被送回,M(0),和,M(2),保存，,M(1),和,M(3),中的数据进行蝶形运算后送回,M(1),和,M(3),保存，等等。这样一直到最后一级的最后一个蝶形运算完成。,可以看出， 每一级的蝶形的,输入与输出,在运算前后可以,存储在同一地址,(,原来位置上,),的存储单元中,，这种同址运算的优点是可以,节省存储单元,，从而,降低,对计算机,存储量,的,要求,或,降低硬件,实现的,成本,。,M(0),M(1),M(2),M(3),M(4),M(5),M(6),M(7),M(0),M(1),M(2),M(3),M(4),M(5),M(6),M(7),M(0),M(1),M(2),M(3),M(4),M(5),M(6),M(7),M(0),M(1),M(2),M(3),M(4),M(5),M(6),M(7),如图所示的N点FFT计算，只需N个存储存储单元,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),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,2,W,N,2,-1,-1,四、,变址计算 （倒序重排）,从,图,4,所示的流程图看出，同址计算要求输入,x(n,),是“混序”排列的。,所谓输入为“混序”，并不是说输入是杂乱无章的，实际上它是有规律的。,如果输入,x(n,),的序号用二进制码来表示，就可以发现输入的顺序恰好是正序输入的“,码位倒置,”。,下,表,2,列出了这种规律。,自然序列,二进制表示,码位倒置,混序,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),x(000),x(001),x(010),x(011),x(100),x(101),x(110),x(111),表2,x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7),x(000),x(100),x(010),x(110),x(001),x(101),x(011),x(111),存储单元 M(0) M(1) M(2) M(3) M(4) M(5) M(6) M(7),自然顺序 x(n) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7),码位倒置顺序 x(l) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7),变址,图5,码位倒置的变址处理,在实际运算中,，按码位倒置顺序输入数据x(n)，特别当,N,较大时，是很不方便的。,因此，数据总是按自然顺序输入存储，然后通过“变址”运算将,自然顺序,转换成,码位倒置顺序,存储。,实现这种转换的程序可用,图,5,来说明。,图中用,n,表示自然顺序的标号，用,l,表示码位倒置的标号,当,l,n,时，,x(n,),和,x(l,),不必互相调换。,当,ln,时， 必须将,x(l,),和,x(n,),互相调换，但只能调换一次，为此必须规定每当,ln,时，要将,x(l,),和,x(n,),相互调换，即把原来存放,x(n,),的存储单元中的数据调入存储,x(l,),的存储单元中，而把原来存储,x(l,),的存储单元中的数据调入到存储,x(n,),的存储单元中。,这样，按自然序输入的数据,x(n,),经过变址计算后变成了码位倒置的排列顺序，便可进入第一级的蝶形运算。,另外一些形式的,时间抽选FFT算法流程图,对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到,DFT,的正确结果，只是数据的提取和存储次序不同而已。,把,图4,中与,x(4)水平相邻的所有节点和与x(1)水平相邻的所有节点交换,，把与,x(6)水平相邻的所有节点和与 x(3)水平相邻的所有节点交换,，而与x(0)、x(2)、x(5)和x(7)水平相邻各节点位置不变，就可以从图4得到,图6,。,图6,与,图4,的区别只是,节点的排列不同,，而支路传输比，即W,N,的各次幂保持不变。显然图6所示流程图的输入是正序（自然顺序）排列的，输出是码位倒置排列的，所以,输出要进行变址计算,。,图4,基2时间抽选法8点FFT流程图,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,W,N,0,W,N,2,-1,-1,x(1),x(5),x(3),x(7),W,N,0,W,N,2,-1,-1,x(0),x(4),x(2),x(6),W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,图6,基2时间抽选法8点FFT流程图（输入正序）,X(0),X(4),X(2),X(6),X(1),X(5),X(3),X(7),W,N,0,W,N,0,W,N,0,W,N,0,-1,-1,-1,-1,W,N,0,W,N,0,-1,-1,x(4),x(5),x(6),x(7),W,N,2,W,N,2,-1,-1,x(0),x(1),x(2),x(3),W,N,0,-1,W,N,1,-1,W,N,2,-1,W,N,3,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),W,N,0,W,N,0,W,N,0,W,N,0,-1,-1,-1,-1,W,N,0,W,N,0,x(4),x(5),x(6),x(7),W,N,2,W,N,2,x(0),x(1),x(2),x(3),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,-1,-1,-1,-1,另一种形式的流程图是将节点排列成,输入和输出,两者都是,正序排列,，但这类流程图不能进行同址计算，因而需要两列长度为N的复数存储器。,其中 r=0, 1, , N/2-1,4.2 基2频率抽选法（桑德图基算法）,基2频率抽选法是在频域内将,X(k),逐次分解成奇偶序列，再进行DFT计算,设N2,M,，M为正整数。为推导方便，取N=2,3,8。,将频率偶奇分，,即X(k)=X(0), X(2), X(4), X(6), | X(1), X(3), X(5), X(7),用X(2r)和X(2r+1)分别表示频率的,偶数项,和,奇数项,，,则有,其中 g(n)=x(n) + x(n+N/2) n=0, 1, , N/2-1,同理,其中 h(n)=x(n) - x(n+N/2) n=0, 1, , N/2-1,(4.7),(4.8),上面两式所表示的是N/2的DFT。,在实际计算中，首先形成序列g(n)和h(n)，然后计算h(n)W,N,n,，最后分别计算g(n)和h(n)W,N,n,的N/2点DFT，便得到偶数输出点和奇数输出点的DFT。计算流程图如,图7,所示。,N/2点,DFT,N/2点,DFT,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),X(0),X(2),X(4),X(6),X(1),X(3),X(5),X(7),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,图7,N点的DFT分解成两个N/2点DFT的的频率抽选流程图,N=8,a,b,-1,a - bW,N,k,a + bW,N,k,W,N,k,a,a + b,b,-1,(a b)W,N,k,W,N,k,时间抽选,蝶形单元,频率抽选,蝶形单元,与时间抽选的FFT算法一样,，,图7,所示的流程图的基本运算也是,蝶形运算,，但是频率抽选与时间抽选中的蝶形单元,有所不同,。,N是2的整数幂，所以N/2仍然是偶数。这样可以将N/2点DFT的输出再分为偶数组和奇数组，即将N/2点的DFT计算进一步分解为两个N/4点的DFT计算，以此类推直到不能分解。如,图8,图8,基2频率抽选法,8,点FFT流程图,X(0),X(4),X(2),X(6),W,N,0,W,N,1,W,N,2,W,N,3,-1,-1,-1,-1,W,N,0,W,N,2,-1,-1,x(4),x(5),x(6),x(7),W,N,0,W,N,2,-1,-1,x(0),x(1),x(2),x(3),W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,X(1),X(5),X(3),X(7),频率抽选与时间抽选的异同点：,比较图,4,与图,8,可知，,频率抽选,FFT,算法,的计算量与,时间抽选,FFT,算法,的计算量相同。,与时间抽选算法一样，频率抽选,FFT,算法也具有,同址（原位）计算,的优点。,但是，与时间抽选不同的是，频率抽选,FFT,算法的信号输入为正序排列，输出为码位倒置排列，因此输出要进行变址计算。,k=0, 1, , N/2-1,在时间抽选FFT法中，第一次分解得到,G(k)、H(k)分别为输入序列偶数点和奇数点的N/2点DFT,(4.1),(4.2),4.3 IFFT的计算方法（快速傅里叶反变换）,一、IFFT算法,k=0, 1, , N/2-1,根据上式可画出蝶形图,G(k),X(k),H(k),-1,X(k+N/2),以此类推可求出x(n)的各点，反变换流程如,图9,根据式4.1与4.2可得到,图9,8点IFFT流程图,1/2,1/2,1/2,1/2,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),-1,-1,-1,-1,-1,-1,x(1),x(5),x(3),x(7),-1,-1,x(0),x(4),x(2),x(6),-1,-1,-1,-1,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,比较上面两式，可以看出，只要把,DFT,公式中的系数,W,N,kn,改为,W,N,-kn,，并乘以系数,1/N,，将,X(k),作为输入序列，将,x(n),作为输出序列，就可用FFT算法来计算IDFT，这就得到了IFFT的算法。（例,图10,）,在IFFT计算中经常把常量1/N分解成M个1/2连乘，,即1/N (1/2),M,，并且在M级的迭代运算中，每级的运算都分别乘 上一个1/2因子。,二、利用FFT求IFFT,FFT算法同样可以应用于IDFT的计算。,已知DFT和IDFT公式为,x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7),X(0),X(1),X(2),X(3),W,N,0,W,N,-1,W,N,-2,W,N,-3,-1,-1,-1,-1,W,N,0,W,N,-2,-1,-1,X(4),X(5),X(6),X(7),W,N,0,W,N,-2,-1,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,W,N,0,-1,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2,图10,8点IFFT流程图,（例：利用频率抽取FFT ,图8,）,IFFT算法分类,当把,时间抽选,FFT,算法,用于,IFFT,计算时，由于原来输入的时间序列,x(n,),现在变为频率序列,X(k,),，原来是将,x(n,),偶奇分的，而现在变成对,X(k,),进行偶奇分了，因此这种算法改称为,频率抽选,IFFT,算法,。,类似地，当把,频率抽选,FFT,算法,用于计算,IFFT,时，应该称为,时间抽选,IFFT,算法,。（图,10,为时间抽选,8,点,IFFT,算法）,与DFT比较，只需将X,*,(k)作为输入序列就可直接利用FFT流程,具体步骤如下：,1,、,求,X(k),的共轭,X,*,(k),，,取共轭只需将虚部乘以,(-1),2,、,以,X,*,(k),作为输入序列，直接调用,FFT,程序，计算得到,Nx,*,(n),3,、,对计算结果取共轭并乘以,1/N,即得到,x(n),取共轭法,：对DFT的反变换取共轭,4.4 基4FFT算法（略）,基4FFT与基2FFT相比，复数乘法减少了约1/4，但复数加法却增加了。,无论是软件还是硬件方法，复数乘法计算时间是复数加法的几十倍乃至上百倍，所以基4算法产生的主要目的是为了减少复数乘法。,近年来，在一些高速数字信号处理器中，实现一次乘法运算与一次加法运算的时间完全一样，所以应用基4算法时就不一定合算了。,4.5 线性调频Z变换算法（CZT）,在某些情况下，我们所需要的频率取样点并不均匀的分布在单位圆上；,有时只在单位圆的某一部分；,有时要求某一部分取样点密集（例如窄带信号）；,有时甚至取样点不在单位圆上。 （例如语音信号处理）,沿Z平面上的一段螺线作等分角抽样,Z,k,=,AW,-k,k,=,0,1,M-1,且,M,N,式中,如图：,一、算法基本原理,已知x(n)长度为N，则,W,0,、A,0,为正实数,Im(,z),z平面,Re(,z),1,A,0,0,0,Z,0,Z,M-1,0,Im(,z),z平面,Re(,z),1,A,0,0,0,Z,0,Z,M-1,0,由图可知：,1、,A,0,表示起始抽样点Z,0,的矢量半径长度，通常A,0, 1，否则Z,0,将在单位圆之外；,2、,q,0,表示起始抽样点Z,0,相角，可正可负;,3、,f,0,表示两相邻抽样点间角度差，,f,0,为正时，表示路径逆时针，,f,0,为负时表示路径顺时针。,4、,W,0,表示螺线的伸展率，W,0,1表示随k增大螺线内缩，W,0,1表示随k增大螺线外伸。W,0,=1表示半径为A,0,的一段圆弧，又如果A,0,=1,则圆弧是单位圆一部分。,与直接计算DFT相似，当N、M很大时，运算量很大；,于是可采用,布鲁斯坦（Bluestein）,等式，将其转换为卷积和形式，从而可采用FFT算法。,Bluestein等式,令,可得：,0kM-1,将Z,k,代入X(z)，有,0kM-1,计算过程如图：,x(n),h(n),y(n),g(n),令,则,或,可想象为频率随时间n成线性增长的复指数序列，在雷达系统中，这种信号称为,线性调频信号,(Chirp signal)，因此在这里称为,线性调频Z变换算法,。,序列,0kM-1,0kM-1,0kM-1,0kM-1,由,可知h(n)的长度为n=-(N-1)M-1 点数为L=N+M-1，y(n)的长度为N，要利用L点循环卷积来计算，y(n)需补M-1个零。,二、实现步骤,考虑h(n)的长度 ：无限长,然后计算,h(n)与y(n)的L点循环卷积,其中g(0)到g(M-1)这M个值正与所需要的线性卷积值相等，后N-1个值不需要。,当,L=M+N-1=2,m,时，可利用基2FFT算法。,n,0,h(n),M-1,-(N-1),n,0,h(n),M-1,L-1,而h(n)选取值如图：,n,0,h(n),M-1,L-1,2、将,3、形成L点h(n)，并利用FFT法求H(k),0nM-1,MnL-N,L-N+1nL-1,CZT运算步骤：,1、选择L值使LM+N-1，且L=2,m,补零，变为L点序列。并利用FFT法求Y(k),（其中前M个值有用）,0nM-1,三、运算量估计（略）,4、将H(k)与Y(k)相乘得到G(k),5、用FFT法求G(k)的L点IDFT,6、最后求,1,、CZT算法灵活，输入序列点数N与输出序列点数M可不等；,2,、N与M为任意数，不需要为2的整数幂；,3,、Z,k,点间的角度分隔,0,可任意，因此可调整分辨率；,4,、Z,k,点所沿周线不必须是弧线；,5,、起始点Z,0,任意选点，即可以从任意频率上开始对输入数据进行频谱分析；,6,、当,A1,、,MN,、,W= e,-j2,p,/N,时，即为DFT，因此利用CZT也可快速计算DFT，且不要求N为2的整数幂。,四、CZT与FFT比较,4.6 实序列的FFT高效算法,在实际中，所需处理的实序列居多，实序列是虚部为0的复序列。,一、两个长度相等的实序列,两个长度相等的实序列，FFT可同时进行。因为DFT所变换的序列一般是复序列，故可将两个实序列组合成一个复序列来进行FFT计算，从而完成这两个FFT计算，节约了计算量。,设,h(n),与,g(n),是长度均为N的实序列，,组合 y(n)=h(n)+jg(n),且DFTy(n)=Y(k) DFTh(n)=H(k) DFTg(n)=G(k),则有Y(k)=H(k)+jG(k),h(n)=Rey(n),H(k)=DFTRey(n)Y,ep,(k)=1/2Y(k)+Y*(N-k),g(n)=Imy(n),G(k)=DFTImy(n)Y,op,(k)=1/2jY(k)-Y*(N-k),因此，做一次N点复序列FFT计算，可得到两个实序列DFT。,将一个2N点的实序列x(n)按奇偶分为两组,h(n)=x(2n),与,g(n)= x(2n+1),n=0,1,N-1,则有,h(n)与g(n)按两个长度相等的实序列计算（如上）,k=0,1,N-1,二、一个2N点的实序列,