数字信号处理(理论算法与实现)第4章

《数字信号处理(理论算法与实现)第4章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章快速傅立叶变换（FFT）4.1概述4.2时间抽取基2算法4.3频率抽取基2算法4.4减少运算量的措施4.5分裂基算法4.6线性调频Z变换4.7其它算法4.1概述N1j2nkNXk（)xne()k0,1,N1n0N11j2nkNxn()Xke()n0,1,N1Nk0若xn()是N点序列，实现xn()的DFT，即求出个NXk（）需要：2N次复数乘法，（NN1）次复数加法!2xn():N＝1024，N＝104857642xnn():NN512,N262144!1,212解决耗时的乘法问题是将数字信号

2、处理理论用于实际的关键问题。特别是30年前，计算机的速度相当慢。因此，很多学者对解决DFT的快速计算问题产生了极大的兴趣。CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301FFT的思路：W＝ej2/NN1nkXk（)xnW()k0,1,N1n001.W1如何充NmN2.W1,W1分利用Nrr这些关3.WWN系4.W21Nr2r5.W

3、W0000X(0)WWWWx(0)0123X(1)WWWWx(1)X(2)W0W2W4W6x(2)四点X(3)W0W3W6W9x(3)DFT1111x(0)111W1Wx(1)1111x(2)1W11W1x(3)1111x(0)1111WWx(2)1111x(1)11W1W1x(3)X(0)[(0)xx(2)][(1)xx

4、(3)]几个1X(1)[(0)xx(2)][(1)xx(3)]W乘X(2)[(0)xx(2)][(1)xx(3)]法1？X(3)[(0)xx(2)][(1)xx(3)]Wx(0)x(2)x(0)X(0)x(0)x(2)x(2)X(1)1x(1)x(3)x(1)X(2)1x(1)x(3)x(3)X(3)111W4.2时间抽取基2算法N点N/2点N/4点2点DFTDFTDFTDFT1个2个4个N/2个问题是如何分最有效？可以对时间变量分（DIT)，也可对频率变量分(DIF）令：n2rr0,1,,N

5、21n2r1N1nkXk（)xnW()n0N/21N/212rk(2r1)kxrW(2)Nxr(21)WNr0r0N/21N/21rkkrkxrW(2)N/2WNxr(21)WN/2r0r0N/21N/21rkkrkXk（)xr(2)WN/2WNxr(21)WN/2r0r0Ak()k0,1,N/21Bk()kNXk()Ak()WBk()k0,1,,1N2NkNXk()Ak()WBk()k0,1,,1N22Ak()Xk()kNBk()WNXk(

6、)12AkBk(),()都是N/2点的DFT，它们各自又可分成N/4点的DFT，如此继续分下去，直至两点DFT。两点DFT不需要乘法运算：X(0)x(0)x(1)X(1)x(0)x(1)M对N2，共可分M次，即m0,1,,M1，每一级有N/2个如下的“蝶形”单元：xm()pxm1()prxq()WNx()qmm11xm()pxm1()prxq()WNx()qmm11rx()px()pxqW()Nm1mmrx()qx()pxqW()Nm1mm即:每一个蝶形单元仅需一个复数乘法，两个复数加法。两点构成一

7、个蝶形单元，并且这两点不再参与别的蝶形单元的运算。同址运算。注意：所需运算量：rNNW因子的位置；MMlogNc222输入序列的顺序MNMNlogNa2－－码位倒置。nxn()Xk()k00000000410000112010010261100113100110045101101530111106711111174.3频率抽取基2算法N/21N1nknkXk（)xn()WNxn()WNn0nN/2N/21N/21nknkNk/2xn()WNxn(N/2)WWNNn0n0N/21knk[()

8、(1)xnxnN(/2)]WNn0令：k2,rk2r1r0,1,,N21gn()N/21nrX(2)r[()xnxn(N/2)]WN/2hn()n