《数字信号处理》课件11

1、第 4 1）,数字信号处理,第4章 快速傅里叶变换,引言 直接计算DFT的问题及改进途径 按时间抽选的基-2FFT算法（Cooley-Tukey算法） 按频率抽选的基-2FFT算法（Sande-Tukey算法） 离散傅里叶反变换的快速计算方法,4.1 引言,注意：FFT不是一种新的变换，是DFT的一种快速算法。,1. DFT在时域和频域都是离散的，可以采用计算机运算；,2. 直接计算DFT的运算量很大，即使采用计算机运算，也 不能解决实时性问题，影响其实际应用；,3. 1965年首次提出了DFT运算的一种快速算法，并发展和形成了一套高速有效的运算方法， 统称为快速傅里叶变换的算法。 （FFT-

2、Fast Fourier Transform）,第4章 快速傅里叶变换,引言 直接计算DFT的问题及改进途径 按时间抽选的基-2FFT算法（Cooley-Tukey算法） 按频率抽选的基-2FFT算法（Sande-Tukey算法） 离散傅里叶反变换的快速计算方法,4.2 直接计算DFT的问题及改进的途径,4.2.1 DFT的运算量,设x(n)为N点有限长序列,二者的差别: 1) WN的指数符号不同，2) 差一个常数乘因子1/N， IDFT与DFT具有相同的运算量， 可以只讨论DFT的运算量。,x (n)、WNnk 、 X(k)是复数，,完成整个DFT运算共需要：N 2次复数乘法 N(N-1)次

3、复数加法。,X (k)共有N个值 （k=0，1，N-1）,每计算一个X(k)值，需要：N次复数乘法 N-1次复数加法。,一次复数乘法：4次实数乘法 2次实数加法,复数运算实际上是由实数运算来完成的，可将DFT运算式写成,一次复数加法：2次实数加法,整个DFT运算共需要：,一个X(k)值：N次复数乘法 N-1次复数加法,每计算一个X(k)需要：4N 次 实数乘法 2N+2(N-1)=2(2N-1)次 实数加法,一次复乘：4次实数乘法 2次实数加法 一次复加：2次实数加法,2N (2N-1)次实数加法,4N 2次实数乘法,（N个X(k)值 ）,N 2次复数乘法,N (N-1)次复数加法,上述统计与

4、实际需要的运算次数稍有出入，,因此，直接计算DFT，乘法次数和加法次数都和N 2成正比， 当 N 很大时，运算量很可观。,某些WNnk可能是1或 j，如W 0N=1，WN= -1，WNN/4= -j等,为了便于比较， 一般不考虑特殊情况，而是把WNnk都看成复数,当N 很大时，这种特例的影响很小。,解: 直接计算DFT复乘次数（N )2=（10241024)2 1012次， 用每秒可做10万次复数乘法的计算机，需要近3000小时。,例：对10241024点的二维图像做DFT变换，计算机每秒可做 10万次复数乘法，需要多少时间？ （忽略加法运算时间）,对实时性很强的信号处理，改进方法： 1）提高

5、计算速度（这样，对计算速度要求太高了）； 2) 改进DFT的计算方法，以大大减少运算次数。,4.2.2 减少运算量的途径,DFT运算，利用系数Wnk的固有特性，可减少运算量：,能否减少运算量，以缩短计算时间呢？,（3） WNnk的可约性,另外,快速傅里叶变换算法的基本思想,使DFT分解为更少点数的DFT运算,DFT的运算量与 N 2 成正比，N 越小DFT的运算量越小。,在DFT运算中合并某些项，,FFT算法基本上可以分成两大类， 按时间抽选法 (DIT ，Decimation-In-Time） 按频率抽选法 (DIF， Decimation-In-Frequency）,第4章 快速傅里叶变换

6、,引言 直接计算DFT的问题及改进途径 按时间抽选的基-2FFT算法（Cooley-Tukey算法） 按频率抽选的基-2FFT算法（Sande-Tukey算法） 离散傅里叶反变换的快速计算方法,4.3 按时间抽选（DIT）的基 -2 FFT算法,4.3.1 算法原理,步骤：将 x(n)按 n先偶后奇分解为两个N/2点的子序列,基-2 FFT算法,且满足N=2L，L为正整数,将DFT化为,利用WNnk的可约性,1个N点DFT 分解为2个N/2点DFT,X1(k) 与 X2(k) 分别是 x1(r) 及 x2(r) 的N/2点DFT,只是X(k)的前一半的结果,X1(k)，X2(k)只有N/2个点，即k=0, 1, , N/2-1。,X(k)有N个点，即k=0, 1, , N-1，,要用X1(k)，X2(k) ，Wk来表达全部的X(k)值,得到,说明： 后半部分k值（N/2kN-1）所对应的X1(k)，2(k) 分别等于前半部分k值（0kN/2-1） 所对应的X1(k)， X2(k),再考虑到WkN 的以下性质:,将X(k)表达为前后两部分：,时间抽选法蝶形运算流图符号,按时间抽选，将一个N点DFT分解为两个N/2点DFT（N=8）,复数乘法：,2个 点DFT,蝶形图部分,1个 点DFT,次复数乘法,复数加