快速傅里叶变换FFT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本章主要内容,引言,基2,FFT,算法,进一步减少运算量的措施,第4章 快速傅里叶变换(,FFT),DFT,是信号分析与处理中的一种重要变换。但,直接计算,DFT,的计算量与变换区间长度,N,的平方成正比,，当,N,较大时，计算量太大，直接用,DFT,算法进行谱分析和信号的实时处理是不切实际的。,1965,年发现了,DFT,的一,种快速算法,，使,DFT,的运算效率提高,12,个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件，推动了数字处理技术的发展。,1984年，提出了,分裂基快速算法,，使运算效率进一步提高；,4.1 引言,4.2.1 直接计算,DFT,的特点及减少运算量的基本途径,直接计算,DFT,长度为,N,的有限长序列,x(n),的,DFT,为：,2、减少运算量的思路和方法,思路：,N,点,DFT,的复乘次数等于,N,2,。,把,N,点,DFT,分解为几个较短的,DFT,，,可使乘法次数大大减少。另外，旋转因子,W,m,N,具有周期性和对称性。,4.2 基2,FFT,算法,考虑,x(n),为复数序列的一般情况，对某一个,k,值，直接按上式计算,X(k),值需要,N,次复数乘法,、,(,N-1),次复数加法,。,方法：,分解,N,为较小值,：把序列分解为几个较短的序列，分别计算其,DFT,值，可使乘法次数大大减少；,利用,旋转因子,W,N,k,的周期性、对称性,进行合并、归类处理，以减少,DFT,的运算次数。,周期性,：,对称性,：,3、,FFT,算法思想,不断地把,长序列,的,DFT,分解成,几个短序列,的,DFT，,并利用旋转因子的,周期性,和,对称性,来减少,DFT,的运算次数。,4.2 基2,FFT,算法,4.2.2 时域抽取法基2,FFT,基本原理,FFT,算法基本上分为两大类：,时域抽取法,FFT(,简称,DIT-FFT),和,频域抽取法,FFT(,简称,DIFFFT),。,1、,时域抽取法,FFT,的,算法思想：,将序列,x(n),按,n,为奇、偶数分为,x,1,(n)、x,2,(n),两组序列；用2个,N/2,点,DFT,来完成一个,N,点,DFT,的计算。,设序列,x(n),的长度为,N，,且满足：,(1)按,n,的奇偶把,x(n),分解为两个,N/2,点的子序列,4.2 基2,FFT,算法,为自然数,(2)用,N/2,点,X,1,(k),和,X,2,(k),表示序列,x(n),的,N,点,DFT X(k),4.2 基2,FFT,算法,偶数,奇数,注意：,这里的,k,的取值范围为0，1，,N-1,由于,X,1,(k),和,X,2,(k),均以,N/2,为周期，且 ,X(k),又可表示为:,对上式的运算用下图所示的,流图符号,来表示,4.2 基2,FFT,算法,这样将,N,点,DFT,分解为两个,N/2,点的,DFT,X,1,(k),X,2,(k),X,1,(k)+,W,N,k,X,2,(k),X,1,(k),W,N,k,X,2,(k),W,N,k,图：蝶形运算符号,完成一个蝶形运算需要一次复数乘和两次复数加法运算，经过一次分解后，共需要复数乘和复数加的次数为,2(,N/2),2,+N/2,和,N,2,/2,4.2 基2,FFT,算法,N/2,点DFT,N/2,点DFT,x(0),x(2),x(4),x(6),x(1),x(3),x(5),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),W,N,0,W,N,1,W,N,2,W,N,3,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),N=8,点的,DIT-2FFT(,时域抽取图)一次分解图,(3)第二次分解：,将,x,1,(r),按,r,取奇、偶可分解成2个长度为,N/4,的子序列,x,3,(l)=x,1,(2l)、,x,4,(l)=x,1,(2l+1)，,根据上面推导可得：,X,1,(k)=X,3,(k)+W,N/2,k,X,4,(k)，,k=0,1,N/2-1,将,x,2,(r),按,r,取奇、偶可分解成2个长,N/4,的子序列,x,5,(l)x,2,(2l)，l=0,1,，N/4,x,6,(l)=x,2,(2l+1)；,同理得,4.2 基2,FFT,算法,l=0,1,，N/4-1；,X,1,(k+N/2)=X,3,(k),W,N/2,k,X,4,(k)，k=0,1,N/4-1；,X,1,(k)=X,3,(k),+,W,N/2,k,X,4,(k)，k=0,1,N/4-1；,X,2,(k)=X,5,(k)+W,N/2,k,X,6,(k)，k=0,1,N/4-1 ；,X,2,(k+N/2)=X,5,(k),W,N/2,k,X,6,(k),k=0,1,N/4-1；,4.2 基2,FFT,算法,N/4点DFT,x(0),x(4),x(2)x(6),x(1),x(5),x(3),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),W,N,0,W,N,1,W,N,2,W,N,3,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),N/4点DFT,N/4点DFT,N/4点DFT,X,3,(0),X,3,(1),X,4,(0),X,4,(1),X,5,(0),X,5,(1),X,6,(0),X,6,(1),W,N/2,0,W,N/2,1,W,N/2,1,W,N/2,0,N=8,点,DFT,的二次时域抽取分解图,X,1,(k+N/2)=X,3,(k),W,N/2,k,X,4,(k),X,1,(k)=X,3,(k),+,W,N/2,k,X,4,(k),X,2,(k)=X,5,(k)+W,N/2,k,X,6,(k),X,2,(k+N/2)=X,5,(k),W,N/2,k,X,6,(k),k=0,1,N/4-1 ；,再次分解，对,N=8,点，可分解三次。,4.2 基2,FFT,算法,X(5),N=8,点,DIT-FFT,运算流图,x(0),x(4),x(2),x(6),x(1),x(5),x(3),X,1,(1),X,1,(2),X,1,(3),X,2,(0),X,2,(1),X,2,(2),X,2,(3),W,N,0,W,N,1,W,N,2,W,N,3,X(0),X(1),X(2),X(3),X(4),X(6),X,3,(1),X,4,(0),X,4,(1),X,5,(0),X,5,(1),X,6,(0),X,6,(1),W,N/2,0,W,N/2,1,W,N/2,0,W,N,0,W,N,0,W,N,0,x(7),W,N/2,1,W,N,0,L=1,级,L=2,L=3,X(7),X,3,(0),X,1,(0),4.2 基2,FFT,算法,N=8,点,DIT-FFT,运算流图,x(0),x(4),x(2),x(6),x(1),x(5),x(3),W,N,0,W,N,1,W,N,2,W,N,3,X(0),X1),X(2),X(3),X(4),X(5),X(6),W,N,0,W,N,2,W,N,0,W,N,0,W,N,0,W,N,0,x(7),W,N,2,W,N,0,L=1,级,L=2,L=3,X(7),4.2.3,DITFFT,算法与直接计算,DFT,运算量的比较,1、直接,DFT,运算,N,点运算,：,复数乘次数：,N,N,复数加次数：,N,(N-1),2、,用,DIT-FFT,作,N,点运算：,复数乘次数：,M,N/2=N/2,log,2,N；,复加次数：,2,N/2M=Nlog,2,N,。,可见,FFT,大大减少了运算次数，提高了运算速度。,4.2 基2,FFT,算法,整个运算流图中有,M,级蝶形,，每一级运算流图中有,N/2,个蝶形,，每个蝶形需,一次复乘和两次复数加,运算。,4.2.4,DITFFT,的运算规律及编程思想,1.原位计算,序列长为,N=2,M,点的,FFT,，,有,M,级蝶形,，每级有,N/2,个蝶形运算,。,同一级中，每个蝶形的两个输入数据只对本蝶形有用,，每个蝶形的输入、输出数据节点在用一条水平线上。这样，当计算完一个蝶形后，所得的输出数据可立即存入原输入数据所占用的存储单元。,经过,M,级运算后，原来存放输入序列数据的,N,个存储单元中可依次存放,X(k),的,N,个值。,原位计算,：,利用同一存储单元存储蝶形计算,输入、输出数据的方法。,优点,：节约存储空间、降低设备成本。,4.2 基2,FFT,算法,2.旋转因子的变化规律,N,点,DITFFT,运算流图中，每个蝶形都要乘,以,旋转因子,W,p,N,，p,称为旋转因子的指数。,N8 2,3,时各级的旋转因子,第一级：,L=1，,有1个旋转因子：,W,N,p,=W,N/4,J,=W,2,L,J,J=0,第二级：,L=2，,有2个旋转因子：,W,N,p,=W,N/2,J,=W,2,L,J,J=0,1,第三级：,L=3，,有4个旋转因子：,W,N,p,=W,N,J,=W,2,L,J,J=0,1,2,3,对于,N2,M,的,一般情况，,第,L,级,共有,2,L-1,个不同的旋转因子：,W,N,pW,2,L,J,J=0,1,2,2,L-1,1,2,L,=2,L,M,2,M,=N,2,L,M,故：,按照上面两式可以确定第,L,级运算的旋转因子。,4.2 基2,FFT,算法,J,J,2,M-L,W,N,p,=W,2,L,J,=W,N,2,L-M,=W,N,p=J2,M-L,，J=0,1,2,2,L-1,1,3、同一级中，同一旋转因子对应蝶形数目,第,L,级,FFT,运算中，,同一旋转因子,用在,2,M-L,个蝶形中；,4、同一级中，蝶形运算使用相同旋转因子之间相隔的“距离”,第,L,级中，蝶距：,D=2,L,。,5、,同一蝶形运算两输入数据的距离,在输入倒序，输出原序的,FFT,变换中第,L,级的每一个蝶形的2个输入数据相距：,B=2,L-1,。,6、,码位颠倒,输入序列,x(n),经过,M,级时域奇、偶抽选后，输出序列,X(k),的顺序和输入序列的顺序关系为,倒位关系,。,4.2 基2,FFT,算法,7、,蝶形运算的规律,序列经过时域抽选后，存入数组中，如果蝶形运算的两个输入数据相距,B,个点，应用原位计算，蝶形运算可表示成如下形式：,4.2 基2,FFT,算法,X,L-1,(J),X,L-1,(J+B),X,L,(J)=X,L-1,(J)+,W,N,p,X,L-1,(J+B),X,L,(J)=X,L-1,(J),W,N,p,X,L-1,(J+B),W,N,p,p=J2M-L,，J=0,1,2,2,L-1,1,8、,DIT-FFT,程序框图,根据,DIT-FFT,原理和过程，,DIT-FFT,的完整程序框图包括以下几部分：,(1),倒序,:,输入自然顺序序列,x(n)，,根据倒序规律，进行倒序处理；,(2),循环层1,:,确定运算的级数，,L=1,M(N=2,M,)；,确定一蝶形两输入数据距离,B=2,L-1,(3),循环层2,:,确定,L,级的(,B=)2,L-1,个旋转因子；旋转因子指数,p=2,M-L,J，J=0,B-1,；,(4),循环层3,:对于同一旋转因子，用于同一级2,M-L,个蝶形运算中：,k,的取值从,J,到,N-1，,步长为2,L,(,使用同一旋转因子的蝶形相距的距离,),(5),完成一个蝶形运算,。,4.2 基2,FFT,算法,9.序列的倒序,N=2,M,，,用,M,位二进制数,(,n,M,-1,n,M-2,n,1,n,0,),2,表示序列的序号,n.,M,次偶奇时域抽选过程为,：对最低位按0、1分为偶、奇两组，次低位也按0、1分组，依此类推，,M,次分解后形成,倒序图,为：,4.2 基2,FFT,算法,二进制数(,N=8),分解倒序图,100,4,101,5,110,6,111,7,000,0,001,1,010,2,011,3,倒序前,001,1,101,5,011,3,111,7,000,0,100,4,010,2,110,6,倒序后,可见，只要将,顺序数,的二进制位倒置可得到对应的二进制,倒序值,。,1,0,n,2,0,1,0,1,n,1,0,0,0,1,0,n,0,1,1,1,(n,2,n,1,n,0,),2,思考题,：已知,N=16,点，在,DIT-FFT,运算中，序数为,2,的二进制经数倒序后为多少?,4.2 基2,FFT,算法,顺序数,增加1,，是在顺序数的二进制数的,最低位加1，向左,进位,到序数是在,M,位二进制数的,最高位加1，向右,进位,(0010-0100),顺序和倒序二进制数对照表,N=2,M,，,用,M,位二进制数表示，则从左至,右的十进制权值为：,N/2、N/4、N/8,、2,1对倒序数,J,，,其下一个序数是在该序数,J,的二进制首位码加1，相当于十进制运算,J,+N/2,。,计算机上倒序数的实现过程为：,4.2 基2,FFT,算法,JN/2,？,JN/4,输入当前倒序数,十进制数值,J,N,Y,N,Y,JN/2,M,N,Y,结束,J=J-N/2,倒序数的十进制运算规律,倒序程序框图,为了实现原位运算，以节约存贮空间，提高运算速率。在倒序数,J,形成后，需将原存储器中存放的输入序列重新排列。下面先分析,N=8,点的倒序规律。,4.2 基2,FFT,算法,x(0),A(0),x(1),A(1),x(2),A(2),x(3),A(3),x(4),A(4),x(5),A5),x(6),A(6),x(7),A(7),A(0),A(1),A(2),A(3),A(4),A(5),A(6),A(7),输入序列,数组,分析上图,N=8,点倒序规律，顺序数,I,与倒序数,J,存在关系：,I=J,时，不交换；,I J,时，不交换，直接更新序数值；,I,J,x(0),x(2),x(4),x(1),x(5),x(6),x(3),x(7),计算倒序值,交换数组中的数据,不交换数据，避免再次调换前面调换过的一对数据，计算下一个倒数值。,4.2.5 频域抽取法,FFT(DIFFFT),在基2快速算法中，频域抽取法,FFT,也是一种常用的快速算法。,1、算法思想和运算过程,设序列,x(n),长度为,N=2,M,，,将,序列,x(n),前后对半分为,x,1,(n)、x,2,(n),两组序列，用2个,N/2,点,DFT,来完成一个,N,点,DFT,的计算。,4.2 基2,FFT,算法,n,k=,偶数,k=,奇数,4.2 基2,FFT,算法,将,X(k),分解成,偶数组,与,奇数组,，当,k,取偶数(,k=2r,r=0,1,N/2-1),时,当,k,取奇数,(,k=2r+1,r=0,1,N/2-1),时：,将,x,1,(n),和,x,2,(n),分别代入上式，可得,x,1,(n),x,2,(n),表明,：,X(k),按奇偶,k,值分为两组:,偶数组,是,x,1,(n),的,N/2,点,DFT,奇数组,是,x,2,(n),的,N/2,点,DFT,n=0,1,N/2-1,那么对序列,x,1,(n)、x,2,(n),和,x(n),可用蝶形运算符号表示,4.2 基2,FFT,算法,x(n),x,1,(n)=x(n)+x(n+N/2),x,2,(n)=x(n),x(n+N/2),W,N,n,W,N,n,x(n+N/2),DIF-FFT,蝶形运算流图符号,N=8,时第1次分解的运算流图,X(3),N/2点DFT,N/2点DFT,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,20),x,2,(1),x,2,(2),x,2,(3),W,N,0,W,N,1,W,N,2,W,N,3,X(0),X(2),X(4),X(6),X(1),X(5),X(7),N=2,M,，,N/2,仍是偶数,，,继续将,N/2,点进行分解,。将输入序列,x,1,(n)、x,2,(n),分别按前、后对半分解成4个长,N/4,的子序列,其,n=0,1,，N/4-1,4.2 基2,FFT,算法,x,3,(n)=x,1,(n)+x,1,(n+N/4),x,4,(n)=x,1,(n)-x,1,(n+N/4),W,N/2,n,x,5,(n)=x,2,(n)+x,2,(n+N/4),x,6,(n)=x,2n)-x,2,(n+N/4),W,N/2,n,N,/4,点,DFT,W,N,0,W,N,1,W,N,2,W,N,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,(5),X,(3),X,(7),W,N,0,W,N,2,W,N,0,W,N,2,N,/4,点,DFT,N,/4,点,DFT,N,/4,点,DFT,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,3,(0),x,3,(1),x,4,(0)x,4,(1),x,5,(0),x,5,(1),x,6,(0),x,6,(1),DIFFFT,二次分解运算流图(,N=8),经过三次分解后，,DIFFFT,运算流图(,N=8),为,：,4.2 基2,FFT,算法,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),W,N,0,W,N,1,W,N,2,W,N,3,X(0),X(4),X(2),X(6),X(1),X(5),X(3),X(7),x,3,(0),x,3,(1),x,4,(0),x,4,(1),x,5,(0),x,5,(1),x,6,(0),x,6,(1),W,N,0,W,N,2,W,N,0,W,N,2,W,N,0,W,N,0,W,N,0,W,N,0,2、,DIF-FFT,运算规律,DIF-FFT,算法也可采用,原位,计算；,N=2,M,时，共有,M,级运算,，每级共有,N/2,个蝶形,，,DIT,与,DIF,算法的,运算次数,相同。,DIT,与,DIF,不同的是,：,DIF-FFT,算法,输入序列为自然序列,，,输出为倒序,序列。因此，在,M,级运算完成后，需对输出数据进行倒序才能得到自然顺序的,X(k)。,蝶形运算符号不同,：,DIT-FFT,蝶形是先相乘，后加/减；而,DIF-FFT,蝶形是先加/减，后相乘。,4.2 基2,FFT,算法,DIT-FFT,蝶形运算符号,X,1,(k),X,2,(k),X,1,(k)+,W,N,k,X,2,(k),X,1,(k),W,N,k,X,2,(k),W,N,k,x,2,(n)=x(n),x(n+N/2),W,N,n,x(n),x,1,(n)=x(n)+x(n+N/2),W,N,n,x(n+N/2),DIF-FFT,蝶形运算流图符号,3、其它形式的,DIT-FFT,运算流图,通过改变,输入/输出节点,中间节点,的排列顺序,可以得到不同变形的,FFT,运算流图。因此，前面介绍的,DIT-FFT,和,DIF-FFT,运算流图都不是唯一的,。,4.2 基2,FFT,算法,X(0),X(4),X(2),X(6),X(1),X(5),X(3),X(7),X,3,(0),X,5,(0),X,4,(0),X,6,(0),X,3,(1),X,5,(1),X,4,(1),X,6,(1),W,N,0,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,2,W,N,1,W,N,3,X,1,(0),X,2,(0,),X,1,(2),X,2,(2,),X,1,(1),X,2,(1),X,1,(3),X,2,(3,),W,N,0,W,N,0,W,N,0,W,N2,W,N,2,输出序列,输入序列,DIT-FFT,的一种变形运算流图（输入顺序，输出倒序）,用同样的方法可得,DIT-FFT,的另外一种变形运算流图，,输入和输出均为顺序排列，但不能采用原位计算。,4.2 基2,FFT,算法,DITFFT,的一种变形运算流图,4.2.6,IDFT,的高效算法,1,DFT,和,IDFT,的公式比较,上述,FFT,算法流图也可以用于离散傅里叶逆变换,IDFT,根据运算公式可以看出，只需将,DFT,的,系数,W,N,kn,变为,W,N,-,kn,，,最后结果,乘以1/,N,，,就是,IDFT,的运算公式。,第4章 快速傅里叶变换(,FFT),X(k),n,2 用FFT,流图实现,IDFT,快速算法,将,DIT-FFT,或,DIF-FFT,蝶形运算流图中,旋转因子,W,N,p,改为,W,N,-p,在,IDFT,快速算法的最后结果输出前，,乘以1/,N,常数,；如要防止溢出，可在每一级运算中，输出支路,分别乘以1/2,，实现系数分级分担。,在,IDFT,快速算法中，,输入序列为,X(k),，,而,输出序列为,x(n),。,节点对应关系：,DIT-FFT,对应,DIF-IFFT,DIF-FFT,对应,DIT-IFFT,第4章 快速傅里叶变换(,FFT),第4章 快速傅里叶变换(,FFT),DITIFFT,运算流图,第4章 快速傅里叶变换(,FFT),DITIFFT,运算流图(防止溢出),3、直接调用,FFT,程序实现,IFFT,的计算,对,FFT,流程作一些修改后，调用,FFT,程序实现,IFFT,的快速计算。,具体实现方法：,先将,X(k),取共轭,，得到,X*(k),；,直接调用,FFT,子程序计算出,DFTX*(k),的值；,对输出序列,取共轭,，并乘以,1/,N,常数。,虽然2次用了取共轭运算，但可以和,FFT,共用一个子程序，实现方便。,第4章 快速傅里叶变换(,FFT),*,本章作业,本章第一次作业,习题 1,习题 2,本章第二次作业,习题 3,习题 4,