快速傅里叶变换课件

1、快速傅里叶变换快速傅里叶变换快速傅里叶变换本章目录直接计算DFT的问题及改进的途径按时间抽取的基2-FFT算法 按频率抽取的基2-FFT算法 快速傅里叶逆变换(IFFT)算法 Matlab实现2本章目录直接计算DFT的问题及改进的途径按时间抽取的基2-FFT算法 按频率抽取的基2-FFT算法 快速傅里叶逆变换(IFFT)算法 Matlab实现24.1 引言 DFT在实际应用中很重要: 可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长,实时处理难以实现。1965年，图基和库利发表了机器计算快速傅立叶级数的一种算法论文后，很快形成了

2、快速计算DFT的计算机算法FFT。（Fast Fourier Transform)FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。 34.2 直接计算DFT的问题及改进的途径 DFT的运算量 设复序列x(n) 长度为N点，其DFT为k=0，N-1 （1）计算一个X(k) 值的运算量复数乘法次数： N复数加法次数： N1（2）计算全部N个X(k) 值的运算量复数乘法次数： N2复数加法次数： N(N1)4DFT运算量的结论N点DFT的复数乘法次数举例NN2NN22464404941612816384864256 65 536 16256512 262 144 32102410

3、24 1 048 576 结论：当N很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，以大大减少运算次数。 5 4.2.2 减少运算工作量的途径 主要原理是利用系数 的以下特性对DFT进行分解： （2）对称性 （1）周期性 （3）可约性 另外，64.3 按时间抽取的基2-FFT算法 算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取FFT算法的其它形式流程图DIT-FFT(Decimation-In-Time)74.3.1 算法原理 设N2M，将x(n)按 n 的奇偶分为两组： r =0，1， 则8

4、式中，X1(k)和X2(k)分别是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范围是：0，1， ，N/21 。9因此， 只能计算出X(k)的前一半值。后一半X(k) 值， N/2 ， N/2 1， ，N-1 ？同理可得10因此可得后半部分X(k) 由前半部分X(k) k=0，1， ，N/21k=0，1， ，N/2111k=0，1， ，N/21结论：因此，只要求出2个N/2点的DFT，即X1(k)和X2(k)，再经过这种运算就可求出全部X(k)的值12新概念：蝶形运算蝶形运算式蝶形运算信号流图符号 X1(k)X2(k)蝶形运算的运算量：每次蝶形含一次复数乘和两 次复数加13以8点为

5、例第一次按奇偶分解以N=8为例，分解为2个4点的DFT，然后做8/2=4次蝶形运算即可求出所有8点X(k)的值。分解一次后所需的运算量2个N/2的DFTN/2蝶形14运算量比较复数乘法次数： N2复数加法次数： N(N1)复数乘法次数： 2*(N/2)2+N/2=N2/2+N/2复数加法次数： 2*(N/2)(N/21)+2*N/2=N2/2N点DFT的运算量 分解一次后所需的运算量2个N/2的DFTN/2蝶形：通过一次分解后，运算工作量减少了差不多一半。每次蝶形含一次复数乘和两次复数加15进一步按奇偶分解 由于N2M，因而N/2仍是偶数 ，可以进一步把每个N/2点子序列再按其奇偶部分分解为两

6、个N/4点的子序列。 以N/2点序列x1(r)为例 则有 k=0,1, 16且k=0,1, 由此可见，一个N/2点DFT可分解成两个N/4点DFT。 同理，也可对x2(n)进行同样的分解，求出X2(k)。 17以8点为例第二次按奇偶分解概念：信号流图18算法原理 对此例N=8，最后剩下的是4个N/4= 2点的DFT，2点DFT也可以由蝶形运算来完成。N=2这说明，N=2M的DFT可全部由蝶形运算来完成。因此：N必须是2的整数次幂. “基2”蝶形运算19以8点为例第三次按奇偶分解N=8按时间抽取法FFT信号流图 x(n)抽取X(k)顺序DIT-FFT(Decimation-In-Time)FFT

7、算法204.3.2 按时间抽取基2-FFT算法与直接计算DFT运算量的比较 由按时间抽取法FFT的信号流图可知，当N=2M时，共有 级蝶形运算；每级都由 个蝶形运算组成，而每个蝶形有 次复乘、 次复加，因此每级运算都需 次复乘和 次复加。 MN/2 N/2 12N21FFT算法中，这样 级运算总共需要： M复数乘法： 复数加法： 直接DFT算法运算量 复数乘法： 复数加法： N2N(N1)直接计算DFT与FFT算法的计算量之比为MN=2M22FFT算法与直接DFT算法运算量的比较NN2计算量之比M NN2计算量之比M 2414.012816 38444836.641644.025665 536

8、1 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404919221.42324N=1024; M=80;x=1:M,zeros(1,N-M);t=cputime;y1=fft(x,N);time_fft=cputime-t;t1=cputime;y2=dft(x,N);time_dft=cputime-t1;FFT算法与直接DFT算法运算量的比较time_dft=6.0290time_fft=0.010025L=1L=2L=3倒

9、序4.3.3 按时间抽取的FFT算法的特点26同址运算（原位运算）序列的逆序排列蝶形运算两节点间的距离相同旋转因子节点间的距离 (旋转因子）的确定27同址运算（原位运算） 某一列任何两个节点k 和j 的节点变量进行蝶形运算后，得到结果为下一列k、j两节点的节点变量，而和其他节点变量无关。这种原位运算结构可以节省存储单元，降低设备成本。运算前运算后例同址运算（原位运算）28观察原位运算规律29序列的逆序排列 由于 x(n) 被反复地按奇、偶分组，所以流图输入端的排列不再是顺序的，但仍有规律可循： 因为 N=2M ， 对于任意 n（0n N-1)，可以用M个二进制码表示为： n 反复按奇、偶分解时

10、，即按二进制码的“0” “1” 分解。序列的逆序排列30倒位序的树状图（N=8） 31码位的倒位序(N=8) 自然顺序 n二进制数倒位序二进制数倒位序顺序数0000000010011004201001023011110641000011510110156110011371111117IJ规律：最左端加1，向右进位倒序32倒位序的变址处理（N=8）I=J 不换IJ 不换IX= czt(x, M, W, A)其中，x是待变换的时域信号x(n)，其长度为N，M是变换长度，W确定变换的步长，A确定变换的起点。若M= N，A= 1，则CZT变成DFT。754.8.1 用FFT计算实信号的快速线性卷积设一

11、离散线性移不变系统的冲激响应为 ,其输入信号为 .其输出为 .并且 的长度为N点, 的长度为M点,计算其线性卷积。76用FFT算 的步骤： 77FFTFFTIFFTxx(n)h(n)y(n)X(k)H(k)Y(k)流程图程序参考第三章幻灯片784.8.2 用FFT进行谱分析的Matlab实现例4.8.2 设模拟信号 ，以 t= 0.01n (n=0: N-1) 进行取样，试用fft函数对其做频谱分析。N分别为：(1) N=10；(2) N=50；(3) N=100；(2) N=1024。 程序清单如下 %计算N=10的FFT并绘出其幅频曲线N=10;n=0:N-1;t=0.01*n;q=n*2

12、*pi/N;x=2*sin(20*pi*t)+5*cos(40*pi*t);y=fft(x,N);figure(1)subplot(2,2,1)plot(q,abs(y)title(FFT N=10)79例4.8.2 程序清单%计算N=50的FFT并绘出其幅频曲线N=50;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(20*pi*t)+5*cos(40*pi*t);y=fft(x,N);figure(1)subplot(2,2,2)plot(q,abs(y)title(FFT N=50)80%计算N=100的FFT并绘出其幅频曲线N=100;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(20*pi*t)+5*cos(40*pi*t);y=fft(x,N);figure(1)subplot(2,2,3)plot(q,abs(y)titl