快速傅里叶变换优秀PPT.ppt

《快速傅里叶变换优秀PPT.ppt》由会员分享，可在线阅读，更多相关《快速傅里叶变换优秀PPT.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、快速傅里叶变换你现在浏览的是第一页，共47页1.1.引言引言FFTFFT不是一种新算法不是一种新算法,只是只是DFTDFT的一种快速算法。的一种快速算法。CooleyCooley和和TukeyTukey在在19651965年发表的年发表的“机器计算傅里叶级机器计算傅里叶级数的一种算法数的一种算法”桑德和图基的快速算法的出现。桑德和图基的快速算法的出现。你现在浏览的是第二页，共47页2.2.直接计算直接计算DFTDFT的问题及改进的途径的问题及改进的途径DFTDFT和和IDFTIDFT的变换公式的变换公式二者的差别就在于二者的差别就在于W WN N的指数符号不同，以及相差一个的指数符号不同，以及

2、相差一个常数乘因子常数乘因子1/N1/N。每计算一个每计算一个X(k)X(k)值，需要值，需要N N次复数乘法，以及（次复数乘法，以及（N-1N-1）次复数加法，而次复数加法，而X(k)X(k)一共有一共有N N个值点，因此完成整个个值点，因此完成整个DFTDFT运算总共需要运算总共需要N N2 2次复数乘法，次复数乘法，N N（N-1N-1）次复数加）次复数加法。法。(4.1)(4.1)(4.2)(4.2)你现在浏览的是第三页，共47页复数运算实际上是由实数运算来完成的，复数运算实际上是由实数运算来完成的，因此因此(4.1)(4.1)式可写成式可写成可以看出，一次复数乘法需要可以看出，一次复

3、数乘法需要4 4次实数乘法和次实数乘法和2 2次实数次实数加法，一次复数加法需要加法，一次复数加法需要2 2次实数加法。次实数加法。因此，每计算一个因此，每计算一个X(k)X(k)值，需要值，需要4N4N次实数乘法，以及次实数乘法，以及2N2N2 2（N-1N-1）2 2（2N2N1 1）次实数加法，整个）次实数加法，整个DFTDFT运运算总共需要算总共需要4N4N2 2次实数乘法，次实数乘法，2N2N（2N-12N-1）次实数加法。）次实数加法。(4.3)你现在浏览的是第四页，共47页存在问题：存在问题：直接计算直接计算DFTDFT，乘法次数和加法次数都是和，乘法次数和加法次数都是和N N2

4、 2成正比。成正比。当当N N很大时，运算量很大，例如，很大时，运算量很大，例如，N=8N=8时，需要时，需要6464次复次复乘，乘，N N10241024时，需要时，需要10485761048576次复乘。次复乘。你现在浏览的是第五页，共47页减少减少DFTDFT运算工作量的途径：运算工作量的途径：利用利用W WN Nnknk的固有特性。的固有特性。（1 1）W WN Nnknk的对称性：的对称性：（2 2）W WN Nnknk的周期性：的周期性：（3 3）W WN Nnknk的可约性：的可约性：可以得出可以得出实际办法：实际办法：（1 1）用上述特性对项合并）用上述特性对项合并（2 2）将

5、长序列的）将长序列的DFTDFT分解为短序列的分解为短序列的DFTDFT，减小，减小N N值。值。你现在浏览的是第六页，共47页对称性与周期性对称性与周期性你现在浏览的是第七页，共47页四点的四点的DFTDFT进行化简，得进行化简，得你现在浏览的是第八页，共47页将该矩阵的第二列和第三列交换，得将该矩阵的第二列和第三列交换，得由此得出由此得出你现在浏览的是第九页，共47页 快速傅里叶变换正是基于这样的思想发展快速傅里叶变换正是基于这样的思想发展进来的，主要分为两大类：进来的，主要分为两大类：DITDIT：按时间抽选：按时间抽选DIFDIF：按频率抽选：按频率抽选你现在浏览的是第十页，共47页3

6、.3.按时间抽选的基按时间抽选的基2FFT2FFT算法算法3.13.1算法原理算法原理先设序列点数为，按先设序列点数为，按n n的奇偶进行分解的奇偶进行分解将将DFTDFT化为化为你现在浏览的是第十一页，共47页利用系数的可约性，即利用系数的可约性，即得得(4.5)(4.6)(4.7)你现在浏览的是第十二页，共47页应用系数的周期性应用系数的周期性,可得可得再考虑性质再考虑性质把把(4.8),(4.9),(4.10)代入代入(4.5)式，将式，将X(k)X(k)表达成表达成前后两部分，前部分为前后两部分，前部分为后部分为后部分为(4.8)(4.9)(4.10)(4.11)(4.12)你现在浏览

7、的是第十三页，共47页 这样，这样，4.114.11、1212式只要式只要0-(N/2-1)0-(N/2-1)区间的所有区间的所有X X1 1(k)(k)和和X X2 2(k)(k)的值，即可求的值，即可求0 0到到(N-1)(N-1)区间所有区间所有X(k)X(k)值。值。4.114.11和和4.124.12式用蝶形图表示。式用蝶形图表示。你现在浏览的是第十四页，共47页N N8 8的情况如图所示的情况如图所示:你现在浏览的是第十五页，共47页 分析：分析：每个蝶形运算需要一次复数乘法每个蝶形运算需要一次复数乘法及两次复数加（减）法。通过分解后运算工作量差不及两次复数加（减）法。通过分解后运

8、算工作量差不多减少到一半。多减少到一半。你现在浏览的是第十六页，共47页进一步把进一步把N/2N/2点子序列再按奇偶部分分解为两个点子序列再按奇偶部分分解为两个N/4N/4点点的子序列的子序列且且其中其中你现在浏览的是第十七页，共47页图图4 43 3，给出，给出N N8 8时，在分解为两个时，在分解为两个N/4N/4点点DFTDFT，由，由两个两个N/4N/4点点DFTDFT组合成组合成N/2N/2点点DFTDFT的流图。的流图。你现在浏览的是第十八页，共47页X X2 2(k)(k)也可进行同样分解：也可进行同样分解：其中其中你现在浏览的是第十九页，共47页一个一个N N8 8点点DFTD

9、FT就可分解为四个就可分解为四个N/4N/42 2点点DFTDFT如图如图你现在浏览的是第二十页，共47页序列按奇偶分解标号变化讨论（序列按奇偶分解标号变化讨论（N N8 8）1 1、第一次分解：两个、第一次分解：两个N/2N/2点序列：点序列：你现在浏览的是第二十一页，共47页2 2、第二次分解，每个、第二次分解，每个N/2N/2点子序列按其奇偶分解为两点子序列按其奇偶分解为两个个N/4N/4点子序列点子序列你现在浏览的是第二十二页，共47页3 3、最后是、最后是2 2点的点的DFTDFT 对于例子对于例子N N8 8，就是，就是4 4个个N/4N/42 2点的点的DFTDFT。如：如：其中

10、其中这种方法的每一步分解都是按输入序列在时间上的次序是属于偶这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数还是属于奇数来分解为两个更短的子序列，所以称为数还是属于奇数来分解为两个更短的子序列，所以称为“按时间按时间抽选法抽选法”。你现在浏览的是第二十三页，共47页3.2 3.2 运算量分析运算量分析（1 1）直接）直接DFTDFT复数算法次数是复数算法次数是N N2 2（2 2）FFTFFT复数乘法次数是（复数乘法次数是（N/2N/2）*L L 当当N=2N=2L L时，一共有时，一共有L L级蝶形，每级有级蝶形，每级有N/2N/2个蝶形运算组个蝶形运算组成，一个蝶形运算有成，一个

11、蝶形运算有1 1次复乘，次复乘，2 2次复加运算。次复加运算。DFTDFT和和FFTFFT算法的计算量之比为算法的计算量之比为结论：结论：FFTFFT比比DFTDFT更优越，当更优越，当N N越大时，优点更明显。越大时，优点更明显。你现在浏览的是第二十四页，共47页你现在浏览的是第二十五页，共47页你现在浏览的是第二十六页，共47页3.3 3.3 按时间抽选的按时间抽选的FFTFFT算法特点算法特点1.1.原位运算原位运算 每个蝶形结构完成下述基本迭代运算：每个蝶形结构完成下述基本迭代运算：4.214.21的蝶形运算如图的蝶形运算如图4 47 7所示。所示。你现在浏览的是第二十七页，共47页

12、蝶形的两个蝶形的两个输出值输出值仍仍放回放回蝶形的两个蝶形的两个输入值所在输入值所在的存储器的存储器中，中间不需要其他的存储器。每列的中，中间不需要其他的存储器。每列的N/2N/2个蝶形运算完成后，再开始下一列的蝶形运算，这样个蝶形运算完成后，再开始下一列的蝶形运算，这样存储数据就只要存储数据就只要N N个存储单元。个存储单元。下一级的蝶形运算仍采取这样的原位运算，只不下一级的蝶形运算仍采取这样的原位运算，只不过进入蝶形的组合关系有所不同。过进入蝶形的组合关系有所不同。你现在浏览的是第二十八页，共47页2.2.倒位序规律倒位序规律你现在浏览的是第二十九页，共47页3.3.倒位序的实现：通过变址

13、运算完成倒位序的实现：通过变址运算完成你现在浏览的是第三十页，共47页4.4.存储单元存储单元输入序列输入序列N N个单元个单元系数系数N/2N/2个单元个单元你现在浏览的是第三十一页，共47页3.43.4按时间抽选的按时间抽选的FFTFFT算法的其它形式流程图算法的其它形式流程图对于任何流图，只要保持各节点所连的支路和传输系对于任何流图，只要保持各节点所连的支路和传输系数不变，则不论节点怎么排列所得的流图总是等效数不变，则不论节点怎么排列所得的流图总是等效的，只是数据的提取和存放的次序不同而已。的，只是数据的提取和存放的次序不同而已。因此就可以有按之间抽取的因此就可以有按之间抽取的FFTFF

14、T算法的若干形式。算法的若干形式。你现在浏览的是第三十二页，共47页你现在浏览的是第三十三页，共47页你现在浏览的是第三十四页，共47页你现在浏览的是第三十五页，共47页你现在浏览的是第三十六页，共47页4.4.按频率抽选（按频率抽选（DIFDIF）的基）的基2FFT2FFT算法算法（桑德图基算法）（桑德图基算法）DIFDIF算法是将输出序列算法是将输出序列X X（K K）按其顺序的奇偶分解为越来越短）按其顺序的奇偶分解为越来越短的序列。仍设序列的点数为的序列。仍设序列的点数为N N2 2L L,L,L为整数。为整数。先将输入序列按先将输入序列按n n的顺序分为前后两半。的顺序分为前后两半。你

15、现在浏览的是第三十七页，共47页当当k k为偶数时，为偶数时，(-1)(-1)k k=1;=1;当当k k为偶数时，为偶数时，(-1)(-1)k k=-1=-1。因此按因此按k k的奇偶可将的奇偶可将X(k)X(k)分为两部分。分为两部分。你现在浏览的是第三十八页，共47页令则你现在浏览的是第三十九页，共47页令则你现在浏览的是第四十页，共47页可以用蝶形运算来表示可以用蝶形运算来表示你现在浏览的是第四十一页，共47页N N8 8时，按时，按k k分解结果如图分解结果如图你现在浏览的是第四十二页，共47页5.5.离散傅里叶反变换离散傅里叶反变换IDFTIDFT的快速计算方法的快速计算方法DFT

16、DFT和和IDFTIDFT的变换公式的变换公式比较可知，只要把比较可知，只要把DFTDFT运算中的每一个系数运算中的每一个系数W WN Nnknk变成变成W WN N-nk-nk ，最后再乘常数，最后再乘常数1/N1/N，则以上所有按时间抽选或按，则以上所有按时间抽选或按频率抽选的频率抽选的FFTFFT都可以拿来运算都可以拿来运算IDFTIDFT。你现在浏览的是第四十三页，共47页上面的方法比较简单，但是要稍微改动上面的方法比较简单，但是要稍微改动FFTFFT的程序和参的程序和参数才能实现，下面的方法不改变数才能实现，下面的方法不改变FFTFFT的程序计算的程序计算IFFTIFFT：对对DFT

17、DFT的反变换公式取共轭的反变换公式取共轭只要先将只要先将X(k)X(k)取共轭，然后直接利用取共轭，然后直接利用FFTFFT子程序，最后子程序，最后将结果取共轭，并乘以将结果取共轭，并乘以1/N1/N，就可以得到，就可以得到x(n)x(n)的值。的值。你现在浏览的是第四十四页，共47页例：假设一次复乘的时间为例：假设一次复乘的时间为1 1 s s，而且假定一个，而且假定一个DFTDFT总共需要的共需要的时间由由计算所有乘法所需的算所有乘法所需的时间确定。确定。1 1）直接）直接计算一个算一个10241024点的点的DFTDFT需要多少需要多少时间？2 2）计算基算基2 2FFTFFT需要多少

18、需要多少时间？解：解：1 1）t tN N2 210106 6s1.05ss1.05s 2)2)基基2 2FFTFFT复乘的次数复乘的次数为(N/2)log(N/2)log2 2N=5120N=5120 t t5120105120106 6s5.12mss5.12ms你现在浏览的是第四十五页，共47页例：对一个连续时间信号例：对一个连续时间信号x xa a(t)(t)进行采样，在进行采样，在1s1s内采集了内采集了40964096个数据，个数据，1 1）若采样后没有产生频谱混叠，则信号）若采样后没有产生频谱混叠，则信号x xa a(t)(t)的最高频率时的最高频率时多少？多少？2 2）若计算采

19、样信号的）若计算采样信号的40964096点的点的DFTDFT，频谱之间的频率间隔，频谱之间的频率间隔是多少是多少HzHz？解：解：1 1）因为在）因为在1s1s内采集了内采集了40964096个数据，个数据，所以所以 f fs s=4096Hz=4096Hz 要采样后不产生频谱混叠，要采样后不产生频谱混叠，f fs s2f2fh h 因此信号的最高频率因此信号的最高频率ffs s/2=2048Hz/2=2048Hz 2)2)频谱之间的频率间隔也就是频率分辨率频谱之间的频率间隔也就是频率分辨率F F0 0 f fs s/F/F0 0N FN F0 0 f fs s/N/N 4096Hz/40964096Hz/40961Hz1Hz你现在浏览的是第四十六页，共47页课外作业课外作业P200P2003 3、你现在浏览的是第四十七页，共47页