四快速傅里叶变换.pptVIP

第四章　快速傅里叶变换 1.　引言 2.　直接计算DFT的问题及改进的途径 3.　按时间抽选（DIT）的基－2FFT算法 4.　按频率抽选（DIF）的基－2FFT算法 5.　离散傅里叶反变换IDFT的快速计算方法 1.　引言 FFT不是一种新算法,只是DFT的一种快速算法。 Cooley和Tukey在1965年发表的“机器计算傅里叶级 数的一种算法” 桑德和图基的快速算法的出现。 2.　直接计算DFT的问题及改进的途径 DFT和IDFT的变换公式 　 二者的差别就在于WN的指数符号不同，以及相差一个 常数乘因子1/N。 每计算一个X(k)值，需要N次复数乘法，以及（N-1） 次复数加法，而X(k)一共有N个值点，因此完成整个 DFT运算总共需要N2次复数乘法，N（N-1）次复数加 法。　　　　　　　　　 复数运算实际上是由实数运算来完成的， 因此(4.1)式可写成 可以看出，一次复数乘法需要4次实数乘法和2次实数 加法，一次复数加法需要2次实数加法。 因此，每计算一个X(k)值，需要4N次实数乘法，以及 2N＋2（N-1）＝2（2N－1）次实数加法，整个DFT运 算总共需要4N2次实数乘法，2N（2N-1）次实数加法。　　　　　 存在问题： 直接计算DFT，乘法次数和加法次数都是和N2成正比。 当N很大时，运算量很大，例如，N=8时，需要64次复 乘，N＝1024时，需要1048576次复乘。 减少DFT运算工作量的途径：利用WNnk的固有特性。 （1） WNnk的对称性： （2） WNnk的周期性： （3） WNnk的可约性： 可以得出 实际办法： （1）用上述特性对项合并 （2）将长序列的DFT分解为短序列的DFT，减小N值。 四点的DFT 将该矩阵的第二列和第三列交换，得 由此得出 快速傅里叶变换正是基于这样的思想发展 进来的，主要分为两大类： DIT：按时间抽选 DIF：按频率抽选 3.　按时间抽选的基－2FFT算法3.1　算法原理 先设序列点数为　　　，按n的奇偶进行分解 将DFT化为 利用系数　　的可约性，即　　　　　　　　　　　　　　 得 　　　　　　　　　　　　　　　　　　 应用系数的周期性　　　　　　　,可得 　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　 再考虑性质　　　　　　　　　　　　　 把(4.8),(4.9),(4.10)代入(4.5)式，将X(k)表达成 前后两部分，前部分为 　　　　　　　　　　　　　　　　　 后部分为 　　　　　　　　　　　　　　　　　 这样，4.11、12式只要0-(N/2-1)区间的所有X1(k) 和X2(k)的值，即可求0到(N-1)区间所有X(k)值。 4.11和4.12式用蝶形图表示。 N＝8的情况如图所示: 分析：每个蝶形运算需要一次复数乘法　　　　 及两次复数加（减）法。通过分解后运算工作量差不 多减少到一半。 进一步把N/2点子序列再按奇偶部分分解为两个N/4点 的子序列 且 其中 图4－3，给出N＝8时，在分解为两个N/4点DFT，由 两个N/4点DFT组合成N/2点DFT的流图。 X2(k)也可进行同样分解： 其中 一个N＝8点DFT就可分解为四个N/4＝2点DFT如图 序列按奇偶分解标号变化讨论（N＝8） 1、第一次分解：两个N/2点序列： 2、第二次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序列 3、最后是2点的DFT 对于例子N＝8，就是4个N/4＝2点的DFT。 如： 其中 这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数还是属于奇数来分解为两个更短的子序列，所以称为“按时间抽选法”。 3.2 运算量分析 （1）直接DFT复数算法次数是N2　　　 （2）FFT复数乘法次数是（N/2）*L 当N=2L时，一共有L级蝶形，每级有N/2个蝶形运算组成，一个蝶形运算有1次复乘，2次复加运算。 DFT和FFT算法的计算量之比为 结论：FFT比DFT更优越，当N越大时，优点更明显。 3.3 按时间抽选的FFT算法特点 1.　原位运算 每个蝶形结构完成下述基本迭代运算： 4.21的蝶形运算如图4－7所示。 蝶形的两个输出值仍放回蝶形的两个输入值所在 的存储器中，中间不需要其他的存储器。每列的N/2 个蝶形运算完成后，再开始下一列的蝶形运算，这样 存储数据就只要N个存储单元。 下一级的蝶形运算仍采取这样的原位运算，只不 过进入蝶形的组合关系有所不同。 2.　倒位序规律 3.　倒位序的实现：通过