数字信号处理及MATLAB实现第四　快速傅里叶变换.pptVIP

第四章　快速傅里叶变换 1.　引言 2.　直接计算DFT的问题及改进的途径 3.　按时间抽选（DIT）的基－2FFT算法 4.　离散傅里叶反变换（IDFT）的快速计算方法 5.　N为复合数的FFT算法－混合基算法 6.　线性调频Z变换（Chirp-z变换）算法 7.　线性卷积与线性相关的FFT算法 1.　引言 库利和图基发表的“机器计算傅里叶级数的一种算法” 桑德和图基的快速算法的出现。 主要讨论几种FFT算法。 2.　直接计算DFT的问题及改进的途径 DFT和IDFT的变换公式 4.1式可写成 　　　　　　　　　　　　　　　　（4.3） 存在问题： 整个DFT运算总共需要4 次行乘法运算和 　　　　　　　　　　　　　　　　次加法运算。 直接计算DFT，乘法次数和加法次数都是和　　成正比。 减少DFT运算工作量的途径：利用　　对称性： （1）　　的对称性： （2）　　的周期性： （3）　　的可约性： 可以得出 实际办法： （1）用上述特性对项合并 （2）将长序列的DFT分解为短序列的DFT。 3.　按时间抽选的基－2FFT算法－－3.1　算法原理 先设序列点数为　　　　，按n的奇偶进行分解 将DFT化为 利用系数　　的可约性，即　　　　　　　　　　　　　　得 　　　　（4.5） 式中 　　　　　　　　　　　　　　　　　　（4.6） 　　　　　　　　　　　　　　　　　　（4.7） 应用系数的周期性　　　　　　　　　可得 　　　　　　　　　　　　　　　　　　（4.8） 　　　　　　　　　　　　　　　　　　（4.9） 再考虑性质　　　　　　　　　　　　　（4.10） 把4.8,4.9,4.10代入4.5式，将X(k)表达成前后两部分，前部分为 　　　　　　　　　　　　　　　　　　（4.11） 后部分为 　　　　　　　　　　　　　　　　　　（4.12） 这样，4.11、12式只要0-(N/2-1)区间的所有 　　　　　　　　的值，即可求0到(N-1)区间所有X(k)值。 4.11和4.12式用图4－1的蝶形符号表示。 N＝8的情况如图4－2 分析：每个蝶形运算需要一次复数乘法　　　　及两次复数加（减）法。通过分解后运算工作量差不多减少到一半。 进一步把N/2点子序列再按奇偶部分分解为两个N/4点的子序列 且 其中 图4－3，给出N＝8时，在分解为两个N/4点DFT，由两个N/4点DFT组合成N/2点DFT的流图。 　　　　也可进行同样分解： 其中 一个N＝8点DFT就可分解为四个N/4＝2点DFT如图 序列按奇偶分解标号变化讨论（N＝8） 第一次分解：两个N/2点序列： 第二次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序列 最后2点DFT按4－14~17进行计算。 这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数不是属于奇数来分解为两个更短的子序列，所以称为“按时间抽选法”。 运算量分析 直接DFT复数算法次数是　　　 FFT复数乘法次数是　　　　 DFT和FFT算法的计算量之比为 结论：FFT比DFT更优越，当N越大时，优点更明显。 三、按时间抽选的FFT算法特点 1.　原位运算 每个蝶形结构完成下述基本迭代运算： 4.21的蝶形运算如图4－7所示。 2.　倒位序规律 3.　倒位序的实现：通过变址运算完成 4.　蝶形运算两结点的距离： 第m级运算，每个蝶形的两节点距离为 　　的确定 第m级运算由4－21式写成 其中r的求解方法为 6.　存储单元 输入序列　　　　　　　　　　　　N个单元 系数　　　　　　　　　　　　　N/2个单元 四.　按时间抽选的FFT算法的其它形式流程图 4.5　离散傅里叶反变换的快速计算方法 从IDFT公式 与DFT公式 比较可知，只要把DFT运算中的每一个系数　　 　　变成　　　，最后再乘常数1/N，则以上所有按时间抽选或按频率抽选的FFT都可以拿来运算IDFT。 不改FFT的程序计算IFFT方法： 对4.29式取共轭 因而 4.6　N为复合数的FFT算法－－混合基算法 当N不满足　　　　　时，可有以下几种办法 （1）将x(n)补一些零值点的办法 （2）如要求准确的N点DFT，而N又是素数，则只能采用直接DFT方法，或者用CZT方法。 （3）N是复合数，即它可以分解成一些成一些因子的乘积，用混合基算法。 一.　整数的多基多进制表示形式 （1）对于二进制，　　　表示为 　　二进制倒序为 （2）对于r进制，正序 　　倒序 （3）对于多进制或称混合基 N可以表示成复合数，　　　　　　　　，则对于 的任一个正整数n,可以按L个基