信号分析及处理15

1、第十章第十章 快速离散傅立叶变换快速离散傅立叶变换 本章的教学内容本章的教学内容 改进改进DFTDFT计算的方法计算的方法 按时间抽取的按时间抽取的FFTFFT算法（算法（DIT FFT） 按频率抽取的按频率抽取的FFTFFT算法（算法（DIF FFT）第第十章章 快速离散傅立叶变换快速离散傅立叶变换 （1） FFT:Fast Fourier Transform（2）傅立叶级数和傅立叶变换理论在19世纪就已经提出,时域离散傅立叶变换理论也在20世纪初发展完善.但由于其手工计算的复杂性,在工程实践中并没有得到广泛应用.相反,在应用中使用广泛的是其它一些手工计算相对简单的数学分析手段,如沃尔什变换

2、.直到1965年, 库利-图基提出了针对N时复合数情况的快速离散傅立叶变换算法,与传统算法相比降低了1个数量级,由此引发了研究快速算法的热潮.这些算法统称为FFT. FFT算法的广泛应用，不仅奠定了离散傅立叶变换在数字信号处理中的经典地位,也极大推动了数字信号处理应用与发展.第一节第一节 改进改进DFT计算的方法计算的方法衡量算法的复杂性: 乘.加法运算次数,不考虑控制调度等操作;只考虑DFT的正变换,因为:10( )( )NknNnX kx n W K=0,1, ,N-1 DFT正变换110011( )( )( )NNknknNNkkx nX k WXk WNNDFT反变换反变换相对正变换:

3、输入取共扼;输出取共轭并加权.直接计算直接计算DFT的运算量的运算量( )x n n=0,1, ,N-1 10()( )NknNnXkx n W k=0,N-1复数运算复数运算 对每一个对每一个k值值: 复乘复乘: N 复加: N-1第一节第一节 改进改进DFT计算的方法计算的方法 对所有对所有k: 复乘复乘: 复加复加: N(N-1)即复数运算量与即复数运算量与 近似成正比近似成正比(不考虑 情况) 2N2N01NW 实数运算10( )Re( )Im( )ReImNknknNNnX kx njx nWjW1100Re( ) ReIm( ) ImNNknknNNnnx nWx nW1100Re

4、( ) ImIm( ) ReNNknknNNnnjx nWx nW k=0,N-1第一节第一节 改进改进DFT计计算的方法算的方法对每一个固定对每一个固定k : 实乘实乘: 4N 实加实加: 2(1) 1242NN对所有对所有k : 实乘实乘: 4N2实加实加: 2N(2N-1)= 4N2 -2N实数运算量与实数运算量与2N近似成正比近似成正比 结论结论:直接计算直接计算DFT的乘的乘.加运算量近似与加运算量近似与 成正比成正比.第一节第一节 改进改进DFT计算的方法计算的方法2N改善运算效率的途径改善运算效率的途径（1）利用）利用 的对称性和周期性等特性合并运算项的对称性和周期性等特性合并运

5、算项复共轭对称性复共轭对称性: 对对n和和k的周期性的周期性: 可约性可约性 特殊值特殊值knNW()k N nknknNNNWWW()()knk n Nk N nNNNWWW第一节第一节 改进改进DFT计算的方法计算的方法11/rNN rMWWW/20/2/4 1 1 kNkNNNNNNNWWWWWj NrM式中其它各对称项也可以找到类似归并办法式中其它各对称项也可以找到类似归并办法. .这样乘法这样乘法次数大约可减少一半次数大约可减少一半. .(2) (2) 大点数大点数DFTDFT逐次分解成小点数逐次分解成小点数DFT)DFT)分解分解 正是正是FFTFFT算法的基本原理算法的基本原理

6、Re( )Re()ReknNx nx NnWImIm( )Im()knNWx nx Nn 1222122NNNNNN第一节第一节 改进改进DFT计算的方法计算的方法例:利用对称性,可以合并对称项:()Re( ) ReRe() ReReknk NnknNNNx nWx NnWW()Im( ) ImIm() Imknk N nNNx nWx NnWFFT的基本原理： 为了提高DFT的运算效率, 把大点数DFT按倒位序逐次分解为更小点数DFT的合成.在分解过程中,要利用系数 的对称性和周期性. 如果算法是逐次分解时间序列得到的,那么这种分解算法称为按时间抽取算法.阐述按时间抽取原理最方便的方法是研究

7、 这种特殊情况.由于N为2的整数幂,可以不断将x(n)一分为二. 这就是最常用的基-2FFT算法. 如果序列不满足这个条件,可以人为地加上若干零点得到.knNW2mN 第一节第一节 改进改进DFT计算的方法计算的方法第二节第二节 按时间抽取按时间抽取FFTFFT算法算法算法原理：假设序列x(n)长为 (n=0,N-1), 由于N为 偶数,可以将x(n)按n为奇数和偶数分解为两个 N/2的长序列,并依此逐级分解来计算x(k).2mN 120,1,1(2 )( )2(21)( )0,1,12Nrxrx rxrx rNr是x(n)按n为奇、偶数分为2个子序列，得:第二节第二节 按时间抽取按时间抽取F

8、FTFFT算法算法第一级分解定义偶序列与奇序列:( )( )( )knknNNnnX kx n Wx n W为偶数为奇数11222(21)00(2 )(21)NNknkrNNrrxr WxrW1122221200( )( )NNkrkrkNNNrrx rWx rWW222221/2NjjNNNWeeW上式可写为:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 2211221200( )( )( )NNNNkrkrkNrrX kx rWx rWW12( )( )kNX kW Xk其中: 2211221100( )( )(2 )NNNNkrkrrrX kx rxrWW k=0,N/2-1

9、第二节第二节 按时间抽取按时间抽取FFT算法算法上式表明一个N点的DFT可以分解成两个 点的DFT. 这两个 点的DFT又可按式合成一个N点DFT一个问题: 和 的长度为 , 它们的DFT 和 的点数也为 , 而x(k)却有N个点。 利用 的周期性解决这一问题，即：/2N1( )x r2( )x r1( )X k2( )X kkNW/2/2k NNkkNNNNWWWW 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法/2N/2N/2N/ 2/ 2/2 1/2 1/2111100(/2)( )( )( )NNNNkNrkrrrX kNx rWx rWX k22()( )2NXkXk表达为前

10、后两个部分:( )X k前半部分 012( )( )( )kNXkX kW Xk后半部分 12(/2)( )( )kNX kNX kW Xk k=0, k=0, /2 1N1( )X k和2( )Xk的周期为/2N同样可得把即：/2 1N第二节第二节 按时间抽取按时间抽取FFTFFT算法算法这样只要求出0 -1 区间所有 和 ,就可以求出0N-1 区间内全部X(k)的值.这就是FFT运算的关键所在。用以下信号流图表示为：1( )X k2( )Xk/2N根据流图的形状，上述运算称为碟形运算。第二节第二节 按时间抽取按时间抽取FFTFFT算法算法复乘: 1 复加: 2一次蝶形运算: 运算分析:当3

11、28N 一次分解后DFT运算的信号流图为：第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 仍为偶数,可以2N NNN2(1)22222 直接计算N点DFT所需复乘 ,复加N(N-1),可见当2N N较大时,一次分解后运算量减少近一半. 由于 N= 2M(M1), 经一次分解后 N2N2 点DFT再分别分解为两个 点DFT的组合.进一步把每个N2复乘: 2NNN(N 1)21222 一次分解: 2个 N2点DFT+ 个蝶形运算N2 复加: 第二节第二节 按时间抽取按时间抽取FFT算法算法第二级分解1( )x r1314(2 )( )0,14(21)( )xlx lNlxlx l可得: 2

12、2112(21)4411100( )(2 )(21)NNNNkrklllX kxlxlWW第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 与第一级分解一样,利用 和 隐含的周期性, 为 改写为前，后两部分: 234( )( )NkXkXkW0,12Nk 其中: 414330( )( )NNkllXkx lW0,14Nk 414440( )( )NNkllXkx lW0,14Nk 3(k)X4(k)X1( )X k第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 2134( )( )( )NkX kXkW kW0,14Nk N2k134()(k)( )4NX kXXkW0,14Nk

13、 由此一个 N4点DFT分解成两个 N2 点的DFT.其流图为:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法2( )Xk也可以进行同样分解:2526(2 )( )0,14(21)( )xlx lNlxlx l第二节第二节 按时间抽取按时间抽取FFTFFT算法算法奇序列中的偶序列,奇序列中的奇序列 22112(21)4422200( )(2 )(21)NNNNkrklllXkxlxlWW 42411445600( )( )NNNNNkrkklllx lx lWWW 256( )( )NkXkXkW0,12Nk 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法414550( )(

14、)NNkllXkx l W0,14Nk 414660( )( )NNkllXkx l W0,14Nk 为 2( )Xk改写为前,后两部分: N2256( )(k)(k)kXkXWX0,14Nk 2256()( )( )4NkNXkXkWXk0,14Nk 第二节第二节 按时间抽取按时间抽取FFTFFT算法算法其中:系数统一为 (今后都使用统一的系数),这样,N22kkNWW一个N点DFT就分解成4个N/4点的DFT,其信号流图为:第二节第二节 按时间抽取按时间抽取FFTFFT算法算法根据前面的分析,第二级分解组合比第一级分解后的运算量又降低了一半.对于N=8点的DFT,经过两次分解后,最后剩下四

15、个N/4=2 的DFT,即 3456( )( ),( )( )Xk XkXkXk和(k =0,1).尽管2点长的DFT只有加减法,仍然可用蝶式运算单元来统一表示.第二节第二节 按时间抽取按时间抽取FFTFFT算法算法例如 组成的2点DFT 可用公式计算: 类似,其它3个2点长DFT都可以用一个蝶式运算单元求得,综合这三级分解过程,可得到一个完整的8点DFT信号流图.4( )Xk410444(0)(0)(1)(2)(6)(2)(6)NNXxW xxxxW x410444(1)(0)(1)(2)(6)(2)(6)NNXxW xxxxW x(2), (6)xx第二节第二节 按时间抽取按时间抽取FFT

16、FFT算法算法第二节第二节 按时间抽取按时间抽取FFTFFT算法算法这种方法每次分解都是按输入序列在时域上的次序是偶数还是奇数来抽取的，故称之为按时间抽取法.运算量分析由DIT FFT信号流图可见,对于任何一个 点DFT运算,都可以通过M次分解,最后分解成2点DFT运算的组合.这样的M级分解,就构成了M级运算过程.每级N/2个蝶形运算.每一级: 复乘: 复加: 2MN 122NN 22NN第二节第二节 按时间抽取按时间抽取FFTFFT算法算法结论: DIF FFT运算量与 近似成正比.全部M级:复乘 复加 2NNlog22pmMN2logpaNMNN第二节第二节 按时间抽取按时间抽取FFTFF

17、T算法算法2logNN第二节第二节 按时间抽取按时间抽取FFTFFT算法算法三. 按时间抽取的FFT算法特点.1. 蝶式运算 系统由大量蝶式运算单元组成,每个蝶式运算的迭代任务是:11( )( )( )rmmNmXpXpW Xq11( )( )( )rmmNmXqXpW Xq1mM 为节点，m：表示第m列叠代。p,q：为数据所在行数，对应信号流图下图所示：01pqN( )( )mmXp Xq第二节第二节 按时间抽取按时间抽取FFT算法算法00( ),( )XpXq是输入数据注：第二节第二节 按时间抽取按时间抽取FFTFFT算法算法（1）蝶式运算的节点距离 (p,q间的距离)以N=8为例m 1

18、2 3q-p 1 2 4推广:基-2 DIF FFT中,第m级蝶式运算节点间距离为12m蝶式运算可写成:111( )( )(2)rmmmNmXpXpW XprNW（2） 的确定每一级的旋转因子都不相同，但排列很有规律，下表所示。第二节第二节 按时间抽取按时间抽取FFTFFT算法算法rNW2. 原址运算第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 多级蝶式运算结构会产生大量中间结果.如果运算式要保存这些中间结果,则需要耗费大量资源(存贮器)观察FFT信号流图,可以发现任何两个节点(p与q)经过蝶式运算后,其结果即为下一列p,q两节点的变量.而每一级蝶式运算的输出,在该级运算结束之后无需

19、保存.因此,任何一个蝶行运算的两个输出结果仍然可以存放两个输入值所在的存储单元中.这样,整个运算只需要N个寄存器,他们保存输入数据,并不断对每一级运算结果刷新,直到最后输出。其优点在于节省存储资源.第二节第二节 按时间抽取按时间抽取FFT算法算法3. 倒位序 观察同址运算结构,可以发现FFT输出端X(k)正好按07自然顺序排列的，而输出序列x(n)不是按07自然顺序排列。x(n)排列表面上混乱无序，而隐含着有规律的排列，即”倒位序”存贮,以N=8点FFT结构来说明。存储器号 数据22222222222222220(000)(000)(0)1(001)(100)(4)2(010)(010)(2)

20、3(011)(110)(6)4(100)(001)(1)5(101)(101)(5)6(110)(011)(3)7(111)(111)(7)xxxxxxxxxxxxxxxx结论: 21020122()()n n nx n n n第二节第二节 按时间抽取按时间抽取FFTFFT算法算法倒位序排列是由于不断将DFT运算分解为较小点数DFT计算造成的。序列x(n)首先分成偶数标号和奇数标号两个子序列：偶数序列出现在流图上半部,奇数序列出现在流图下半部。从形式上说,这样的划分可通过分析标号n的二进制表示 的最低位 来实现。标号为偶数，则 =0，标号为奇数，则 =1。这样 =0的标号出现在流图上半部2 1

21、020 122x( )()()nx n n nn n n 存储2 1 0 2()n nn0n从中我们可以发现: 若 2 102()nn nn, 则: 0n0n0n第二节第二节 按时间抽取按时间抽取FFTFFT算法算法 =1的标号出现在下半部。下一次奇偶序列的分解又分别根据标号二进制表示的倒数第二位 开始,根据 分别将第一次分解生成的两个子序列再一次按奇偶性分开。持续该过程,直得到N个长度为1的子序列。最后的排列顺序呈”倒位序”0n1n1n第二节第二节 按时间抽取按时间抽取FFTFFT算法算法所以要实现FFT算法，首先必须把按自然顺序存放的数据变换成按倒序存放。这一过程称为整序，N=8时的整序过

22、程下图所示。第二节第二节 按时间抽取按时间抽取FFTFFT算法算法小结:1. 算法原理2. 计算量: 复乘:复加:3. 运算特点:蝶式运算.同址运算.倒位序2log2NN2logNN第二节第二节 按时间抽取按时间抽取FFTFFT算法算法第三节第三节 按频率抽取按频率抽取FFTFFT算法算法DIT:将输入序列x(n)按其标号n为奇数或偶数分解成短序列DIF:将输出序列X(k)按其k值为奇数或偶数分解成短序列算法原理仍讨论基-2FFT,即 频域抽取法是将X(k)按标号k的自然顺序分成前后两半(注意:不再是奇偶顺序)2MN 1/2 1100/2( )( )( )( )NNNknknknNNNnnn

23、NX kx n Wx n Wx n W/2 1/2 1(/2)00( )(/2)NNknk n NNNnnx n Wx nNW/2 1/20/2 10( )(/2)( )( 1)(/2)NkNknNNnNkknNnx nWx nNWx nx nNW 第三节第三节 按频率抽取按频率抽取FFTFFT算法算法/2 120( )(2 )( )(/2)NrnNnX kXrx nx nNW/2 1/20( )(/2)NrnNnx nx nNW/2 1(21)0( )(21)( )(/2)NrnNnX kXrx nx nNW按k为偶数或是奇数将x(k)分解成两部分2 ,0,1,.,/2 1kr rN21,0,1,.,/2 1krrN/2 1/20( )(/2)NnrnNNnx nx nNWW第三节第三节 按频率抽取按频率抽取FFTFFT算法算法输入序列前一半与后一半之差再与 乘积nNW1( )( )()2Nx nx nx n2( )( )()2nNNx nx nx nW令输入序列前一半与后一半之和0,12Nn 0,12Nn 第三节第三节 按频率抽取按频率抽取FFTFFT算法算法1210212202(2 )( )0,1 2(21)( )NrnNnNnrNnXr