《数字信号处理DSP_Chapter5_快速傅立叶变换.ppt》由会员分享，可在线阅读，更多相关《数字信号处理DSP_Chapter5_快速傅立叶变换.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数字信号处理数字信号处理DSP_Chapter5_快速快速傅立叶变换傅立叶变换Overview1.DFT的计算2.快速傅立叶变换算法3.短时傅立叶变换DSP:Digital Signal Processing 2页1.DFT的计算由于时域处理更加经济,因此滤波器设计已经转向时域处理.但是频域处理使得有些问题变得更加简单:需要有效的方法来计算DFT.DSP:Digital Signal Processing 3离散傅立叶变换DFT:离散序列的离散变换.矩阵形式:具有许多特殊结构可以设计高效算法.DSP:Digital Signal Processing 4计算复杂性对于每一个点需要N个复数乘法和
2、N-1个复数加法,k=0,1,2,N-1.复数乘法:(a+bj)(c+dj)=(ac-bd)+j(ad+bc)需要4个实数乘法+2个实数加法.复数加法=2 个实数加法.总共需要4N2 个实数乘法和 4N2 2 N 个实数加法.DSP:Digital Signal Processing 5Goertzel 算法把X(k)化为:以上式子具有卷积的形式,令DSP:Digital Signal Processing 6Goertzel 算法因此把X(k)表示为卷积的形式:X(k)=yk(N)而 yk(n)=xe(n)*hk(n)多项式可以表示为DSP:Digital Signal Processing
3、 7Goertzel 算法对于每一个X(k)分别滤波处理:即使只有一些采样点也能计算.不需要很大的缓存和系数表.与完全傅立叶变换有同样的复杂度(4N2 个实数乘法和 4N2 2 N 个实数加法).做乘法时,可以乘以一个实分母的形式:DSP:Digital Signal Processing 82 快速傅立叶变换FFT把DFT的计算复杂度从O(N2)降到O(Nlog2N).当N很大是这两者的复杂度差异就更明显.算法原理是把大的DFT分解成许多小的DFTs.一般使用经过优化了的库函数来实现.DSP:Digital Signal Processing 9Decimation in Time FFT给
4、定序列x(n),0 n N,N=2M i.e.N 以2为基底.把 z变换X(z)分解为奇数部分和偶数部分:序列x(n)中的N/2 个偶数点的 z变换:序列x(n)中的N/2 个奇数点的z变换:DSP:Digital Signal Processing 10时域抽取的FFT算法由于 以及因此 分解成了只有N/2个点列DFT.DSP:Digital Signal Processing 11时域抽取的FFT算法等价于偶数点列的DFT和奇数点列的DFT之和.DSP:Digital Signal Processing 12计算复杂性的初步估计DFTNx(n)=DFTN/2x0(n)+Wk DFTN/2x
5、1(n)我们可以通过估计N/2个点列的DFT的计算复杂性来估计N个点列的DFT的计算复杂性.如果 DFTN O(N2)那么 DFTN/2 O(N/2)2)=1/4 O(N2)总的计算量 21/4O(N2)=直接计算DFT计算量的 1/2.DSP:Digital Signal Processing 13第一级的DIT计算流程图DSP:Digital Signal Processing 14多级DIT算法把一个DFTN分解成两个更小的DFTN/2能加速DFTN的计算速度,因此我们可以考虑把DFTN/2作进一步的分解:其中X00(N/4)为偶数子集合的偶数点DFT,X01(N/4)为奇数点的DFT.
6、DSP:Digital Signal Processing 15两级DIT计算流程图DSP:Digital Signal Processing 16多级DIT快速傅立叶变换按照以上奇偶分解方法把DFTs一直分解到只有两个点的DFTs:N=2 个点的DFT分解为M级蝶形计算流程图.实数乘法 M4N,实数加法 2M2N 复杂性 O(NM)=O(Nlog2N)DSP:Digital Signal Processing 17FFT 实现细节基本的蝶形结:可以化简为:DSP:Digital Signal Processing 188个点列的DIT FFT流程图-1 已经被合并进加法接点.W0N 已经消失
7、内嵌算法:逐级计算.DSP:Digital Signal Processing 19FFT的计算步骤1.全部计算分解为M级.2.把输入序列x(n)的下标0,1,2,3,N-1写成二进制的形式,并且把它进行“码位倒读”,重新按十进制读数,如:3 011 110 6,5 1011015.3.每级迭代都包含N/2个蝶形单元.4.每个蝶形单元都包含Wnk与W-nk 的运算.5.各级W的分布规律.DSP:Digital Signal Processing 20码位倒置输入序列x(n)按照码位倒置存储,输出序列X(k)为正常顺序.Question:输入序列为什么要按照码位倒置的顺序存储,而不是其它顺序?它
8、的本质是由于我们每次要把序列按照奇偶分组引起的.Question:序列x(n)的下标 n=0,1,2,3,2M 1,这N=2M个数我们如何判断它的奇偶性?DSP:Digital Signal Processing 21码位倒置规律偶数:能被2整除的数.把一个非负整数n 表示为二进制的形式:因此非负整数n能被2整除,意味着它的二进制表达式中的末尾系数 c0=0.n不能被2整除意味着它的二进制系数 c0=1.DSP:Digital Signal Processing 22码位倒置规律因此对序列x(n)进行第一次奇偶分组时,变量n的二进制系数c0=0 的都分在偶数组,c0=1的都分在奇数组.第二次奇
9、偶分组的规则是:把奇数序列组和偶数序组重新编号排列:这样新序列的下标 r=n/2,这相当于把下标 n 的二进制数进行向右移动一位.DSP:Digital Signal Processing 23码位倒置规律即 再把奇数序列和偶数序列进行奇偶分组.由于 r的二进制表示与n有相似结构,因此这次的奇偶分组要看下标r的末尾系数c1的值,如果c1=0 则分在偶数组的偶数组或者奇数组的偶数组,否则c1=1分在偶数组的奇数组或者奇数组的奇数组.DSP:Digital Signal Processing 24码位倒置规律利用上述规律递推可得:如果下标 n 的二进制系数ci=0则在第i+1次分组时它应该分在偶数
10、组,ci=1则分在奇数组.由于我们实际计算时,利用了先进后出的堆栈机制,即最先分组的级最后进行奇偶FFT计算,因此经过M-1次分组后,假设 m,n 分在同一组,则它们的二进制表达式为:DSP:Digital Signal Processing 25码位倒置规律即最后分在同一组的最后两个数x(m),x(n),它们的下标m,n 的二进制系数ci 除了最高位系数不同之外,其余位的系数都应该相同.而每两个相邻的自然数n,n+1的二进制数除了最低位不同之外,其余位数都相同,如:0=000,1=001,2=010,3=011,4=100,5=101,6=110,7=111.这样我们只要把顺序自然数0,1,
11、2,.,N-1的二进制数进行码位倒置就可以得到我们所需要的输入序列.DSP:Digital Signal Processing 26系数WrN 的表达式第1级:第2级:第3级:第i级:第M级:DSP:Digital Signal Processing 27 系数WrN的推导由于第一次进行奇偶数分组后的系数W为:第二次进行奇偶分组后的系数W为:第l 次进行奇偶分组后的系数W为:l=1,2,M.DSP:Digital Signal Processing 28系数WrN的推导由于因此第l 次进行奇偶分组后的系数W为:由于我们实际进行运算时,最先分组时产生的系数W最后一级计算时才用到,因此做替换:i=
12、M+1-l,2M=N有DSP:Digital Signal Processing 29蝶形运算两结点间的距离当计算第1级蝶形结时,每个蝶形的结点距离为1;第2级蝶形时,每个蝶形的结点距离为2;第3级蝶形时,每个蝶形的结点距离为4;依此类推,第i级每个蝶形的结点距离为2i-1.因而蝶形结点的递推运算公式为:DSP:Digital Signal Processing 30其它N值的FFTN=2M 意味着我们每次都能把一组数据进行折半分解=“基2-FFT”.还有其它方法:N=3M,基3算法.N=4M,基4算法,是更优化的算法.N=a b c d,混合基算法.可以填充一些零值,使得N=2M.DSP:D
13、igital Signal Processing 31逆FFTIDFT为:因此从而可以利用FFT计算IFFT.DSP:Digital Signal Processing 32实数序列的DFT如果x(n)为实数,在进行DFT时可以节约一些乘法时间.实数x(n)为共扼对称 X(k)=X*(-k)给定两个实数序列x(n),w(n);y(n)=jw(n),v(n)=x(n)+y(n).N点DFT V(k)=X(k)+Y(k),但是:V(k)+V*(-k)=X(k)+X*(-k)+Y(k)+Y*(-k)X(k)=1/2(V(k)+V*(-k),W(k)=-j/2(V(k)-V*(-k)计算两个N点实数序列的DFT等价于计算一个N点DFT.DSP:Digital Signal Processing 33