FFT快速傅里叶变换（蝶形算法）详解ppt课件.ppt

《FFT快速傅里叶变换（蝶形算法）详解ppt课件.ppt》由会员分享，可在线阅读，更多相关《FFT快速傅里叶变换（蝶形算法）详解ppt课件.ppt（53页珍藏版）》请在三一办公上搜索。

1、第五章 快速傅里叶变换,本章目录,直接计算DFT的问题及改进的途径,按时间抽取的基2-FFT算法,按频率抽取的基2-FFT算法,快速傅里叶逆变换(IFFT)算法,Matlab实现,2,t课件,5.1 引言,DFT在实际应用中很重要: 可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长。FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。,3,t课件,5.2 直接计算DFT的问题及改进的途径,DFT的运算量,设复序列x(n) 长度为N点，其DFT为,k=0，N-1,（1）计算一个X(k) 值的运算量,复数乘法次数：,

2、N,复数加法次数：,N1,4,t课件,5.2.1 DFT的运算量,（2）计算全部N个X(k) 值的运算量,复数乘法次数：,N2,复数加法次数：,N(N1),（3）对应的实数运算量,5,t课件,一次复数乘法：,4次实数乘法,2次实数加法,一个X(k) ：,4N次实数乘法,2N+2(N-1)= 2(2N-1)次实数加法,所以,整个N点DFT运算共需要：,N2(2N-1)= 2N(2N-1),实数乘法次数：,4 N2,实数加法次数：,6,t课件,DFT运算量的结论,N点DFT的复数乘法次数举例,结论：当N很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，

3、以大大减少运算次数。,7,t课件,5.2.2 减少运算工作量的途径,主要原理是利用系数 的以下特性对DFT进行分解：,（1）对称性,（2）周期性,（3）可约性,另外，,8,t课件,5.3 按时间抽取的基2-FFT算法,算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取FFT算法的其它形式流程图,9,t课件,5.3.1 算法原理,设N2L，将x(n)按 n 的奇偶分为两组：,r =0，1，,则,10,t课件,式中，X1(k)和X2(k)分别是x1(n)和x2(n)的N/2的DFT。,另外，式中k的取值范围是：0，1， ，N/21 。,11,t课件

4、,因此， 只能计算出X(k)的前一半值。,后一半X(k) 值， N/2 ， N/2 1， ，N ？,利用,可得到,同理可得,12,t课件,考虑到,因此可得后半部分X(k),及前半部分X(k),k=0，1， ，N/21,k=0，1， ，N/21,13,t课件,蝶形运算,蝶形运算式,蝶形运算信号流图符号,因此，只要求出2个N/2点的DFT，即X1(k)和X2(k)，再经过蝶形运算就可求出全部X(k)的值，运算量大大减少。,14,t课件,以8点为例第一次按奇偶分解,以N=8为例，分解为2个4点的DFT，然后做8/2=4次蝶形运算即可求出所有8点X(k)的值。,15,t课件,蝶形运算量比较,复数乘法次

5、数：,N2,复数加法次数：,N(N1),复数乘法次数：,2*(N/2)2+N/2=N2/2+N/2,复数加法次数：,2*(N/2)(N/21)+2*N/2=N2/2,N点DFT的运算量,分解一次后所需的运算量2个N/2的DFTN/2蝶形：,因此通过一次分解后，运算工作量减少了差不多一半。,16,t课件,进一步按奇偶分解,由于N2L，因而N/2仍是偶数 ，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。,以N/2点序列x1(r)为例,则有,k=0,1,17,t课件,且,k=0,1,由此可见，一个N/2点DFT可分解成两个N/4点DFT。,同理，也可对x2(n)进行同样的分

6、解，求出X2(k)。,18,t课件,以8点为例第二次按奇偶分解,19,t课件,算法原理,对此例N=8，最后剩下的是4个N/4= 2点的DFT，2点DFT也可以由蝶形运算来完成。以X3(k)为例。,k=0, 1,即,这说明，N=2M的DFT可全部由蝶形运算来完成。,20,t课件,以8点为例第三次按奇偶分解,N=8按时间抽取法FFT信号流图,21,t课件,5.3.2 按时间抽取基2-FFT算法与直接计算DFT运算量的比较,由按时间抽取法FFT的信号流图可知，当N=2L时，共有 级蝶形运算；每级都由 个蝶形运算组成，而每个蝶形有 次复乘、 次复加，因此每级运算都需 次复乘和 次复加。,L,N/2,N

7、/2,1,2,N,22,t课件,这样 级运算总共需要：,L,复数乘法：,复数加法：,直接DFT算法运算量,复数乘法：,复数加法：,N2,N(N1),直接计算DFT与FFT算法的计算量之比为M,23,t课件,FFT算法与直接DFT算法运算量的比较,24,t课件,5.3.3 按时间抽取的FFT算法的特点,序列的逆序排列同址运算（原位运算）蝶形运算两节点间的距离 的确定,25,t课件,序列的逆序排列,由于 x(n) 被反复地按奇、偶分组，所以流图输入端的排列不再是顺序的，但仍有规律可循：,因为 N=2M ，,对于任意 n（0n N-1)，可以用M个二进制码表示为：,n 反复按奇、偶分解时，即按二进制

8、码的“0” “1” 分解。,序列的逆序排列,26,t课件,倒位序的树状图（N=8）,27,t课件,码位的倒位序(N=8),28,t课件,倒位序的变址处理（N=8）,29,t课件,同址运算（原位运算）,某一列任何两个节点k 和j 的节点变量进行蝶形运算后，得到结果为下一列k、j两节点的节点变量，而和其他节点变量无关。这种原位运算结构可以节省存储单元，降低设备成本。,运算前,运算后,例,同址运算（原位运算）,30,t课件,观察原位运算规律,31,t课件,蝶形运算两节点间的距离,以N=8为例：,第一级蝶形，距离为：,第二级蝶形，距离为：,第三级蝶形，距离为：,规律：对于共L级的蝶形而言，其m级蝶形运

9、算的节 点间的距离为,1,2,4,蝶形运算两节点间的距离,32,t课件,的确定,以N=8为例：,的确定,33,t课件,5.4 按频率抽取的基2-FFT算法,算法原理,再把输出X(k)按k的奇偶分组,先把输入按n的顺序分成前后两半,设序列长度为N=2L，L为整数,前半子序列x(n),后半子序列,0n,0n,34,t课件,5.4.1 算法原理,由DFT定义得,k=0，1， ，N,35,t课件,由于,所以,则,k=0，1， ，N,36,t课件,然后按k的奇偶可将X(k)分为两部分,r=0，1， ，,则式,可转化为,37,t课件,令,n=0，1， ，,代入,r=0，1， ，,可得,为2个N/2点的DF

10、T，合起来正好是N点X(k)的值。,38,t课件,蝶形运算,将,称为蝶形运算,与时间抽选基2FFT算法中的蝶形运算符号略有不同。,39,t课件,例 按频率抽取(N=8),例 按频率抽取，将N点DFT分解为两个N/2点DFT的组合(N=8),40,t课件,与时间抽取法的推导过程一样，由于 N=2L，N/2仍然是一个偶数，因而可以将每个N/2点DFT的输出再分解为偶数组与奇数组，这就将N/2点DFT进一步分解为两个N/4点DFT。,N=8,41,t课件,5.4.2 频率抽取法与时间抽取法的异同,频率抽取法输入是自然顺序，输出是倒位序的；时间抽取法正好相反。频率抽取法的基本蝶形与时间抽取法的基本蝶形

11、有所不同。频率抽取法运算量与时间抽取法相同。频率抽取法与时间抽取法的基本蝶形是互为转置的。,42,t课件,5.5 快速傅里叶逆变换(IFFT)算法,IDFT公式,DFT公式,比较可以看出，,IDFT多出,M个1/2可分解到M级蝶形运算中。,43,t课件,例 频率抽取IFFT流图(N=8),44,t课件,快速傅里叶逆变换另一种算法,45,t课件,5.8 Matlab实现,用FFT进行谱分析的Matlab实现用CZT进行谱分析的Matlab实现,在Matlab中使用的线性调频z变换函数为czt，其调用格式为X= czt(x, M, W, A)其中，x是待变换的时域信号x(n)，其长度为N，M是变换

12、的长度，W确定变换的步长，A确定变换的起点。若M= N，A= 1，则CZT变成DFT。,46,t课件,5.8.1 用FFT进行谱分析的Matlab实现,例5.1 设模拟信号 ，以 t= 0.01n (n=0: N-1) 进行取样，试用fft函数对其做频谱分析。N分别为：(1) N=45；(2) N=50；(3) N=55；(2) N=60。,程序清单如下,%计算N=45的FFT并绘出其幅频曲线N=45;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,1)plot(

13、q,abs(y)title(FFT N=45),47,t课件,例5.1程序清单,%计算N=50的FFT并绘出其幅频曲线N=50;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,2)plot(q,abs(y)title(FFT N=50),48,t课件,%计算N=55的FFT并绘出其幅频曲线N=55;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplo

14、t(2,2,3)plot(q,abs(y)title(FFT N=55),49,t课件,%计算N=60的FFT并绘出其幅频曲线N=60;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,4)plot(q,abs(y)title(FFT N=60),50,t课件,例5.1程序运行结果,从图中可以看出，这几种情况下均有较好的精度。,51,t课件,例5.1程序运行结果分析,分析：由t=0.01n进行取样可得，采样频率fs=100Hz。而连续信号的最高模拟角频率为8 ，由2 f可得，最高频率为8 /2 =4Hz。因此，满足采样定理的要求。 采样序列为,即,为周期序列，周期N=50。,将程序中plot改为stem函数，则可以更清楚地看出频谱。,52,t课件,例5.1修改程序运行结果,53,t课件,