第五章快速傅立叶变换，2、本章目录直接计算DFT的问题和改进途径，按时间提取的基底2 FFT算法，按频率提取的基底2 FFT算法，快速傅立叶逆变换(IFFT )算法，Matlab的实现，3、 DFT在实际应用中很重要，如果用可以计算：信号频谱、功率谱的直接DFT变换来计算，序列长度n大的情况下，计算量非常多，所需时间变长。 FFT不是与DFT不同的变换，而是DFT的高速计算的算法。 4、5.2直接计算DFT问题及改进途径。 DFT的运算量是将复序列x(n )的长度设为n点，该DFT是计算一个k=0，…，N-1，)1) x(k )的值的运算量，复乘法次数：n，复加法次数：)。 N2，复数加法次数：N(N-1 )，3 )对应的实数运算量，6，一次复数乘法：四次实数乘法，二次实数加法，一个x ) k )，4N次实数乘法，2N2(N-1 ) 结论： n大时，其运算量大，实时性高的信号处理要求计算速度快，因此有必要改进DFT的计算方法，大幅减少运算次数。8、5.2.2减少运算量的方法，主要原理是利用系数的以下特性来分解DFT。1 )对称性，2 )周期性，3 )可约性，，9，5.3小时提取的基底2-FFT算法，原理时间提取基础-2FFT算法与直接计算DFT运算量的比较时间提取的FFT算法的特征时间提取FFT 5.3.1算法原理，假定N=2L，x(n )利用n个奇偶校验被分成两个组，且公式中k的可能范围为0、1、…、N/2-1。12，所以只能计算x(k )的前一半的值。下半场的x(k )值，N/2，N/2 1，…，n？ 利用，就能得到。 同样，如果考虑、13、则得到后半部x(k )及前半部x(k )、k=0，1，…、N/2-1，k=0，1，…、n/2-1，14，蝶形运算、16、蝶形运算量比较、复数乘法次数：N2、复数相加次数：n(n-1 )、复数乘法次数：2* ) N/2 ) 2 N/2=N2/2 N/2、复数相加次数：2* ) (n ，以N/2点列x1(r )为例，k=0，1，18，然后k=0，1，一个N/2点DFT可以分解为两个N/4点DFT 另外，同样地，对x2(n )也进行同样的分解，可以求出x2 ) k )。 以、19、8点为例，第二次奇偶分解、20、算法原理，该例中N=8，最后剩下的是4个N/4=2点的DFT，2点的DFT也可以通过蝶形运算进行。 以x3(k )为例。k=0，1，即N=2M的DFT都表示能够进行蝶形运算。21、8点为例，从第三次奇偶分解、N=8小时提取法FFT信号流图、22、5.3.2小时提取基础2-FFT算法与直接计算的DFT运算量的比较、时间提取法FFT信号流图可知，N=2L 各级由蝶形运算构成，但由于各级蝶形有乘法、乘法、加法，各级运算需要乘法和加法。
、l、N/2、N/2、1、2、n、23、…这样电平运算共有：l、复数乘法：复数加法：直接DFT算法运算量、复数乘法：复数加法：N2、 如果需要n () n-1，则直接DFT算法和FFT算法计算每5.3.3小时提取的FFT算法的特征、序列的反向排列同地址运算(原位运算)蝶形运算两节点间的距离的确定，220 对于序列的逆序排列，x ) n )是重复的奇、偶分组，从而流图的输入端的排列不再是顺序，但是N=2M，因此可以规则地遵循任意排列，序列的逆序排列，27，逆序逆序索引处理) N=8)，30，同地址运算)原位运算)，对某列的任意两个节点k和j的节点变量进行蝶形运算，这样的原位运算结构能够节约存储单元，降低设备成本、运算前、运算后，例如观察同地址运算(原位运算)、31、原位运算法则
32,蝶形运算两节点间的距离,以N=8为例：,第一级蝶形，距离为：,第二级蝶形，距离为：,第三级蝶形，距离为：,规律：对于共L级的蝶形而言，其m级蝶形运算的节 点间的距离为,1,2,4,蝶形运算两节点间的距离,,33,的确定,以N=8为例：,的确定,,34,5.4 按频率抽取的基2-FFT算法,算法原理,再把输出X(k)按k的奇偶分组,先把输入按n的顺序分成前后两半,,设序列长度为N=2L，L为整数,前半子序列x(n),后半子序列,,,0≤n≤,0≤n≤,,35,5.4.1 算法原理,由DFT定义得,k=0，1， …，N,,36,,由于,所以,则,k=0，1， …，N,,37,,然后按k的奇偶可将X(k)分为两部分,r=0，1， …，,则式,可转化为,,,38,,令,n=0，1， …，,代入,r=0，1， …，,可得,为2个N/2点的DFT，合起来正好是N点X(k)的值。,,39,蝶形运算,将,称为蝶形运算,与时间抽选基2FFT算法中的蝶形运算符号略有不同。,,40,例 按频率抽取(N=8),例 按频率抽取，将N点DFT分解为两个N/2点DFT的组合(N=8),,41,,与时间抽取法的推导过程一样，由于 N=2L，N/2仍然是 一个偶数，因而可以将每个N/2点DFT的输出再分解为偶数组 与奇数组，这就将N/2点DFT进一步分解为两个N/4点DFT。,N=8,,42,5.4.2 频率抽取法与时间抽取法的异同,频率抽取法输入是自然顺序，输出是倒位序的；时间抽取法正好相反。 频率抽取法的基本蝶形与时间抽取法的基本蝶形有所不同。 频率抽取法运算量与时间抽取法相同。 频率抽取法与时间抽取法的基本蝶形是互为转置的。,,43,5.5 快速傅里叶逆变换(IFFT)算法,IDFT公式,DFT公式,比较可以看出，,,,IDFT多出,,M个1/2可分解到M级蝶形运算中。,,44,例 频率抽取IFFT流图(N=8),,45,快速傅里叶逆变换另一种算法,,46,5.8 Matlab实现,用FFT进行谱分析的Matlab实现 用CZT进行谱分析的Matlab实现,在Matlab中使用的线性调频z变换函数为czt，其调用格式为 X= czt(x, M, W, A) 其中，x是待变换的时域信号x(n)，其长度为N，M是变换的长度，W确定变换的步长，A确定变换的起点。若M= N，A= 1，则CZT变成DFT。,,47,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(q,abs(y)) title('FFT N=45'),,48,例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'),,49,,%计算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) subplot(2,2,3) plot(q,abs(y)) title('FFT N=55'),,50,,%计算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'),,51,例5.1程序运行结果,从图中可以看出，这几种情况下均有较好的精度。,,52,例5.1程序运行结果分析,分析：由t=0.01n进行取样可得，采样频率fs=100Hz。而连续信号的最高模拟角频率为Ω＝8 π ，由Ω＝2 πf可得，最高频率为8 π /2 π=4Hz。因此，满足采样定理的要求。 采样序列为,即,为周期序列，周期N=50。,将程序中plot改为stem函数，则可以更清楚地看出频谱。,,53,例5.1修改程序运行结果,,展开阅读全文