数字信号处理-第4章I

《数字信号处理-第4章I》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章离散傅里叶变换快速算法（FFT）1快速傅里叶变换（FFT）是计算DFT的一种快速有效方法，并不是新的傅立叶变换式。从前面的讨论中看到，有限长序列在数字技术中占有很重要的地位。有限长序列的一个重要特点是其频域也可以离散化，即离散傅里叶变换（DFT）。2DFT是信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。1965年发现了DFT的一种快速算法，使DFT的运算效率提高1－2个数量级

2、，为数字信号处理技术应用于各种信号的实时处理创造了条件，推动了数字处理技术的发展。1984年，提出了分裂基快速算法，使运算效率进一步提高；3一、直接计算DFT的问题及改进的方法DFT的定义两者形式类似，差别只在于的指数符号不同，及常数因子。运算量是相同的41、运算量运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)(a+jb)(c+

3、jd)=(ac-bd)+j(ad+bc)∑-=10)(NnnkNWnx562、减少运算量的途径具有如下特性：使DFT运算中的有些项可以合并。可将长序列的DFT分解为短序列的DFT。对称性周期性可约性knNNkNnNWW=--)()(=kNNkNNNWWW-=-=+)2/(2/,17二、按时间抽取(DIT)的基-2FFT算法设M为自然数将长度为N的序列x(n)按n的奇偶分成两组)12/(,1,0),12()()12/(,1,0),2()(21-=+=-==NrrxrxNrrxrx……1、算法原理8则

4、x(n)的DFT为)()(21kXWkXkN+=∑∑--+=12/2/212/2/1)()(NkrNkNNkrNWrxWWrxr=0r=01、算法原理9其中是x(2r)与x(2r+1)的N/2点DFT。1、算法原理10由于得12,,1,0-=Nk…1、算法原理11信号流图将X1(k)和X2(k)合成X(k)运算可归结为：蝶形运算的简化Wa+bWa-bW-W-1a+bWa-bWWabab(a)(b)X1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk图：蝶形运算

5、符号124点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFTX[0]X[1]X[2]X[3]138点基2FFT算法N/2点DFTN/2点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)｛N=8点的DIT-2FFT(时域抽取图)一次分解图14(3

6、)第二次分解：将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1)，根据上面推导可得：X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/2-1将x2(r)按r取奇、偶可分解成2个长N/4的子序列x5(l)=x2(2l)，l=0,1,…，N/4x6(l)=x2(2l+1)；同理得l=0,1,…，N/4-1；X1(k+N/2)=X3(k)WN/2kX4(k)，k=0,1,…,N/4-1；X1(k)=X3(k)+WN/2kX

7、4(k)，k=0,1,…,N/4-1；X2(k)=X5(k)+WN/2kX6(k)，k=0,1,…,N/4-1；X2(k+N/2)=X5(k)WN/2kX6(k),k=0,1,…,N/4-1；15N/4点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N/4点DFTN/4点DFTN/4点DFTX3(0)X3

8、(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/21WN/20N=8点DFT的二次时域抽取分解图X1(k+N/2)=X3(k)WN/2kX4(k)X1(k)=X3(k)+WN/2kX4(k)X2(k)=X5(k)+WN/2kX6(k)X2(k+N/2)=X5(k)WN/2kX6(k)k=0,1,…,N/4-1；16最后剩下的是2点DFT，它可以用一个蝶形结表示：由于这种方法每一步分解都是按输入时间序列是属于偶数还