第2章-离散傅里叶变换及其快速算法2.ppt

2.3 快速傅里叶变换 （FFT） 1、DFT运算的特点： FFT算法的基本思想： 2）利用 的周期性和对称性，把长度为N点的大点数的DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正比于N2，N小，计算量也就小。 FFT算法正是基于这样的基本思想发展起来的。它有多种形式，但基本上可分为两类：时间抽取法和频率抽取法。 2、按时间抽取的FFT（N点DFT运算的分解） 将DFT运算也相应分为两组： 蝶形信号流图 时间抽取法FFT的运算特点： 第一次分偶、奇，根据最低位n0的0、1状态来分，若n0=0，则为偶序列；n0=1则为奇序列，得到两组序列： 000 010 100 110 ? 001 011 101 111 第二次对这两个偶、奇序列再分一次偶、奇序列，这就要根据n1的０、１状态。若n1=0，则为偶序列；n1=1则为奇序列，得到四组序列： 000 100 ? 010 110 ? 001 101 ? 011 111 同理，再根据n2的０、１状态来分偶、奇序列，直到不能再分偶、奇时为止。对于N=8, n2已是最高位，最后一次分得结果为 000 ? 100 ? 010 ? 110 ? 001 ? 101 ? 011 ? 111 3、按频率抽取的FFT（按输出X(k)在频域的顺序上属于偶数还是奇数分解为两组） 以N=8的频率抽取为例 4. N为组合数的FFT（任意基数的FFT算法） 以P=3，Q=4, N=12为例 (1) 先将 x(n)通过 x(n1Q+n0)改写成 x(n1,n0)。因为 Q=4, n1=0,1,2, n0=0,1,2,3,故输入是按自然顺序的，即 x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,3)=x(3) x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,3)=x(7) x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,3)=x(11) （2）求Ｑ个Ｐ点的DFT （３）X1(k0,n0)乘以旋转因子得到X1/(k0,n0)。 （４）求P个Ｑ点的DFT，参变量是k0 （１）求Ｑ个P点DFT需要ＱP2次复数乘法和Ｑ·P·(P-1)次复数加法； （２）乘Ｎ个W因子需要Ｎ次复数乘法； （３）求P个Ｑ点DFT需要PQ2 次复数乘法和P·Ｑ（Ｑ-1)次复数加法。 总的复数乘法量: QP2+N+PQ2=N(P+Q+1)； 总的复数加法量: Q·P(P-1)+P·Q·(Q-1)=N(P+Q-2) 当组合数 N=P1P2P3…Pm中所有的Pi均为4时，就是基四FFT算法 以N=43为例,第一级运算的一般形式为： 5、Chirp-z变换 提出原因（特点） 公式表达 快速算法（卷积形式理解） 运算量比较 算法原理： Chirp-z变换的计算步骤： 由于输入信号 g(n)是有限长的，长为N，但序列 是无限长的，而计算 0～M-1 点卷积 g(k)*h(k)所需要的h(n)是取值在n=-(N-1)～(M-1)那一部分的值，即L点。那么g(n)和h(n)两个序列线性卷积时需要延拓的周期为2N+M-2。但是，由于我们只需要M点X(k)，对以后的卷积结果是否有混叠失真并不感兴趣，这样循环卷积的点数，即延拓周期可以仍是L。 Chirp-z变换的特点： 2.4 FFT应用中的几个问题 例x1(n)={1,2,3}, x2(n)={5,4,-3,-2}循环卷积和线性卷积 L=4+3-1时，线性卷积等于循环卷积 若L6，则由于循环卷绕，循环卷积和线性卷积结果存在误差 线性卷积重叠相加得到循环卷积结果：5-13=-8，14-6=8 a)??? 重叠相加法 补零相加 b)重叠保留法 重叠保留法与重叠相加法的计算量差不多，但省去了重叠相加法最后的相加运算。 修改相关的定义，加上共轭；或者认为x、y是实数序列 利用FFT求两个有限长序列的线性相关： x=[1 3 -1 1 2 3 3 1]; y=[2 1 -1 1 2 0 -1 3]; k=length(x); xk=fft(x,2*k); yk=fft(y,2*k); rm=real(ifft(conj(xk).*yk)); rm=[rm(k+2:2*k) rm(1:k)]; m=(-k+1):(k-1); stem(m,rm) xlabel(m); ylabel(幅度); 例9 实验分为两次 一、应用FFT对典型信号进行频谱分析 （2、3）