快速傅里叶变换PPT讲稿.ppt

快速傅里叶变换第1页，共47页，编辑于2022年，星期六1.1.引言引言FFTFFT不是一种新算法不是一种新算法,只是只是DFTDFT的一种快速算法。的一种快速算法。CooleyCooley和和TukeyTukey在在19651965年发表的年发表的“机器计算傅里叶级机器计算傅里叶级数的一种算法数的一种算法”桑德和图基的快速算法的出现。桑德和图基的快速算法的出现。第2页，共47页，编辑于2022年，星期六2.2.直接计算直接计算DFTDFT的问题及改进的途径的问题及改进的途径DFTDFT和和IDFTIDFT的变换公式的变换公式二者的差别就在于二者的差别就在于W WN N的指数符号不同，以及相差一个的指数符号不同，以及相差一个常数乘因子常数乘因子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)第3页，共47页，编辑于2022年，星期六复数运算实际上是由实数运算来完成的，复数运算实际上是由实数运算来完成的，因此因此(4.1)(4.1)式可写成式可写成可以看出，一次复数乘法需要可以看出，一次复数乘法需要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)第4页，共47页，编辑于2022年，星期六存在问题：存在问题：直接计算直接计算DFTDFT，乘法次数和加法次数都是和，乘法次数和加法次数都是和N N2 2成正比。成正比。当当N N很大时，运算量很大，例如，很大时，运算量很大，例如，N=8N=8时，需要时，需要6464次复次复乘，乘，N N10241024时，需要时，需要10485761048576次复乘。次复乘。第5页，共47页，编辑于2022年，星期六减少减少DFTDFT运算工作量的途径：运算工作量的途径：利用利用W WN Nnknk的固有特性。的固有特性。（1 1）W WN Nnknk的对称性：的对称性：（2 2）W WN Nnknk的周期性：的周期性：（3 3）W WN Nnknk的可约性：的可约性：可以得出可以得出实际办法：实际办法：（1 1）用上述特性对项合并）用上述特性对项合并（2 2）将长序列的）将长序列的DFTDFT分解为短序列的分解为短序列的DFTDFT，减小，减小N N值。值。第6页，共47页，编辑于2022年，星期六对称性与周期性对称性与周期性第7页，共47页，编辑于2022年，星期六四点的四点的DFTDFT进行化简，得进行化简，得第8页，共47页，编辑于2022年，星期六将该矩阵的第二列和第三列交换，得将该矩阵的第二列和第三列交换，得由此得出由此得出第9页，共47页，编辑于2022年，星期六 快速傅里叶变换正是基于这样的思想发展快速傅里叶变换正是基于这样的思想发展进来的，主要分为两大类：进来的，主要分为两大类：DITDIT：按时间抽选：按时间抽选DIFDIF：按频率抽选：按频率抽选第10页，共47页，编辑于2022年，星期六3.3.按时间抽选的基按时间抽选的基2FFT2FFT算法算法3.13.1算法原理算法原理先设序列点数为，按先设序列点数为，按n n的奇偶进行分解的奇偶进行分解将将DFTDFT化为化为第11页，共47页，编辑于2022年，星期六利用系数的可约性，即利用系数的可约性，即得得(4.5)(4.6)(4.7)第12页，共47页，编辑于2022年，星期六应用系数的周期性应用系数的周期性,可得可得再考虑性质再考虑性质把把(4.8),(4.9),(4.10)代入代入(4.5)式，将式，将X(k)X(k)表达成表达成前后两部分，前部分为前后两部分，前部分为后部分为后部分为(4.8)(4.9)(4.10)(4.11)(4.12)第13页，共47页，编辑于2022年，星期六 这样，这样，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式用蝶形图表示。式用蝶形图表示。第14页，共47页，编辑于2022年，星期六N N8 8的情况如图所示的情况如图所示:第15页，共47页，编辑于2022年，星期六 分析：分析：每个蝶形运算需要一次复数乘法每个蝶形运算需要一次复数乘法及两次复数加（减）法。通过分解后运算工作量差不及两次复数加（减）法。通过分解后运算工作量差不多减少到一半。多减少到一半。第16页，共47页，编辑于2022年，星期六进一步把进一步把N/2N/2点子序列再按奇偶部分分解为两个点子序列再按奇偶部分分解为两个N/4N/4点点的子序列的子序列且且其中其中第17页，共47页，编辑于2022年，星期六图图4 43 3，给出，给出N N8 8时，在分解为两个时，在分解为两个N/4N/4点点DFTDFT，由，由两个两个N/4N/4点点DFTDFT组合成组合成N/2N/2点点DFTDFT的流图。的流图。第18页，共47页，编辑于2022年，星期六X X2 2(k)(k)也可进行同样分解：也可进行同样分解：其中其中第19页，共47页，编辑于2022年，星期六一个一个N N8 8点点DFTDFT就可分解为四个就可分解为四个N/4N/42 2点点DFTDFT如图如图第20页，共47页，编辑于2022年，星期六序列按奇偶分解标号变化讨论（序列按奇偶分解标号变化讨论（N N8 8）1 1、第一次分解：两个、第一次分解：两个N/2N/2点序列：点序列：第21页，共47页，编辑于2022年，星期六2 2、第二次分解，每个、第二次分解，每个N/2N/2点子序列按其奇偶分解为两个点子序列按其奇偶分解为两个N/4N/4点子序列点子序列第22页，共47页，编辑于2022年，星期六3 3、最后是、最后是2 2点的点的DFTDFT 对于例子对于例子N N8 8，就是，就是4 4个个N/4N/42 2点的点的DFTDFT。如：如：其中其中这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数还这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数还是属于奇数来分解为两个更短的子序列，所以称为是属于奇数来分解为两个更短的子序列，所以称为“按时间抽选法按时间抽选法”。第23页，共47页，编辑于2022年，星期六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个蝶形运算组个蝶形运算组成，一个蝶形运算有成，一个蝶形运算有1 1次复乘，次复乘，2 2次复加运算。次复加运算。DFTDFT和和FFTFFT算法的计算量之比为算法的计算量之比为结论：结论：FFTFFT比比DFTDFT更优越，当更优越，当N N越大时，优点更明显。越大时，优点更明显。第24页，共47页，编辑于2022年，星期六第25页，共47页，编辑于2022年，星期六第26页，共47页，编辑于2022年，星期六3.3 3.3 按时间抽选的按时间抽选的FFTFFT算法特点算法特点1.1.原位运算原位运算 每个蝶形结构完成下述基本迭代运算：每个蝶形结构完成下述基本迭代运算：4.214.21的蝶形运算如图的蝶形运算如图4 47 7所示。所示。第27页，共47页，编辑于2022年，星期六 蝶形的两个蝶形的两个输出值输出值仍仍放回放回蝶形的两个蝶形的两个输入值所在输入值所在的存储器的存储器中，中间不需要其他的存储器。每列的中，中间不需要其他的存储器。每列的N/2N/2个蝶形运算完成后，再开始下一列的蝶形运算，这样个蝶形运算完成后，再开始下一列的蝶形运算，这样存储数据就只要存储数据就只要N N个存储单元。个存储单元。下一级的蝶形运算仍采取这样的原位运算，只不下一级的蝶形运算仍采取这样的原位运算，只不过进入蝶形的组合关系有所不同。过进入蝶形的组合关系有所不同。第28页，共47页，编辑于2022年，星期六2.2.倒位序规律倒位序规律第29页，共47页，编辑于2022年，星期六3.3.倒位序的实现：通过变址运算完成倒位序的实现：通过变址运算完成第30页，共47页，编辑于2022年，星期六4.4.存储单元存储单元输入序列输入序列N N个单元个单元系数系数N/2N/2个单元个单元第31页，共47页，编辑于2022年，星期六3.43.4按时间抽选的按时间抽选的FFTFFT算法的其它形式流程图算法的其它形式流程图对于任何流图，只要保持各节点所连的支路和传输系对于任何流图，只要保持各节点所连的支路和传输系数不变，则不论节点怎么排列所得的流图总是等效数不变，则不论节点怎么排列所得的流图总是等效的，只是数据的提取和存放的次序不同而已。的，只是数据的提取和存放的次序不同而已。因此就可以有按之间抽取的因此就可以有按之间抽取的FFTFFT算法的若干形式。算法的若干形式。第32页，共47页，编辑于2022年，星期六第33页，共47页，编辑于2022年，星期六第34页，共47页，编辑于2022年，星期六第35页，共47页，编辑于2022年，星期六第36页，共47页，编辑于2022年，星期六4.4.按频率抽选（按频率抽选（DIFDIF）的基）的基2FFT2FFT算法算法（桑德图基算法）（桑德图基算法）DIFDIF算法是将输出序列算法是将输出序列X X（K K）按其顺序的奇偶分解为越来越短）按其顺序的奇偶分解为越来越短的序列。仍设序列的点数为的序列。仍设序列的点数为N N2 2L L,L,L为整数。为整数。先将输入序列按先将输入序列按n n的顺序分为前后两半。的顺序分为前后两半。第37页，共47页，编辑于2022年，星期六当当k k为偶数时，为偶数时，(-1)(-1)k k=1;=1;当当k k为偶数时，为偶数时，(-1)(-1)k k=-1=-1。因此按因此按k k的奇偶可将的奇偶可将X(k)X(k)分为两部分。分为两部分。第38页，共47页，编辑于2022年，星期六令则第39页，共47页，编辑于2022年，星期六令则第40页，共47页，编辑于2022年，星期六可以用蝶形运算来表示可以用蝶形运算来表示第41页，共47页，编辑于2022年，星期六N N8 8时，按时，按k k分解结果如图分解结果如图第42页，共47页，编辑于2022年，星期六5.5.离散傅里叶反变换离散傅里叶反变换IDFTIDFT的快速计算方法的快速计算方法DFTDFT和和IDFTIDFT的变换公式的变换公式比较可知，只要把比较可知，只要把DFTDFT运算中的每一个系数运算中的每一个系数W WN Nnknk变成变成W WN N-nk-nk ，最后再乘常数，最后再乘常数1/N1/N，则以上所有按时间抽选或按，则以上所有按时间抽选或按频率抽选的频率抽选的FFTFFT都可以拿来运算都可以拿来运算IDFTIDFT。第43页，共47页，编辑于2022年，星期六上面的方法比较简单，但是要稍微改动上面的方法比较简单，但是要稍微改动FFTFFT的程序和参的程序和参数才能实现，下面的方法不改变数才能实现，下面的方法不改变FFTFFT的程序计算的程序计算IFFTIFFT：对对DFTDFT的反变换公式取共轭的反变换公式取共轭只要先将只要先将X(k)X(k)取共轭，然后直接利用取共轭，然后直接利用FFTFFT子程序，最后子程序，最后将结果取共轭，并乘以将结果取共轭，并乘以1/N1/N，就可以得到，就可以得到x(n)x(n)的值。的值。第44页，共47页，编辑于2022年，星期六例：假设一次复乘的时间为例：假设一次复乘的时间为1 1 s s，而且假定一个，而且假定一个DFTDFT总共需要的共需要的时间由由计算所有乘法所需的算所有乘法所需的时间确定。确定。1 1）直接）直接计算一个算一个10241024点的点的DFTDFT需要多少需要多少时间？2 2）计算基算基2 2FFTFFT需要多少需要多少时间？解：解：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第45页，共47页，编辑于2022年，星期六例：对一个连续时间信号例：对一个连续时间信号x xa a(t)(t)进行采样，在进行采样，在1s1s内采集了内采集了40964096个个数据，数据，1 1）若采样后没有产生频谱混叠，则信号）若采样后没有产生频谱混叠，则信号x xa a(t)(t)的最高频率的最高频率时多少？时多少？2 2）若计算采样信号的）若计算采样信号的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第46页，共47页，编辑于2022年，星期六课外作业课外作业P200P2003 3、第47页，共47页，编辑于2022年，星期六