第五章 快速傅里叶变换(FFT)(数字信号处理)

《第五章 快速傅里叶变换(FFT)(数字信号处理)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章快速傅里叶变换(FFT)5.1引言DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。5.2基2FFT算法5.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(5.2.1

2、)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(5.2.1)如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(5.2.2)其对称性表现为或者5.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两大类：时域抽取法FFT(DecimationInTimeFFT,简称DIT-FFT)和频域抽取法FFT(DecimationInFrequencyFFT,简称DIF―FFT)。

3、下面先介绍DIF―FFT算法。设序列x(n)的长度为N，且满足为自然数按n的奇偶性将x(n)分解为两个N/2点的子序列则x(n)的DFT为由于所以其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即(5.2.5)(5.2.6)由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为(5.2.7)(5.2.8)图5.2.1蝶形运算符号图5.2.2N点DFT的一次时域抽取分解图(N=8)与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l

4、)，即那么，X1(k)又可表示为(5.2.9)式中同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到：(5.2.10)用同样的方法可计算出(5.2.11)其中图5.2.3N点DFT的第二次时域抽取分解图(N=8)图5.2.4N点DIT―FFT运算流图(N=8)5.2.3DIT―FFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为例如，N=210=1

5、024时图5.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线5.2.4DIT―FFT的运算规律及编程思想1.原位计算由图5.2.4可以看出，DIT―FFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。2.旋转因子的变化规律如上所述，N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数。观察图5.2.4不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：L=1时，

6、WpN=WJN/4=WJ2L，J=0L=2时，WpN=WJN/2=WJ2L，J=0，1L=3时，WpN=WJN=WJ2L，J=0，1，2，3对N=2M的一般情况，第L级的旋转因子为(5.2.12)(5.2.13)3.蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：X(J)XL-1(J)+XL-1(J+B)WpNXL(J+B)XL-1(J)-XL-1(J+B)WpN式中p=J·2M-L；J=0,1,…，2L-

7、1-1；L=1,2,…，M下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设T=XL-1(J+B)WpN=TR+jTIXL-1(J)=X′R(J)+jX′I(J)式中下标R表示取实部，I表示取虚部，则4.编程思想及程序框图图5.2.6DIT―FFT运算和程序框图5.序列的倒序DIT―FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2…

8、n1n0)表示。图5.2.7形成倒序的树状图(N=23)表5.2.1顺序和倒序二进制数对照表图5.2.8倒序规律图5.2.9倒序程序框图5.2.5频域抽取法FFT(DIF―FFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIF―FFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：偶数奇数将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,…,N/2-1)时(5.2.14)当k取