第7章 应用程序设计.ppt

1、7.5 快速傅里叶变换FFT,FFT算法原理 库利一图基算法 FFT算法的实现,1. FFT算法的原理,对于长度为N的有限长序列x(n)，它的离散傅里叶变换为：,k = 0,1,N-1,WN = e-j2/N，称为旋转因子，或蝶形因子。,离散傅氏变换DFT,在x(n)为复数序列的情况下，计算X(k): 对某个k值，需要N次复数乘法、(N-1)次复数加法； 对所有N个k值，需要N2次复数乘法和N(N-1)次复数加法。,X(0) = x0WN0 + x1WN0*1 + xN-1WN0*(N-1) X(1) = x0WN0 + x1WN1*1 + xN-1WN1*(N-1) : X(k) = x0W

2、N0 + x1WNk*1 + xN-1WNk*(N-1) : X(N-1)= x0WN0 + x1WN (N-1)*1 + xN-1WN (N-1)(N-1),离散傅氏变换DFT,旋转因子WN的特性：, 周期性, 对称性,W80 = W88,W81 = W89,W82,W84,W83,W86,W87,W85,WNk+N/2 = -WNk,WNk+N = WNk,W8k+4 = -W8k,W8k+8 = W8k,旋转因子WN的特性,例: N=8,例如：当N为偶数时，其算法： 将N点的DFT分解为两个N/2点的DFT，使复数乘法减少一半； 将每个N/2点的DFT分解成N/4点的DFT，使复数乘法又

3、减少 一半，继续进行分解可以大大减少计算量。,假定序列x(n)的点数N是2的幂，按照DIT FFT算法可分解为：,偶序列：x(0)，x(2)，x(4)，x(N -2) 即x1(n) = x(2n)，r = 0，1，,奇序列：x(1)，x(3)，x(5)，x(N -1) 即x2(n) = x(2n+1)，r = 0，1，,快速傅氏变换FFT,快速傅氏变换FFT,WN2nk=e-j(2/N)nk2=e-j2/(N/2)nk= WN/2nk,快速傅氏变换FFT,k = 0,1,N/2-1,由于对称性，WNk+N/2 = -WNk， 则 X(k+N/2)=X1(k) - WNkX2(k)。,N点X(k

4、)可分为两部分： 前半部分：X(k)=X1(k) + WNkX2(k) k=0, 1, N/2-1 后半部分：X(k+N/2)=X1(k)-WNkX2(k) k=0, 1, N/2-1,快速傅氏变换FFT,k = 0,1,N/4-1,WN2nk= WN/2nk,X(0)= x(0)+x(4)W0 + (x(2)+x(6)W0 W0 + x(1)+x(5) W0 +x(3)+x(7)W0 W0 W0 X(1)= x(0)-x(4)W0 + (x(2)-x(6)W0 W2 + x(1)-x(5) W0 +x(3)-x(7)W0 W2 W1 X(2)= x(0)+x(4)W0 - (x(2)+x(6)W0 W0 + x(1)+x(5) W0 +x(3)+x(7)W0 W0 W2 ,例：N=8,快速傅氏变换FFT,基2 DIT FFT的蝶形运算：,蝶形算法： xm(p)= xm-1(p)+ xm-1(q)WNk xm(q)= xm-1(p) - xm-1(q)WNk,在基数为2的FFT中，设N=2M，共有M级运算，每级有N/2个2点FFT蝶形运算，因此，N点FFT总共有(N/2)log2N个蝶形运算