数字信号处理第8章.ppt

《数字信号处理第8章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章DSP算法实现8.3离散傅里叶变换(DFT)的计算本节中，我们讨论傅里叶变换的快速算法---FFT算法。我们仅考虑按时间抽取FFT算法。DFT直接算法的运算量复旋转因子WNkn的性质按时间抽取FFT算法的原理8.3离散傅里叶变换(DFT)的计算蝶形运算位倒序FFT算法编程DFT直接算法的运算量N2次复数乘法N(N-1)次复数加法DFT直接算法的运算量:返回复旋转因子WNk的性质我们研究FFT算法，首先要关注复旋转因子WNk的性质:复旋转因子WNk的性质首先，它是k的周期函数，周期为N:其次，复旋

2、转因子WNk的性质第三，它是关于k的对称函数:利用复旋转因子的这些特性，使得我们计算DFT更加高效。返回按时间抽取FFT算法按时间抽取FFT算法考虑序列x[n]的长度N是2的整数次幂，即：N=2:x[0],x[1],x[2],x[3],x[4],…,x[N-1]则x[n]的DFT：令按时间抽取FFT算法x[0],x[1],x[2],x[3],x[4],…,x[N-1]令：按时间抽取FFT算法流程图表示N=2=8(N2/2)+N复数乘法(N2/2)复数加法按时间抽取FFT算法再令：得到：按时间抽取F

3、FT算法流程图表示N=2=8按时间抽取FFT算法这四个2点DFT：Xij[k],i,j=0,1，很容易计算出来按时间抽取FFT算法8-点DFT的完整流图如下：按时间抽取FFT算法整个流图包含3级。第一级计算四个2-点DFT；第二级计算两个4-点DFT；第三级计算期望的8-点DFT。每一级的复数乘法和复数加法的次数均为8，即DFT变换的点数。按时间抽取FFT算法DFT直接算法和基-2FFT算法的比较：返回蝶形运算可以进一步简化运算。.在上面过程中，我们考虑同和的相乘也为复数。利用对称性质:蝶形运算重新

4、再看流图:流图显示DFT运算过程中的每一级都用到了相同的基本运算模块。蝶形运算基本运算模块称为蝶形运算。蝶形运算基本运算模块称为蝶形运算。蝶形运算基本运算模块称为蝶形运算。蝶形运算利用改进的蝶形运算模块，使FFT计算的复数乘法的总数减少了50%.蝶形运算N=8,μ=3蝶形运算改进的蝶形运算模块的新流图，N=8:蝶形运算上述改进的FFT算法的另一个吸引人的特性是存储要求。避免，，和的乘法，进一步降低了运算复杂度。蝶形运算我们从[]和[]计算出+1[]和+1[]，它们可以存在[

5、]和[]先前存放的位置，这种存储位置共享特性通常称为同址计算，明显节省了整个算法的存储要求。返回位倒序位倒序在算法流图中可以看出：DFT样本X[k]在输出端顺序排列时，输入时域样本x[n]不是顺序排列的。位倒序来看下面的流程图:位倒序变量m和n之间关系如下:n:顺序排列m:新顺序nb0b1b2mb2b1b0000000001100010010011110100001101101110011111111若x[n]的长度不是2的幂次,可以通过补零将序列长度延长为2的幂。返回FFT算法编程FFT算法

6、编程观察流程图:FFT算法编程编写FFT程序，必须解决下面问题:位倒序旋转因子蝶形运算返回FFT算法编程位倒序位倒序J=正序00000000序号001002003004000255000001000100000000000000J=000计算JIfJ

7、If(J≥N/4)thenJ=J-N/4If(J

8、t_reversed_orderx=input(‘Typeinthesequence:');N=length(x);M=log2(N);x1=zeros(1,N);x1(1)=x(1);x1(N)=x(N);J=0;forI=1:N-2;k=1;c=0;whilek~=M+1&c~=1;ifJ>=N/(2.^k);J=J-N/(2.^k);c=0;elseJ=J+N/(2.^k);c=1;endk=k+1;endx1(I+1)=x(J+1);end返回F