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

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

2、T的变换公式4.1式可写成（4.3）10,0,1,1NnkNnX kx n WkN4.1 101,0,1,1NnkNkx nX k WnNN (4-2)110010ReImReImReReImImReImImReNNnknknkNNNnnNnknknknkNNNNnX kx nWx njx nWjWx nWx nWjx nWx nW存在问题：整个DFT运算总共需要4 次行乘法运算和次加法运算。直接计算DFT，乘法次数和加法次数都是和成正比。2N2(21)2(21)NNNN2N减少DFT运算工作量的途径：利用对称性：（1）的对称性：（2）的周期性：（3）的可约性：可以得出实际办法：（1）用上述特

3、性对项合并（2）将长序列的DFT分解为短序列的DFT。3.按时间抽选的基2FFT算法3.1算法原理先设序列点数为，按n的奇偶进行分解将DFT化为2LN 利用系数的可约性，即得（4.5）式中（4.6）（4.7）nkNW 112212221200NNrkkrkkNNNNrrX kx r WWxr WXkW Xk 11221122002NNrkrkNNrrXkxr Wxr W 112222220021NNrkrkNNrrXkxr WxrW应用系数的周期性可得（4.8）（4.9）再考虑性质（4.10）把4.8,4.9,4.10代入4.5式，将X(k)表达成前后两部分，前部分为（4.11）后部分为（4.

4、12）11222112121002NNNrkrkNNrrNXkx r Wx r WXk 222NXkXk22NkNkkNNNNWWWW 12,kNX kXkW Xk0,1,12Nk 21212222,0,1,12Nr kNkNNNNX kXkWXkNXkW Xkk这样，4.11、12式只要0-(N/2-1)区间的所有的值，即可求0到(N-1)区间所有X(k)值。4.11和4.12式用图41的蝶形符号表示。N8的情况如图42分析：每个蝶形运算需要一次复数乘法及两次复数加（减）法。通过分解后运算工作量差不多减少到一半。进一步把N/2点子序列再按奇偶部分分解为两个N/4点的子序列且其中图43，给出N

5、8时，在分解为两个N/4点DFT，由两个N/4点DFT组合成N/2点DFT的流图。也可进行同样分解：其中一个N8点DFT就可分解为四个N/42点DFT如图序列按奇偶分解标号变化讨论（N8）第一次分解：两个N/2点序列：第二次分解，每个N/2点子序列按其奇偶分解为两个N/4点子序列最后2点DFT按41417进行计算。这种方法的每一步分解都是按输入序列在时这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数不是属于奇数来分解间上的次序是属于偶数不是属于奇数来分解为两个更短的子序列，所以称为为两个更短的子序列，所以称为“按时间抽按时间抽选法选法”。运算量分析直接DFT复数算法次数是FFT复数乘

6、法次数是DFT和FFT算法的计算量之比为结论：FFT比DFT更优越，当N越大时，优点更明显。三、按时间抽选的FFT算法特点1.原位运算每个蝶形结构完成下述基本迭代运算：4.21的蝶形运算如图47所示。2.倒位序规律3.倒位序的实现：通过变址运算完成4.蝶形运算两结点的距离：第m级运算，每个蝶形的两节点距离为的确定第m级运算由421式写成其中r的求解方法为6.存储单元输入序列N个单元系数N/2个单元四.按时间抽选的FFT算法的其它形式流程图4.5离散傅里叶反变换的快速计算方法从IDFT公式与DFT公式比较可知，只要把DFT运算中的每一个系数变成，最后再乘常数1/N，则以上所有按时间抽选或按频率抽

7、选的FFT都可以拿来运算IDFT。不改FFT的程序计算IFFT方法：对4.29式取共轭因而4.6N为复合数的FFT算法混合基算法当N不满足时，可有以下几种办法（1）将x(n)补一些零值点的办法（2）如要求准确的N点DFT，而N又是素数，则只能采用直接DFT方法，或者用CZT方法。（3）N是复合数，即它可以分解成一些成一些因子的乘积，用混合基算法。一.整数的多基多进制表示形式（1）对于二进制，表示为二进制倒序为（2）对于r进制，正序倒序（3）对于多进制或称混合基N可以表示成复合数，则对于 的任一个正整数n,可以按L个基表示。正序倒序在这一多进制的表示中可记为例41二、的快速算法要计算N点DFT为

8、（4.39）设n是一个复合数，可将n的数用下面的公式表达：（4.40）同样，倒序表达为（4.41）例：设，则那么所以则排列为124,2rr同样，若则所以将4.40式与4.41式代入4.39式，可得上式运用了结果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式变成算法可以采用先乘旋转因子再算

9、DFT的算法当N为一个复合数时，可以分解为一些因子的乘积2.N为复合数时FFT运算量的估计当时，运算量为复数乘法复数加法直接计算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

10、(n),h(n)都补零值点，补到至少N=M+L-1，即然后计算圆周卷积此时y(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的数量级

11、相同，用表示x(n)的第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，求4.11数字信号处理的实现