数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件

1、第四章快速傅里叶变换1.引言2.直接计算DFT的问题及改进的途径3.按时间抽选（DIT）的基2FFT算法4.离散傅里叶反变换（IDFT）的快速计算方法5.N为复合数的FFT算法混合基算法6.线性调频Z变换（Chirp-z变换）算法7.线性卷积与线性相关的FFT算法第四章快速傅里叶变换1.引言1.引言库利和图基发表的“机器计算傅里叶级数的一种算法”桑德和图基的快速算法的出现。主要讨论几种FFT算法。1.引言库利和图基发表的“机器计算傅里叶级数的一种算法”2.直接计算DFT的问题及改进的途径DFT和IDFT的变换公式4.1式可写成（4.3）4.1 (4-2)2.直接计算DFT的问题及改进的途径DF

2、T和IDFT的变换存在问题：整个DFT运算总共需要4 次行乘法运算和次加法运算。直接计算DFT，乘法次数和加法次数都是和成正比。存在问题：减少DFT运算工作量的途径：利用对称性：（1）的对称性：（2）的周期性：（3）的可约性：可以得出实际办法：（1）用上述特性对项合并（2）将长序列的DFT分解为短序列的DFT。减少DFT运算工作量的途径：利用对称性：3.按时间抽选的基2FFT算法3.1算法原理先设序列点数为，按n的奇偶进行分解将DFT化为3.按时间抽选的基2FFT算法3.1算法原理先设利用系数的可约性，即得（4.5）式中（4.6）（4.7）利用系数的可约性，即得应用系数的周期性可得（4.8）（

3、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式用图41的蝶形符号表示。这样，4.11、12式只要0-(N/2-1)区间的所有N8的情况如图42N8的情况如图42分析：每个蝶形运算需要一次复数乘法及两次复数加（减）法。通过分解后运算工作量差不多减少到一半。分析：每个蝶形运算需要一次复数乘法及两次复数加（减）进一步把N/2点子序列再按奇偶部分分解为两个N/4点的子序列且

4、其中进一步把N/2点子序列再按奇偶部分分解为两个N/4点的子序列图43，给出N8时，在分解为两个N/4点DFT，由两个N/4点DFT组合成N/2点DFT的流图。图43，给出N8时，在分解为两个N/4点DFT，由两个N也可进行同样分解：其中也可进行同样分解：一个N8点DFT就可分解为四个N/42点DFT如图一个N8点DFT就可分解为四个N/42点DFT如图序列按奇偶分解标号变化讨论（N8）第一次分解：两个N/2点序列：序列按奇偶分解标号变化讨论（N8）第二次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序列第二次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序最后2点DFT按4141

5、7进行计算。这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数不是属于奇数来分解为两个更短的子序列，所以称为“按时间抽选法”。最后2点DFT按41417进行计算。运算量分析直接DFT复数算法次数是FFT复数乘法次数是DFT和FFT算法的计算量之比为结论：FFT比DFT更优越，当N越大时，优点更明显。运算量分析直接DFT复数算法次数是数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件三、按时间抽选的FFT算法特点1.原位运算每个蝶形结构完成下述基本迭代运算：4.21的蝶形运算如图47所示。三、按时间抽选的FFT算法特点1.原位运算2.倒位序规律2.倒位序规律3.倒位序的实现：通过

6、变址运算完成3.倒位序的实现：通过变址运算完成4.蝶形运算两结点的距离：第m级运算，每个蝶形的两节点距离为的确定第m级运算由421式写成其中r的求解方法为4.蝶形运算两结点的距离：6.存储单元输入序列N个单元系数N/2个单元6.存储单元四.按时间抽选的FFT算法的其它形式流程图四.按时间抽选的FFT算法的其它形式流程图数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件4.5离散傅里叶反变换的快速计算方法从IDFT公

7、式与DFT公式比较可知，只要把DFT运算中的每一个系数变成，最后再乘常数1/N，则以上所有按时间抽选或按频率抽选的FFT都可以拿来运算IDFT。4.5离散傅里叶反变换的快速计算方法从IDFT公式不改FFT的程序计算IFFT方法：对4.29式取共轭因而不改FFT的程序计算IFFT方法：数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件4.6N为复合数的FFT算法混合基算法当N不满足时，可有以下几种办法（1）将x(n)补一些零值点的办法（2）如要求准确的N点DFT，而N又是素数，则只能采用直接DFT方法，或者用CZT方法。（3）N是复合数，即它可以分解成一些成一些因子的乘积，用混合基算法。

8、4.6N为复合数的FFT算法混合基算法当N不满足一.整数的多基多进制表示形式（1）对于二进制，表示为二进制倒序为（2）对于r进制，正序倒序一.整数的多基多进制表示形式（3）对于多进制或称混合基N可以表示成复合数，则对于 的任一个正整数n,可以按L个基表示。正序倒序（3）对于多进制或称混合基在这一多进制的表示中可记为在这一多进制的表示中例41例41二、的快速算法要计算N点DFT为（4.39）设n是一个复合数，可将n的数用下面的公式表达：（4.40）同样，倒序表达为（4.41）二、的快速算法例：设，则那么所以则排列为例：设，则同样，若则所以同样，若则将4.40式与4.41式代入4.39式，可得上式

9、运用了结果将4.40式与4.41式代入4.39式，可得4.42式可进一步表示为4.42式可进一步表示为式中式中N为复合数的DFT算法的步骤归纳如下：（1）将x(n)改写成利用利用4.44式做个点DFT，得利用4.45式，把N个乘以相应的旋转因子，组成。利用4.46式，做个点DFT，得利用4.47式，进行整序，得到其中N为复合数的DFT算法的步骤归纳如下：对于重写n和k的表达式则4.44式变成对于重写n和k的表达式此时有两组4点DFT。4.45,46式分别变成后一式子共有4组2点DFT，4.47式变成此时有两组4点DFT。4.45,46式分别变成数字信号处理及MATLAB实现第四章-快速傅里叶变

10、换-课件算法可以采用先乘旋转因子再算DFT的算法当N为一个复合数时，可以分解为一些因子的乘积算法可以采用先乘旋转因子再算DFT的算法2.N为复合数时FFT运算量的估计当时，运算量为复数乘法复数加法直接计算N个点DFT工作量加法乘法：N（N1）2.N为复合数时FFT运算量的估计混合基算法可节省的运算量倍数为乘法加法混合基算法可节省的运算量倍数为当时，混合基算法总乘法次数与直接计算DFT相比，运算量之比当时，混合基算法总乘法次数4.10 线性卷积与线性相关的FFT算法一、线性卷积的FFT算法1.概念设x(n)为L点，h(n)为M点，输出y(n)为 y(n)也是有限长序列，其点数为LM1。2.线性卷

11、积运算量乘法次数4.10 线性卷积与线性相关的FFT算法一、线性卷积的FFT线性相位滤波器满足条件运算结构如图5.26,5.27所示线性相位FIR滤波器的乘法运算量线性相位滤波器满足条件用FFT法（圆周卷积）来代替这线性卷积时，不产生混叠条件是使x(n),h(n)都补零值点，补到至少N=M+L-1，即然后计算圆周卷积此时y(n)能代表线性卷积结果。用FFT法（圆周卷积）来代替这线性卷积时，不产生混叠条件是使用FFT计算y(n)步骤如下：（1）求，N点（2）求，N点（3）计算；（4）求，N点用FFT计算y(n)步骤如下：工作量分析FFT计算工作量（4.105）用线性相位滤波器来比较直接计算线性卷

12、积和FFT法计算线性卷积时比值（4.106）工作量分析运算量分析：（1）x(n)与h(n)点数差不多，设ML，则，则计算得下表运算量分析：（2）当x(n)点数很多时，即当则这时当L太大时，体现不出圆周积分的优点。解决办法：分段卷积或称分段过滤（2）当x(n)点数很多时，即当1.重叠相加法设h(n)的点数为M，信号x(n)为很长的序列。将x(n)分解为很多段，每段为L点，L选择成和M的数量级相同，用表示x(n)的第i段（4.108）则输入序列可表示成（4.109）线性卷积为（4.110）1.重叠相加法每一个才可用快速卷积办法来运算，对和补零值点，补到N点。为利用基2算法，取，然后作N点的圆周卷积

13、其方法如图429所示。每一个才可用快速卷积办法来运算，对和数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件数字信号处理及MATLAB实现第四章-快速傅里叶变换-课件重叠相加法的步骤总结（1）计算N点FFT，（2）计算N点FFT，（3）相乘，（4）计算N点IFFT，（5）将各段（包括重叠部分相加），重叠相加法的步骤总结2.重叠保留法先将x(n)分段，每段补上LNM1个点；序列中补零处不补零，而每一段的前边补上前一段保留下来的（M1）个输入序列值，组成LM1点序列，如图4.30a所示。如果，则可在每段序列未端补零值点，补到长度为2m。2.重叠保留法二、线性相关的FFT算法：常称之为快速相关，要利用补零值点的办法避免混叠失真。设x(n)为L点，y(n)为M点，需求线性相关（4.115）利用FFT法求线性相关