数字信号处理程佩青件快速傅里叶变换.pptx

《数字信号处理程佩青件快速傅里叶变换.pptx》由会员分享，可在线阅读，更多相关《数字信号处理程佩青件快速傅里叶变换.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主要内容DIT-FFT算法 DIF-FFT算法IFFT算法Chirp-FFT算法线性卷积的FFT算法第1页/共63页4.1 引言FFT:Fast Fourier Transform1965年，Cooley-Turky 发表文章机器计算傅里叶级数的一种算法，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。FFT的应用。频谱分析、滤波器实现、实时信号处理等。DSP芯片实现。TI公司的TMS 320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。第2页/共63页典型应用：信号频谱计算、系统分析等 系统分析系统分析 频谱分析与功率谱计算频谱分析与功率谱计算第3页/共6

2、3页4.2 直接计算DFT的问题及改进途径1、DFT与与IDFT第4页/共63页2、DFT与与IDFT运算特点运算特点复数乘法复数乘法复数加法复数加法一个一个X(k)NN 1N个个X(k)(N点点DFT)N 2N(N 1)同理：同理：IDFT运算量与运算量与DFT相同。相同。实数乘法实数乘法实数加法实数加法一次复乘一次复乘42一次复加一次复加2一个一个X(k)4N2N+2(N 1)=2(2N 1)N个个X(k)(N点点DFT)4N 22N(2N 1)第5页/共63页3、降低DFT运算量的考虑第6页/共63页FFT算法分类算法分类:q时间抽选法时间抽选法DIT:Decimation-In-Tim

3、eq频率抽选法频率抽选法DIF:Decimation-In-Frequency第7页/共63页4.3 按时间抽取（DIT）的FFT算法（Decimation In Time）1、算法原理设序列点数 N=2L，L 为整数。若不满足，则补零将序列将序列x(n)按按n的奇偶分成两组：的奇偶分成两组：N为为2的整数幂的的整数幂的FFT算法称算法称基基-2FFT算法算法。第8页/共63页将N点DFT定义式分解为两个长度为N/2的DFT记：记：（1 1）（这一步利用：（这一步利用：）第9页/共63页再利用周期性求再利用周期性求X(k)的后半部分的后半部分第10页/共63页将上式表达的运算用一个专用“蝶形”

4、信流图表示。注：注：a.上支路为加法，下支路为减法；上支路为加法，下支路为减法；b.乘法运算的支路标箭头和系数。乘法运算的支路标箭头和系数。第11页/共63页用“蝶形结”表示上面运算的分解：第12页/共63页分解后的运算量：分解后的运算量：复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计运算量减少了近一半运算量减少了近一半第13页/共63页进一步分解进一步分解由于由于 ，仍为偶数，因此，两个仍为偶数，因此，两个 点点DFTDFT又可同样进一步分解为又可同

5、样进一步分解为4 4个个 点的点的DFTDFT。第14页/共63页“蝶形蝶形”信流图表示信流图表示 第15页/共63页N点DFT分解为四个N/4点的DFT第16页/共63页类似的分解一直继续下去，直到分解为最后的两类蝶形运算为止(2点DFT).如上述N=8=23，N/4=2点中：类似进一步分解1点DFTx(0)1点DFTx(4)X3(0)X3(1)第17页/共63页进一步简化为蝶形流图：进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)因此因此8 8点点FFTFFT时间抽取方法的信流图如下时间抽取方法的信流图如下第18页/共63页第19页/共63页FFT运算量与运算特点 1 N=2L时

6、，共有L=log2N级运算；每一级有N/2个蝶形结。2每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N 次复乘法；复加法L*N=Nlog2N 次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当 N大时，此倍数很大。第20页/共63页比较比较DFT 参考P150 表4-1 图4-6可以直观看出，当点数N越大时，FFT的优点更突出。第21页/共63页按时间抽取FFT蝶形运算特点 1、关于FFT运算的混序与顺序处理（位倒序处理）由于输入序列按时间序位的奇

7、偶抽取，故输入序列是混序的，为此需要先进行混序处理。混序规律：x(n)按n位置进行码位（二进制）倒置规律输入，而非自然排序，即得到混序排列。所以称为位倒序处理。位倒序实现：（1）DSP实现采用位倒序寻址（2）通用计算机实现可以有两个方法：一是严格按照位倒序含义进行；二是倒进位的加N/2。第22页/共63页倒位序倒位序自然序自然序0000000010041001010220101106301100114100101551010113611011177111倒位序倒位序第23页/共63页第24页/共63页例计算 ，。计算 点FFT。用时间抽取输入倒序算法，问倒序前寄存器的数 和倒序后 的数据值？解

8、：倒序前解：倒序前 倒序倒序 倒序为倒序为 倒序后倒序后 第25页/共63页DIT FFT中最主要的蝶形运算实现（1）参与蝶形运算的两类结点（信号）间“距离”（码地址）与其所处的第几级蝶形有关；第m级的“结距离”为 (即原位计算迭代）（2）每级迭形结构为第26页/共63页q 蝶形运算两节点的第一个节点为蝶形运算两节点的第一个节点为k值，表值，表示成示成L位二进制数，左移位二进制数，左移L m位，把右边位，把右边空出的位置补零，结果为空出的位置补零，结果为r的二进制数。的二进制数。（3）的确定：的确定：第第m级的级的r取值：取值：第27页/共63页DIT算法的其他形式流图输入倒位序输出自然序输入

9、自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序参考P154-155第28页/共63页时间抽取、时间抽取、输入自然顺序、输入自然顺序、输出倒位序的输出倒位序的FFTFFT流图流图 第29页/共63页 例 用FFT算法处理一幅NN点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解 当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为 次，仅为直接计算DFT所需时间的10万分之一。即原需要3000小时，现在只需要2 分钟。第30页/共63页4.4 按频率抽取（DIF）的FFT算法与DIT-FF

10、T算法类似分解，但是抽取的是X(k)。即分解X(k)成奇数与偶数序号的两个序列。设：N=2L，L 为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：（Decimation In Frequency)一、算法原理一、算法原理第31页/共63页第32页/共63页下面讨论按按k k的奇偶将的奇偶将X(k)X(k)分成两部分：分成两部分：显然：显然：第33页/共63页令：令：用蝶型结构图表示为：用蝶型结构图表示为：第34页/共63页x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1

11、)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)第35页/共63页N/2仍为偶数，进一步分解：仍为偶数，进一步分解：N/2 N/4第36页/共63页x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)q按照以上思路继续分解，即一个按照以上思路继续分解，即

12、一个N/2的的DFT分解成两个分解成两个N/4点点DFT，直到只计算，直到只计算2点的点的DFT，这就是，这就是DIF-FFT算法。算法。第37页/共63页2个个1点的点的DFT蝶形流图蝶形流图 进一步简化为蝶形流图：1点DFTx3(0)1点DFTx3(1)X(0)X(4)X(0)X(4)x3(0)x3(1)第38页/共63页第39页/共63页二、按频率抽取FFT蝶形运算特点1）原位计算-1L级蝶形运算，每级级蝶形运算，每级N/2个蝶形，每个蝶形结构：个蝶形，每个蝶形结构：m表示第表示第m级迭代，级迭代，k，j表示数据所在的行数表示数据所在的行数第40页/共63页2）蝶形运算）蝶形运算对对N=

13、2L点点FFT，输入自然序，输出倒位序，输入自然序，输出倒位序，两节点距离：两节点距离：2L-m=N/2m第第m级运算：级运算：第41页/共63页q 蝶形运算两节点的第一个节点为蝶形运算两节点的第一个节点为k值，表示成值，表示成L位二进制数，左移位二进制数，左移m-1位，把右边空出的位位，把右边空出的位置补零，结果为置补零，结果为r的二进制数。的二进制数。存储单元存储单元输入序列输入序列x(n):N个存储单元个存储单元系数系数 ：N/2个存储单元个存储单元第42页/共63页三、三、DIT与与DIF的异同的异同q基本蝶形不同基本蝶形不同qDIT:先复乘后加减先复乘后加减qDIF:先减后复乘先减后

14、复乘q运算量相同运算量相同q都可原位运算都可原位运算qDIT和和DIF的基本蝶形互为转置的基本蝶形互为转置第43页/共63页4.5 IDFT的FFT算法（FFT应用一）一、从定义比较分析与与DFT的比较：的比较：1）、旋转因子）、旋转因子WN-kn 的不同；的不同；2）、结果还要乘）、结果还要乘 1/N。第44页/共63页二、实现算法二、实现算法直接使用直接使用FFT程序的算法程序的算法共轭FFT共轭乘1/N直接调用FFT子程序计算IFFT的方法：第45页/共63页4.6 线性调频Z变换（Chirp-Z变换）算法（FFT应用二）单位圆与非单位圆采样（a）沿单位圆采样;(b)沿AB弧采样 第46

15、页/共63页 螺线采样螺线采样 zk=AW-k k=0,1,M-1 第47页/共63页Chirp-Z变换的线性系统表示 由于系统的单位脉冲响应由于系统的单位脉冲响应 可以想象为频率可以想象为频率随时间随时间(n)(n)呈线性增长的复指数序列。在雷达系统中呈线性增长的复指数序列。在雷达系统中,这这种信号称为种信号称为线性调频信号（线性调频信号（Chirp SignalChirp Signal），因此，这，因此，这里的变换称为里的变换称为线性调频线性调频Z Z变换变换。第48页/共63页一、基本算法思路一、基本算法思路4.7 线性卷积的FFT算法（FFT应用三）若若L点点x(n)，M点点h(n)，

16、则直接计算其线性卷积则直接计算其线性卷积y(n)需运算量：需运算量：若系统满足线性相位，即：若系统满足线性相位，即：则需运算量：则需运算量：第49页/共63页FFT法：以圆周卷积代替线性卷积法：以圆周卷积代替线性卷积N总运算量：总运算量：次乘法次乘法第50页/共63页比较直接计算和比较直接计算和FFT法计算的运算量法计算的运算量讨论：讨论：1）当）当2）当）当第51页/共63页 x(n)长长度度很很长长时时，将将x(n)分分为为L长长的的若若干干小的片段，小的片段，L与与M可比拟。可比拟。1 1、重叠相加法、重叠相加法 则：则：输出：输出：第52页/共63页其中：其中：可以用圆周卷积计算：可以

17、用圆周卷积计算：选选 ，上面圆周卷积可用，上面圆周卷积可用FFTFFT计算。计算。N 由于由于yi(n)长度为长度为N，而，而xi(n)长度长度L，必有，必有M-1点重叠，点重叠，yi(n)应相加才能构成最后应相加才能构成最后y(n)的。的。第53页/共63页重叠相加法图形重叠相加法图形第54页/共63页第55页/共63页和上面的讨论一样，用FFT法实现重叠相加法的步骤如下:计算N点FFT，H(k)=DFTh(n)；计算N点FFT，Xi(k)=DFTxi(n)；相乘，Yi(k)=Xi(k)H(k)；计算N点IFFT，yi(n)=IDFTYi(k)；将各段yi(n)（包括重叠部分）相加，。重叠相

18、加的名称是由于各输出段的重叠部分相加而得名的。第56页/共63页例例 已知序列已知序列xn=n+2,0 n 12,hn=1,2,1试试利用重叠相加法计算线性卷积利用重叠相加法计算线性卷积,取取L=5。yn=2,7,12,16,20,24,28,32,36,40,44,48,52,41,14解解:重叠相加法重叠相加法x1n=2,3,4,5,6x2n=7,8,9,10,11x3n=12,13,14y1n=2,7,12,16,20,17,6y2n=7,22,32,36,40,32,11y3n=12,37,52,41,14第57页/共63页2 2、重叠保存法此方法与上述方法稍有不同。先将x(n)分段，

19、每段L=N-M+1个点，这是相同的。不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值，组成L+M-1点序列xi(n)。如果L+M-12m，则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。第58页/共63页重叠保留法示意图第59页/共63页重叠保留法示意图第60页/共63页yk=2,7,12,16,20,24,28,32,36,40,44,48,52,41,14x1k=0,0,2,3,4x2k=3,4,5,6,7x3k=6,7,8,9,10

20、y1k=x1k hk=11,4,2,7,12x4k=9,10,11,12,13y2k=x2k hk=23,17,16,20,24y3k=x3k hk=35,29,28,32,36y4k=x4k hk=47,41,40,44,48x5k=12,13,14,0,0y5k=x5k hk=12,37,52,41,14解解:重叠保留法重叠保留法例例 已知序列已知序列xn=n+2,0 n 12,hn=1,2,1试试利用重叠利用重叠保留法保留法计算线性卷积计算线性卷积,取取L=5。第61页/共63页语音信号消噪过程语音信号消噪过程(a)信号淹没在啸叫噪声中；信号淹没在啸叫噪声中；(b)信号与噪声的功率谱；信号与噪声的功率谱；(c)去噪后的功率谱；去噪后的功率谱；(d)重构原语音信号重构原语音信号FFT应用举例应用举例第62页/共63页感谢您的观看。第63页/共63页