信息与通信FFT原理.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,快速傅里叶变换（,FFT,）,快速傅里叶变换（,FFT,）是计算,DFT,的一种快速高效的算法。,有限长序列在数字技术中占有很重要的地位，主要原因是由于其频谱可以离散化。有限长序列的,DFT,本身可以完全表达序列的频谱，所以,DFT,也可以直接对信号进行频谱分析。,谱分析在通信技术、图象传输、语音压缩、生物医学等领域都得到应用。,虽然频谱分析和,DFT,运算很重要，但在很长一段时间里，由于,DFT,运算量太大，因此它并没有得到真正的运用，频谱分析也大多采用模拟信号滤波的方法解决。直到,1965,年美国,IBM,公司的库利和图基这两位科学家首次提出,DFT,运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到,DFT,运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法,快速付里叶变换,(FFT),算法。,FFT,的出现，使,DFT,的运算大大简化，运算时间缩短,1-2,个数量级，,FFT,的问世使得,DFT,在实际中得到广泛应用。,6.1 DFT,运算的特点：,有限长序列,x(n),进行一次,DFT,运算所需的运算量,:,一,.DFT,的运算量：,一般,x(n),和 都是复数，,X(k),也是复数，所以计算一次,DFT,的运算量是：,在这些运算中，乘法比加法运算复杂，尤其是复数相,乘，每个复数相乘包括,4,个实数相乘和,2,个实数相加，例：,又因每个复数相加包括,2,个实数相加,所以,每计算一个,X(k),要进行,4N,次实数相乘和,2N+2(N-1)=2(2N-1),次实数相,加，因此，整个,DFT,运算需要,4N,2,实数相乘和,2N(2N-1),次实,数相加。,计算一个,X(k),值需：,N,次复数相乘和,(N-1),次复数相加,计算,N,点,X(k),值需：次复数相乘和,N(N-1),次复数相加,从上面的分析看到，在,DFT,计算中，不论是乘法和加法，运算量均与,N,2,成正比。因此，,N,较大时，运算量十分可观。例：计算,N=10,点的,DFT,，需要,100,次复数相乘，而,N=1024,点时，需要,1048576,（一百多万）次复数乘法，如果要求实时处理，则要求有很高的计算速度才能完成上述计算量。反变换,IDFT,与,DFT,的运算结构相同，只是多乘一个常数,1/N,，所以二者的计算量相同。,考察,DFT,的运算特点发现,利用以下两个特性可减少运算量：,1,）系数 是一个周期函数，利用它的周,期性和对称性可改进运算，提高计算效率。,二,.DFT,的运算特点,周期性,对称性,我们利用系数 的周期性和对称性，考察它,是如何简化,DFT,运算的过程。,以,N,4,为例，的矩阵形式为：,DFT,的矩阵运算,2),因为,DFT,的计算量,正比于,N,2,，,N,小计算量也就小。,因此可以把长度为,N,点的大点数的,DFT,运算依次,分解为若干个小点数的,DFT,来运算。,FFT,算法正是基于以上两点基本思想来提高,DFT,的,运算速度。,FFT,算法基本上可分为两大类：,按时间抽取,FFT,算法,和,按频率抽取,FFT,算法,。,结论：,1),利用系数 的,周期性,和,对称性,可以提高,DFT,的,运算速度。上例中作一次,DFT,需,N,2,=,16,次,乘法运,算，而,FFT,只需,6,次,乘法运算。,6.2,按时间抽取的,FFT,为了保证,N,点,DFT,的运算分解，首先假设,N,是,2,的整幂次方，,即,N=2,M,，,M,是正整数。,一,.,算法原理,(1),将序列 按序号,n,的奇、偶分解为两个 点子序列,DFT,运算也相应分为两组：,故,：,显然，和 都只含有,N/2,点,DFT,所以,X(k),也只包含,k=0,1,N/2-1,点的,DFT,，还必须利用系数,的周期性和对称性，求出,X(k),的后,N/2,点的,DFT,。,(2),求：,可见，一个,N,点的,DFT,被分解为前后,两个,N/2,点的,DFT,，,这,两个,N/2,点的,DFT,再合成为,一个,N,点,DFT,。,同理：,再利用,W,系数的对称性：,以上两个表达式说明：只要我们计算出,N/2,个点,的所有 和 的值，就等于求出,N,点的,X(k),值,这使得,DFT,的运算量减少了约一半。,上述两个公式的运算过程可用专用蝶形图表示：,图,(a),需要两次乘法、两次加减法,将图,(a),简化成图,(b),，此时仅需一次乘法、两次加减法。,按时间抽取的蝶形运算流图：,(3),和 可以继续分解下去，可将,N/2,点的 子序列再按奇、偶项分解，一直到最后分解成 两两点的,DFT,为止。,偶序列中的偶序列,偶序列中的奇序列,奇序列中的偶序列,奇序列中的奇序列,四个 点,DFT,例：,N=2,3,=8,按时间抽取的,DFT,分解过程,由于,N/2,仍是偶数，可以被整除，因此可以对两个,N/2,点的,DFT,再分别作进一步的分解。将一个点的,DFT,可以分解成四个点的,DFT,直到,最后得到两两,点的,DFT,为止。,由于这种方法每一步分解都是按输入序列是属于偶数还是奇数来抽取的，所以称为,“,按时间抽取的,FFT,算法,”,。,N,8,点按时间抽取的,FFT,运算流图,第一级蝶形,第二级蝶形,第三级蝶形,时间抽取法,FFT,的运算特点：,（,1,）蝶形运算,（,2,）原位运算结构,（,3,）码位倒置变换,（,4,）蝶形类型随迭代次数成倍增加,（,1,）蝶形运算,对于,N=2,M,，总可以通过,M,次分解最后分解成,2,点的,DFT,运算。这构成从,x,(n),到,X(k),的,M,级运算过程。从上面流图可看到，每一级运算都由,N/2,个蝶形运算构成。因此每一级运算都需要,N/2,次复乘和,N,次复加，经过,M,级运算后总共需要的运算量为：,复乘：复加：,而直接进行,DFT,运算时则与,N,2,成正比,。,算法的运算速度,例,:N=2048,，,N,2,=4194304,，,显然,FFT,要比直接,DFT,运算快得多,。,（,2,）原位运算结构（,同址运算,）,FFT,运算结构很有规律，它具有强烈的对称性，它的所有运算都可以由左下图所示的基本运算构成。,由于运算结构规律，所以硬件实现起来简单，软件编程方便。,FFT,的蝶形运算结构很经济，它可以采用原位运算。,原位运算,指当数据输入到存储器中以后，,每一级运算的结果仍然储存在同,一组存储器中，直到最后输出，,中间无需其它任何存储器，称为,原位运算。,例如：输入数据,A,、,B,相应的存放在寄存器,A(1),和,A(2),中，当进行完蝶形运算后，输出和存放在,A(1),中，输出差存放在,A(2),中。下一级蝶形运算的输入数据又分别存放在,A(1),和,A(2),中，而把前一级输出的结果覆盖掉，直到最后输出，中间无需任何其它存储器。原位运算结构节省存储单元，可以降低设备成本，,还可节省寻址的时间。,（,3,）,码位倒置变换,对按时间抽取,FFT,的原位运算结构，如果输出按顺序输出,即顺序存放,x(0),x(1),x(2),x(7),但它的输入,x(n),却不是按自然顺序输入的,而是按,x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7),存入,，这种顺序看起来很杂乱，实际上它很有规律。当用二进制表示这个顺序时，它正好是,“,码位倒置,”,的顺序。,例如：顺序输出,码位倒置,指序号用,二进制码形式表示，然后将,二进制码的首尾颠倒。,输入,在实际运算中，输入数据总是按自然顺序输入到存储单元，再通过变址运算将自然顺序转换成码位倒置顺序存储，然后再进行,FFT,的原位计算。目前有许多通用,DSP,芯片支持这种码位倒置的寻址功能。,下表中以,N=8,为例给,出码位倒置顺序,I,J,码位倒置的规律,(1),当,I=J,时，,A(I),中存储的数不变，,A(I)=A(J);,(2),当,IJ,时，意味着,A(I),和,A(J),的内容已经互换,过了，为了避免将已互换过的数据再次调换，,所以,A(I),和,A(J),的内容不变。,N,8,点按时间抽取的,FFT,运算流图,第一级蝶形,第二级蝶形,第三级蝶形,观察,N=,2,3,=8,点,FFT,的蝶形系数 ：,第一级：有一种类型的蝶形运算系数,第二级,:,有二种类型的蝶形运算系数 、,第三级,:,有四种类型的蝶形运算系数,、,第,L,级,:,有,种,蝶形运算系数,（,4,）蝶形图的系数,将,x(n),按,n,的顺,序前后对半分开：,6.3,按频率抽取的,FFT,频率抽取法是,N=2,M,情况下的另外一种,FFT,算法,按时间抽取,FFT,算法的基本思路,按频率抽取,FFT,算法的基本思路,x(n),按奇、偶一级级分开，,X(k),按前一半、后一半一级级分开。,X(k),按奇、偶一级级分开，,x(n),按前后对半一次次分开。,一,.,按频率抽取法的,FFT,算法原理,按,k,的奇、偶把,X(k),进一步分解为两部分：,a),k,为偶数，令,k=2r,b),k,为奇数，令,k=2r+1,按频率抽取的蝶形运算流图：,例：以,N=8,按频率抽取的,FFT,把,8,点,DFT,分解成两个,4,点的,DFT,K,为偶数,X(2r),K,为奇数,X(2r,1),将两个,4,点,DFT,再分解成四个,2,点,DFT,由于,N/2,仍是偶数可以继续分解，直到分解为两两点的,DFT,为止。,下图是,N=8,按频率抽取的,FFT,流图,频率抽取法的分解过程：,(1),把输入序列前后对半分；,(2),输出按,k,值的奇、偶将,X(k),分解为奇数组和偶数组两部分；,(3),输入如果按顺序输入，输出则是码位倒置形式。,按频率抽取法,FFT,的运算特点：,（,1,）蝶形运算的运算量,其运算量与按时间抽取运算量相同。即：,复乘：复加：,（,2,）输入如果是自然顺序，输出则是码位倒置形式。如果要求输出为自然顺序，则需要进行变址运算。按频率抽取的,FFT,流图可以由按时域抽取的,FFT,流图转置 而得到。转置指将流图中所有支路的方向反,并将输入变输出，输出变输入。,频率抽取法的基本蝶形图与时间抽取法的基本蝶形图有所不同。时间抽取法是先乘后加、减，频率抽取法是先加、减，再乘系数,按频率抽取的,蝶形运算流图,按时间抽取的,蝶形运算流图,按时间抽取的,FFT,算法以及按频率抽取的,FFT,算法是,DFT,的两种快速算法，这些算法同样可以用於,IDFT,，我们称为快速傅立叶反变换,(IFFT),。我们把,IDFT,公式与,DFT,公式作以比较：,(1)DFT,中的系数,(2)IDFT,中要乘以常数,6.4 IDFT,的快速算法,IFFT,另外一种,IFFT,算法的实现,以上讨论的时间抽取或频率抽取的,FFT,运算均可直接用于,IFFT,运算。但需要将蝶形系数 改为 ，每级乘以系数,1/2,。,IFFT,计算分为三步：,将,X(k),取共轭,(,虚部乘以,-1);,对 直接作,FFT,；,对,FFT,的结果取共轭并乘以,1/N,，就得到,x,(n),。,按上述方法求得的,IFFT,，完全不需要改动,FFT,程序，,FFT,和,IFFT,可以共用一个程序。,总结,FFT,和,IFFT,蝶形图的表示方法：,按时间抽取的,FFT,变到,IFFT,时，对应的流图应该是按频率抽取的,IFFT,。因为：,按时间抽取的,FFT,输入变量是,x(n),x(n),按奇、偶分解,按频率抽取的,IFFT,输入变量是,X(k),X(k),按奇、偶分解,同理，按频率抽取的,FFT,变到,IFFT,时，对应的流图应该是按时间抽取的,IFFT,。,（,1,）输入按奇、偶分解：,（,2,）输入按前、后分解：,6,.5,任意基数的,FFT,算法,前面讨论的,FFT,算法，序列的长度均满足,N=2,M,，这种情况实际使用得最多，因为它程序简单，效率,高，使用方便。如果不满足,N=2,M,处理方法有两种,:,补零,:,将,x(n),补零,使,N,增加到临近的一个值，,满足,N=2,M,。,例如：,N=30,补上,x,(30),=,x,(31),=0,两个零点,使,得满足,N=2,5,=32,这样可直接调用以,2,为基数的,FFT,运算。有限长序列补零后并不影响其频谱 ，,补零只是频谱的采样点数增加了。,如 ，如果要求,N,点,DFT,值,几乎要补一半,0,值,(2044,个,0),，显然用第一种方法处理很不经济，因此，如果要求求准确的,N,点,DFT,值,可采用任意基数的,FFT,算法,但其运算效率低于以,2,为基数的,FFT,算法。,任意基数的,FFT,算法的基本思想,首先要求,N,可以分解成因子乘积的形式，,N,不能是素数。任意基数的,FFT,算法的基本思想仍是把一个大,N,点的,FFT,尽量分解为小点数的,FFT,。,首先将,N,分解为两个整数,p,与,q,的乘积,即：,，其步骤为：,(1),将序列,x,(n),分成,p,组,p,组,r=0,1,q-1,(2),将,N,点,DFT,分成,p,组,q,点的,DFT,来运算,例,：,N,6,p,3 q,2,P,组,6,.6,Chirp-z,变换,（简称,CZT),采用,FFT,可以算出全部,N,点,DFT,值，而,DFT,值是,Z,变换,X(z),在,Z,平面单位圆上的等间隔取样值，但有些情况下不需要求出全部的,DFT,值。例如：,对于窄带信号，只需要对信号所在的一段频带进,行谱分析，这时,希望频谱的采样集中在这一段频,带内，以获得较高的分辨率，而频带以外部分可,不考虑。,语音信号处理中，需要知道,Z,变换的极点所在的复频率位置，即共振峰的位置。如果极点位置离单位圆较远，则其单位圆上的频谱会很平滑，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在的频率上将出现明显的尖峰，这些尖峰就是共振峰，它可较准确地测定极点对应的频率。,当,N,是素数时，不能采用任意基数的,FFT,算法。,鉴于以上三种情况，我们提出一种最有效的变换,螺线采样，或称为,Chirp-z,变换。螺线采样是,FFT,的另外一种快速算法，它是沿着一条螺旋线的采样。,一,.,算法原理：,首先对,Z,平面单位圆内的一段螺线作,M,等分采样。令采样点,z,k,=AW,-k,，,k=0,M-1,，,M,为采样点数，,A,0,表示起始取样点的,半径长度，通常,A,0,1,0,表示起始取样点的相角,0,表示两相邻点之间的等分角,A,、,W,为任意复数，其中：,W,0,表示螺旋线的伸展率，则随,K,的增大螺线外伸，则螺线内缩,(,反时针,),，,W,0,=1,表示半径为,A,0,的一段圆弧,若,A,0,=1,表示这段圆弧是单位圆的一部分。把,代入,z,k,=AW,-k,，计算,Z,变换在采样点,z,k,的值：,为了能够利用,FFT,运算，想办法把,Z,变换转换为线性卷积形式运算，从而可采用,FFT,进行，这样可大大提高计算速度。,Z,变换在采样点,z,k,上的值为：,z,k,=AW,-k,令：,则,上式说明，如对信号,x(n),先进行一次加权处理，加权系数为 ，然后通过一个单位脉冲响应为,h(n),的线性系统，最后对该系统的前,M,点输出再作一次 加权，就可得到全部,M,点的螺旋线采样值,。,系统的单位脉冲响应,是具有二次相位的复指数信号，,h(n),可以想象为,频率随时间,n,成线性增长的,复指数序列，它和雷达系统中的,线性调频信号相似，因此称为,Chirp-z,变换。,二,.CZT,的算法实现,输入信号 是有限长序列，长度为,N,，,但,是无限长序列,而计算,0,M-1,点卷积中,h(n),取值只需要,n,=,-(N-1),M-1,那一部分的值。因此，可以认为,h(n),是一个有限长序列,其长度为,L=N+M-1,。所以，把,Chirp-z,变换可以看成两个有限长序列的线性卷积。,可利用圆圈卷积通过,FFT,来实现。,h(n),的主值序列 可由,h(n),作周期延拓后取,0nL-1,部分值获得，将 与,g(n),作圆周卷积后，其输出的,前,M,个值,就是,Chirp-z,变换的,M,个值。这个圆周卷积的过程可在频域用,FFT,实现。,Chirp-z,变换的计算步骤：,(1),求,h(n),的主值序列,(2),求 的,L,点的,FFT:H(k)=FFT ,(3),对,x(,n),加权并补零,(4)G(k)=FFTg(n),L,点,(5)Y(k)=G(k)H(k),L,点,(6)y(n)=IFFTY(k),L,点,(7),0kM-1,利用,FFT,计算,Chirp-z,变换,Chirp-z,变换的特点：,1,）输入序列长度,N,与输出序列长度,M,不需要相等；,2,）,N,及,M,不必是高度复合数，二者均可为素数；,3,）相邻采样点,z,k,之间的角间隔,0,是任意的，即频,率分辨率是任意的；,4,）围线是任意的，不必是,Z,平面上的圆；,5,）起始点,z,0,可任意选定，即可从任意频率上开始,对输入数据进行窄带高分辨率分析；,6,）若,A=1,M=N,可用,Chirp-z,变换,计算,DFT,（即使,N,为素数）。,6,.7,线性卷积的,FFT,算法,线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上。,第二章中已讨论过，线性卷积可以用圆周卷积的方法替代，为了不产生混叠，序列长度将,:,长度为,N,2,的序列,x(n),延长到,L,补,L-N,2,个零，,长度为,N,1,的序列,h(n),延长到,L,补,L-N,1,个零，,如果,LN,1,+N,2,-1,则,圆周卷积,与,线性卷积相等,此时,可用,FFT,运算替代线性卷积，方法如下,:,a.,计算,X(k)=FFTx(n),b.,求,H(k)=FFTh(n),c.,求,Y(k)=H(k)X(k)k=0,L-1,d.,求,y(n)=IFFTY(k)n=0,L-1,可见，只要进行二次,FFT,一次,IFFT,就可完成,线性卷积计算。计算表明,L32,时,上述计算线,性卷积的方法比直接计算线卷积有明显的优越性。,因此,也称圆周卷积的方法为,快速卷积法,。,上述方法适用于,x(n),、,h(n),两序列长度比较接近或相等的情况。如果,x(n),、,h(n),长度相差较多,例如：,h(n),为某滤波器的单位脉冲响应,长度有限,用来处理一个很长很长的输入信号,x(n),按上述方法,h(n),要补许多零值后再进行计算,这降低了运算速度，发挥不出圆周卷积的优点。,为了保持快速卷积法的优越性,可将,x(n),分为许多段,每段的长度与,h(n),接近,处理方法有两种：,(1),重叠相加法,(2),重叠保留法,(1),重叠相加法,由分段卷积的各段相加构 成总的卷积输出,h(n),x(n),序列长度为,序列长度为,假定 表示,x(,n),序列的第,i,段：,则输入序列可表为：,于是输出可分解为：,其中,d.,重叠部分相加构成最后的输出序列。,重叠相加法计算步骤：,a.,先对,h(n),及 补零，补到具有,N,点长度，,N=N,1,+N,2,-1,，并且满足,N=2,M,。,b.,用,N,点,FFT,计算,c.,用,N,点,FFT,计算,由于 的长度为,N,，而 的长度为,N,2,，因此相邻两段序列 必然有,N-N,2,=N,1,-1,点发生重叠，最后的输出应该是这些重叠部分相加起来，再和不重叠部分共同组成输出序列 。,重叠相加法对处理一个无限长的语音信号或地震信号都是十分有效的。,有,N,1,-1,个点发生重叠,(2),重叠保留法,这种方法和第一种方法稍有不同，即将上面分段序列中补零的部分不是补零，而是保留原来的输入序列值，如果利用,FFT,实现,h(n),和,x,i,(n),的圆周卷积，则每段卷积结果中有,N,1,-1,个点不等于线性卷积值需舍去。,重叠保留法与重叠相加法的计算量差不多，但省去了重叠相加法最后的相加运算。,h(n),x(n),序列长度为,序列长度为,(1),重叠相加法,(2),重叠保留法,保留 点的输入序列值,FFT,应用中的几个问题,实数序列的,FFT,以上讨论的,FFT,算法都是复数运算,包括序列,x(n),也认为是复数,但大多数场合,信号是实数序列,任何实数都可看成虚部为零的复数。例如,求某实信号,x(n),的复谱,可认为是实信号加上数值为零的虚部组成复信号,(x(n)+j0),再用,FFT,求其离散傅里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,造成运算速度下降。合理的解决方法是利用复数据,FFT,对实数据进行有效计算,下面介绍两种方法。,（,1,）用一个,N,点,FFT,同时计算两个,N,点实序列的,DFT,设,x(n),、,y(n),是彼此独立的两个,N,点实序列,且,X(k)=DFTx(n),，,Y(k)=DFTy(n),则,X(k),、,Y(k),可通过一次,FFT,运算同时获得。,首先将,x(n),、,y(n),分别当作一复序列的实部及,虚部,令：,g(n)=x(n)+jy(n),通过,FFT,运算可获得,g(n),的,DFT,值,利用离散傅里叶变换的共轭对称性,通过,g(n),的,FFT,运算结果,G(k),由上式可得到,X(k),的值。,Y(k),的值也可以通过,g(n),的,FFT,运算结果,G(k),得到。,作一次,点复序列的,FFT,，再通过加、减法运算就可以将,X,(,k,),与,Y,(,k,),分离出来。显然，这将使运算效率提高一倍。,（,2,）用一个,N,点的,FFT,获得一个,2N,点实序列的,DFT,设,x(n),是,2N,点的实序列,现人为地将,x(n),分为偶数组,x,1,(n),和奇数组,x,2,(n),x,1,(n)=x(2n)n=,0,1,N-1,x,2,(n)=x(2n+1)n=,0,1,N-1,然后将,x,1,(n),及,x,2,(n),组成一个复序列：,y(n)=x,1,(n)+jx,2,(n),通过,N,点,FFT,运算可得到：,Y(k)=X,1,(k)+jX,2,(k),为求,2N,点,x,(n),所对应,X(k),，需求出,X(k),与,X,1,(k),、,X,2,(k),的关系：,所以,1,）由,x,1,(n),及,x,2,(n),组成复序列，经,FFT,运算求得,Y(k);,2,）利用共轭对称性求出,X,1,(k),、,X,2,(k);,3,）最后利用上式求出,X(k),达到用一个,N,点的,FFT,计算一个,2N,点的实序列的,DFT,的目的。,X(k)=X,1,(k)+W,2N,k,X,2,(k),