1、第第4 4章章 快速傅里叶变换快速傅里叶变换 引言引言 直接计算直接计算DFTDFT的问题及改进途径的问题及改进途径 按时间抽选的基按时间抽选的基-2FFT-2FFT算法（算法（Cooley-Cooley-TukeyTukey算法）算法）按频率抽选的基按频率抽选的基-2FFT-2FFT算法（算法（Sande-TukeySande-Tukey算法）算法）离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法4.1 4.1 引言引言注意：注意：FFT不是一种新的变换，是DFT的一种快速算法。1.DFT在时域和频域都是离散的，可以采用计算机运算；2.直接计算DFT的运算量很大，即使采用计算机运
2、算，也 不能解决实时性问题，影响其实际应用；3.1965年首次提出了DFT运算的一种快速算法，并发展和形成了一套高速有效的运算方法，统称为快速傅里叶变换的算法。（FFT-Fast Fourier Transform）第第4 4章章 快速傅里叶变换快速傅里叶变换 引言引言 直接计算直接计算DFTDFT的问题及改进途径的问题及改进途径 按时间抽选的基按时间抽选的基-2FFT-2FFT算法（算法（Cooley-Cooley-TukeyTukey算法）算法）按频率抽选的基按频率抽选的基-2FFT-2FFT算法（算法（Sande-TukeySande-Tukey算法）算法）离散傅里叶反变换的快速计算方法
3、离散傅里叶反变换的快速计算方法4.2 4.2 直接计算直接计算DFTDFT的问题及改进的途径的问题及改进的途径 4.2.1 DFT4.2.1 DFT的运算量的运算量IDFT10)(1)(NknkNWkXNnXn=0,1,N-1 设x(n)为N点有限长序列二者的差别:1)WN的指数符号不同，2)差一个常数乘因子1/N，IDFT与DFT具有相同的运算量，可以只讨论DFT的运算量。10)()(NnnkNWnxkXk=0,1,N-1 DFTDFTDFT运算实质运算实质复数乘法复数乘法复数加法复数加法x(n)、WNnk 、X(k)是复数，完成整个DFT运算共需要：N 2次复数乘法 N(N-1)次复数加法
4、。X(k)共有N个值 （k=0，1，N-1）每计算一个X(k)值，需要：N次复数乘法 N-1次复数加法。10)()(NnnkNWnxkX1100()()Re()jIm()RejImNNnknknkNNNnnX kx n Wx nx nWW 一次复数乘法：4次实数乘法 2次实数加法复数运算实际上是由实数运算来完成的，可将DFT运算式写成 10Re()ReIm()ImNnknkNNnx nWx nWj(Re()ImIm()Re)nknkNNx nWx nW一次复数加法：2次实数加法 整个DFT运算共需要：一个X(k)值：N次复数乘法 N-1次复数加法每计算一个X(k)需要：4N 次 实数乘法 2N
5、+2(N-1)=2(2N-1)次 实数加法 一次复乘：4次实数乘法 2次实数加法 一次复加：2次实数加法 2N(2N-1)次实数加法4N 2次实数乘法（N个X(k)值）N 2次复数乘法N(N-1)次复数加法上述统计与实际需要的运算次数稍有出入，因此，直接计算DFT，乘法次数和加法次数都和N 2成正比，当 N 很大时，运算量很可观。某些WNnk可能是1或 j，如W 0N=1，WN=-1，WNN/4=-j等为了便于比较，一般不考虑特殊情况，而是把WNnk都看成复数当N 很大时，这种特例的影响很小。解解:直接计算直接计算DFT复乘次数（复乘次数（N)2=（10241024)2 1012次，次，用每秒
6、可做用每秒可做10万次复数乘法的计算机，需要近万次复数乘法的计算机，需要近3000小时。小时。例：对例：对10241024点的二维图像做点的二维图像做DFT变换，计算机每秒可做变换，计算机每秒可做 10万次复数乘法，需要多少时间？万次复数乘法，需要多少时间？（忽略加法运算时间）（忽略加法运算时间）对实时性很强的信号处理，改进方法：对实时性很强的信号处理，改进方法：1）提高计算速度（这样，对计算速度要求太高）提高计算速度（这样，对计算速度要求太高了了）；）；2)改进改进DFT的计算方法，以大大减少运算次数。的计算方法，以大大减少运算次数。4.2.2 4.2.2 减少运算量的途径减少运算量的途径（
7、2）WNnk的周期性)()(NknNkNnNnkNWWWDFT运算，利用系数Wnk的固有特性，可减少运算量：能否减少运算量，以缩短计算时间呢？nkNnkNWW*)(（1）WNnk的对称性（3）WNnk的可约性/,nknmknknk mNmNNN mWWWW()()n NkNn knkNNNWWW/2(/2)1,NkNkNNNWWW 另外 快速傅里叶变换算法的基本思想使DFT分解为更少点数的DFT运算DFT的运算量与 N 2 成正比，N 越小DFT的运算量越小。在DFT运算中合并某些项，FFT算法基本上可以分成两大类，按时间抽选法 (DIT，Decimation-In-Time）按频率抽选法 (
8、DIF，Decimation-In-Frequency）第第4 4章章 快速傅里叶变换快速傅里叶变换 引言引言 直接计算直接计算DFTDFT的问题及改进途径的问题及改进途径 按时间抽选的基按时间抽选的基-2FFT-2FFT算法（算法（Cooley-Cooley-TukeyTukey算法）算法）按频率抽选的基按频率抽选的基-2FFT-2FFT算法（算法（Sande-TukeySande-Tukey算法）算法）离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法4.3 4.3 按时间抽选（按时间抽选（DITDIT）的基的基 -2 FFT-2 FFT算法算法 4.3.1 4.3.1 算法原理
9、算法原理12(2)()0,1,1(21)()2xrxrNrxrxr设序列x(n)长度为N，步骤：将 x(n)按 n先偶后奇分解为两个N/2点的子序列 基-2 FFT算法且满足N=2L，L为正整数111000()DFT()()()()NNNnknknkNNNnnnnnX kx nx n Wx n Wx n W为偶数为奇数将DFT化为 11222(21)00(2)(21)NNrkrkNNrrxr WxrW1122221200()()()()NNrkkrkNNNrrx rWWxr W2j2/j222/2NNNNWeeW11221/22/200()()NNrkkrkNNNrrxr WWxr W利用WN
10、nk的可约性 12()()kNXkWXk 1122221200()()()()NNrkkrkNNNrrXkx rWWxr W11221122002/()()()NNrkrkNNrrXkxr Wxr W )()()()()(212/21202/1120kXWkXWrxWWrxkXkNrkNNrkNrkNNr1个N点DFT 分解为2个N/2点DFTX1(k)与 X2(k)分别是 x1(r)及 x2(r)的N/2点DFT112222220021/()()()NNrkrkNNrrXkxr WxrW 只是X(k)的前一半的结果X1(k)，X2(k)只有N/2个点，即k=0,1,N/2-1。12()()(
11、)kNX kXkWXkX(k)有N个点，即k=0,1,N-1，要用X1(k)，X2(k)，Wk来表达全部的X(k)值得到)()()(212/120122/12011kXWrxWrxkNXrkNNrkNrNNr)(222kXkNX说明：后半部分k值（N/2kN-1）所对应的X1(k)，2(k)分别等于前半部分k值（0kN/2-1）所对应的X1(k)，X2(k)222/NrkrkNNWW 再考虑到WkN 的以下性质:kNkNNNkNNWWWW2/2将X(k)表达为前后两部分：12()()()0,1,12kNNX kXkWXkk21212()()222NkkNNNNNXkXkWXkXkW Xk12,
12、1,0Nk时间抽选法蝶形运算流图符号 12()()()0,1,12kNNX kXkWXkk12()()()0,1,122kNNNX kXkWXkk按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8）复数乘法：2N2个 点DFT22222NN蝶形图部分2N21222NNNN2224NN2N1个 点DFT22N次复数乘法复数加法：2N2个 点DFT12NN蝶形图部分N2122NNNN122NN2N1个 点DFTN点DFT，一次分解后次复数乘法22N次复数加法22N将N点DFT，进行一次分解后，运算工作量节省了近一半N点DFT，不进行分解次复数加法次复数乘法2N1NN由于N=2L，N/2仍是偶数可以进一步把每个N/2点子序列分解为两个N/4点的子序列
