第四章-快速傅里叶变换课件

第4章 快速傅里叶变换4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度复数加法复数加法 N(N-1)复数乘法复数乘法 N 2如何提高DFT的运算效率?4.1 快速傅里叶变换1.将长序列DFT分解为短序列的DFT2.由于DFT的运算量与N2成正比，N越小，DFT的运算量越少。所以如果把一个长序列的DFT能分解为短序列的DFT的组合，则显然可取得减少运算工作量的效果。2.利用旋转因子 的周期性、对称性、可约性。旋转因子 的性质1)周期性周期性2)对称性对称性3)可约性可约性例：求当N4时，X(2)的值 通过合并，使乘法次数由4次减少到1次，运算量减少。4.2 按时间抽取的快速傅里叶变换算法按时间抽取的快速傅里叶变换算法 FFT的算法形式有很多种，但基本上可以分为两大类：时间抽取时间抽取(Decimation in time)FFT算法算法频率抽取频率抽取(Decimation in frequency)FFT算法算法 为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是 的情况（M为正整数）。该情况下的变换称为基2FFT。先将序列x(n)按奇偶项分解为两组 将DFT运算也相应分为两组 因为其中 、分别是 的N/2点的DFT 至此，一个N点DFT被分解为两个N/2点的DFT。这样N点DFT可全部由下式确定出来：上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运算。通过这样的分解以后，每一个N2点的DFT只需要 次复数乘法，两个N/2点的DFT需要 次复数乘法，再加上将两个N2点DFT合并成为N点DFT时有N2次与W因子相乘，一共需要 次复乘。可见，通过这样的分解，运算量节省了近一半。因为，N/2仍然是偶数，因此可以对两个N/2点的DFT再分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT。例如对 ，可以在按其偶数部分及奇数部分进行分解：则运算可相应分为两组：将系数统一为以为周期，即 ，可得 同样，对也可进行类似的分解。一直分解下去，最后是点的DFT，点DFT的运算也可用碟形符号来表示。这样，对于一个的DFT运算，其按时间抽取的分解过程及完整流图如下图所示。基基2 2时间抽取时间抽取FFTFFT算法流图算法流图第一级第一级第二级第二级第三级第三级 分析上面的流图，一共要进行M次分解，构成了从x(n)到X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共需要复数乘法次数：复数加法次数：由于计算机进行乘法所需时间比加法多得多，如果计算时间只考虑与乘法次数成正比，则直接DFT算法与FFT算法的计算量之比为算法的计算复杂度算法的计算复杂度复乘次数复乘次数NN 2按时间抽取的FFT算法特点 1、原位运算 也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。2、倒位序规律倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x11101010101自然顺序二进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117FFT算法流图旋转因子 规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级 的蝶形系数为 ，蝶形节点的距离为N/2。4.3 按频率抽取的快速傅里叶变换算法 除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法。频率抽取法将输入序列不是按奇、偶分组，而是将点DFT写成前后两部分：因为，k为偶数时，k为奇数时，由此可将X(k)分解为偶数组和奇数组：令 令令这两个序列都是N/2点的序列，对应的是两个N/2点的DFT运算：这样，同样是将一个N点的DFT分解为两个N/2点的DFT了。频率抽选法对应的碟形运算关系图如下：对于N=8时频率抽取法的FFT流图如下：0NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-14.4 离散傅里叶反变换的快速算法步骤：A)将X k取共轭C)对B)中结果取共轭并除以NnkNNkWkXNkXIDFTnx-=110*-=nkNNkWkXNnx110B)用FFT程序计算DFTX*k4.5 实序列的快速傅里叶变换x1k,x2k是实序列，将其构成复序列yk=x1k+j x2kDFTx1k+j x2k=YR m+jYI m=-21njxnxDFT)()(NINRkjYkY-)()(211NIINRRkYkYjkYkYnxDFT-+-+=)()(212NIINRRkYkYjkYkYjnxDFT-+-=yk是一个长度为2N的序列1,1,0 12221-=+=NknynxnynxnyL1,1,0 221221-=-=+=NmkXWkXNkYkXWkXkYkNkNK