《快速傅里叶变换ppt课件》由会员分享，可在线阅读，更多相关《快速傅里叶变换ppt课件（68页珍藏版）》请在金锄头文库上搜索。
1、第四章 快速傅里叶变换,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）,4.1,(4-2),存在问题： 整个DFT运算总共需要4 次行乘法运算和 次加法运算。 直
2、接计算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） 后部分为 （
3、4.12）,这样，4.11、12式只要0-(N/2-1)区间的所有 的值，即可求0到(N-1)区间所有X(k)值。 4.11和4.12式用图41的蝶形符号表示。,N8的情况如图42,分析：每个蝶形运算需要一次复数乘法 及两次复数加（减）法。通过分解后运算工作量差不多减少到一半。,进一步把N/2点子序列再按奇偶部分分解为两个N/4点的子序列 且 其中,图43，给出N8时，在分解为两个N/4点DFT，由两个N/4点DFT组合成N/2点DFT的流图。,也可进行同样分解： 其中,一个N8点DFT就可分解为四个N/42点DFT如图,序列按奇偶分解标号变化讨论（N8） 第一次分解：两个N/2点序列：,第二
4、次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序列,最后2点DFT按41417进行计算。 这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数不是属于奇数来分解为两个更短的子序列，所以称为“按时间抽选法”。,运算量分析,直接DFT复数算法次数是 FFT复数乘法次数是 DFT和FFT算法的计算量之比为 结论：FFT比DFT更优越，当N越大时，优点更明显。,三、按时间抽选的FFT算法特点,1. 原位运算 每个蝶形结构完成下述基本迭代运算： 4.21的蝶形运算如图47所示。,2. 倒位序规律,3. 倒位序的实现：通过变址运算完成,4. 蝶形运算两结点的距离： 第m级运算，每个蝶形的两节
5、点距离为 的确定 第m级运算由421式写成 其中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又是素数，则只能采
6、用直接DFT方法，或者用CZT方法。 （3）N是复合数，即它可以分解成一些成一些因子的乘积，用混合基算法。,一. 整数的多基多进制表示形式 （1）对于二进制， 表示为 二进制倒序为 （2）对于r进制，正序 倒序,（3）对于多进制或称混合基 N可以表示成复合数， ，则对于 的任一个正整数n,可以按L个基 表示。正序 倒序,在这一多进制的表示中 可记为,例41,二、 的快速算法 要计算N点DFT为 （4.39） 设n是一个复合数 ，可将n的数用下面的公式表达： （4.40） 同样，倒序表达为 （4.41）,例：设 ，则 那么 所以 则排列为,同样，若 则 所以,将4.40式与4.41式代入4.39
7、式，可得 上式运用了 结果,4.42式可进一步表示为,式中,N为复合数 的DFT算法的步骤归纳如下： （1）将x(n)改写成 利用 利用4.44式做 个 点DFT，得 利用4.45式，把N个 乘以相应的旋转因子 ，组成 。 利用4.46式，做 个 点DFT，得 利用4.47式，进行整序，得到 其中,对于 重写n和k的表达式 则4.44式变成,此时有两组4点DFT。4.45,46式分别变成 后一式子共有4组2点DFT，4.47式变成,算法可以采用先乘旋转因子再算DFT的算法 当N为一个复合数时，可以分解为一些因子的乘积,2. N为复合数时FFT运算量的估计 当 时，运算量为 复数乘法 复数加法
8、直接计算N个点DFT工作量 加法 乘法：N（N1）,混合基算法可节省的运算量倍数为 乘法 加法,当 时，混合基算法总乘法次数 与直接计算DFT相比，运算量之比,4.10 线性卷积与线性相关的FFT算法,一、线性卷积的FFT算法 1. 概念 设x(n)为L点，h(n)为M点，输出y(n)为 y(n)也是有限长序列，其点数为LM1。 2. 线性卷积运算量 乘法次数,线性相位滤波器满足条件 运算结构如图5.26,5.27所示 线性相位FIR滤波器的乘法运算量,用FFT法（圆周卷积）来代替这线性卷积时，不产生混叠条件是使x(n),h(n)都补零值点，补到至少N=M+L-1，即 然后计算圆周卷积 此时y
9、(n)能代表线性卷积结果。,用FFT计算y(n)步骤如下： （1）求 ，N点 （2）求 ，N点 （3）计算 ； （4）求 ，N点,工作量分析 FFT计算工作量 （4.105） 用线性相位滤波器来比较直接计算线性卷积和FFT法计算线性卷积时比值 （4.106）,运算量分析： （1）x(n)与h(n)点数差不多，设ML， 则 ，则 计算得下表,（2）当x(n)点数很多时，即当 则 这时 当L太大时，体现不出圆周积分的优点。 解决办法：分段卷积或称分段过滤,1. 重叠相加法 设h(n)的点数为M，信号x(n)为很长的序列。将x(n)分解为很多段，每段为L点，L选择成和M的数量级相同，用 表示x(n)
10、的第i段 （4.108） 则输入序列可表示成 （4.109） 线性卷积为 （4.110）,每一个 才可用快速卷积办法来运算，对 和 补零值点，补到N点。为利用基2算法，取 ，然后作N点的圆周卷积 其方法如图429所示。,重叠相加法的步骤总结 （1）计算N点FFT， （2）计算N点FFT， （3）相乘， （4）计算N点IFFT， （5）将各段 （包括重叠部分相加），,2. 重叠保留法 先将x(n)分段，每段补上LNM1个点；序列中补零处不补零，而每一段的前边补上前一段保留下来的（M1）个输入序列值，组成LM1点序列 ，如图4.30a所示。 如果 ，则可在每段序列未端补零值点，补到长度为2m。,二、线性相关的FFT算法：常称之为快速相关，要利用补零值点的办法避免混叠失真。 设x(n)为L点，y(n)为M点，需求线性相关 （4.115） 利用FFT法求线性相关是用圆周相关代替线性相关，选择 令,其计算步骤如下： （1）求N点FFT， （2）求N点FFT， （3）求乘积， （4）求N点IFFT， 同样，可以只利用已有的FFT程序计算IFFT，求,再见！,
