-第5快速傅里叶度换 第3章快速傅里叶变换 3,1引言 3.2直接计算DHT的问题及改进的途径 33按时间抽取(Dm)的基2-FFT算法 34按频率抽取(DIF)的基2-FFT算法 35N为复合数的FFT算法 36线性调频Z变换(Chip-Z变换)算法 3.7利用FFT分析时域连续信号频谱 38FFT的其他应用 BACI
第3章 快速傅里叶变换 第3章 快速傅里叶变换 3.1 引言 3.2 直接计算DFT的问题及改进的途径 3.3 按时间抽取（DIT）的基2-FFT算法 3.4 按频率抽取（DIF）的基2-FFT算法 3.5 N为复合数的FFT算法 3.6 线性调频Z变换（Chirp-Z变换）算法 3.7 利用FFT分析时域连续信号频谱 3.8 FFT的其他应用
-第3快速疼里叶变换一 31引言 快速傅里叶变换(FFT)并不是一种新的变换,而是离散傅里叶变换 (DFT)的一种快速算法。 由于有限长序列在其频域也可离散化为有限长序列(DFT),因此离散 傅里叶变换(DFT)在数字信号处理中是非常有用的。例如,在信号的频谱 分析、系统的分析、设计和实现中都会用到DFT的计算。但是,在相当长 的时间里,由于DFT的计算量太大,即使采用计算机也很难对问题进行实时 处理,所以并没有得到真正的运用。直到1965年首次发现了DFT运算的一种 快速算法以后,情况才发生了根本的变化。人们开始认识到DFT运算的一些 内在规律,从而很快地发展和完善了一套高速有效的运算方法,这就是现在 人们普遍称之为快速傅里叶变换(FFT)的算法。FFT出现后使DFT的运算 大大简化,运算时间一般可缩短一二个数量级之多,从而使DFT的运算在实 际中真正得到了广泛的应用
第3章 快速傅里叶变换 3.1 引 言 快速傅里叶变换（FFT）并不是一种新的变换， 而是离散傅里叶变换 （DFT）的一种快速算法。 由于有限长序列在其频域也可离散化为有限长序列（DFT），因此离散 傅里叶变换（DFT）在数字信号处理中是非常有用的。例如，在信号的频谱 分析、 系统的分析、 设计和实现中都会用到DFT的计算。 但是，在相当长 的时间里， 由于DFT的计算量太大，即使采用计算机也很难对问题进行实时 处理，所以并没有得到真正的运用。 直到1965年首次发现了DFT运算的一种 快速算法以后，情况才发生了根本的变化。人们开始认识到DFT运算的一些 内在规律，从而很快地发展和完善了一套高速有效的运算方法， 这就是现在 人们普遍称之为快速傅里叶变换（FFT）的算法。 FFT出现后使DFT的运算 大大简化，运算时间一般可缩短一二个数量级之多，从而使DFT的运算在实 际中真正得到了广泛的应用
-第5快速傅里叶度换 32直接计算DFT的问题及改进的途径 321直接计算DFT的运算量问题 设x(n)为N点有限长序列,其DFT为 X(k)=∑(nwk01,,M1 (3-1) 反变换(IDFT)为 N X(n)=∑X(k)Wn=0.1,…N1(32) k=0
第3章 快速傅里叶变换 3.2 直接计算DFT的问题及改进的途径 3.2.1 直接计算DFT的运算量问题 设x(n)为N点有限长序列，其DFT为 − = = 1 0 ( ) ( ) N n nk n WN X k x k=0, 1, …, N-1 （3-1） 反变换（IDFT）为 − = − = 1 0 ( ) 1 ( ) N k n k WN X k N X n n=0, 1, …, N-1 （3-2）
-第3快速疼里叶变换一 二者的差别只在于W的指数符号不同,以及差一个常数乘 因子1/N,所以IDFT与DFT具有相同的运算工作量。下面我们 只讨论DFT的运算量。 般来说,x(n)和W都是复数,X(k)也是复数,因此每计 算一个X(k)值,需要N次复数乘法和N-1次复数加法。而Ⅺ(k)一共 有N个点(k从0取到M-1),所以完成整个DFT运算总共需要M 次复数乘法及NN-1)次复数加法。在这些运算中乘法运算要比 加法运算复杂,需要的运算时间也多一些。因为复数运算实际 上是由实数运算来完成的,这时DFT运算式可写成
第3章 快速傅里叶变换 二者的差别只在于WN的指数符号不同，以及差一个常数乘 因子1/N，所以IDFT与DFT具有相同的运算工作量。 下面我们 只讨论DFT的运算量。 一般来说，x(n)和WN nk都是复数，X(k)也是复数，因此每计 算一个X(k)值，需要N次复数乘法和N-1次复数加法。而X(k)一共 有N个点（k从0取到N-1），所以完成整个DFT运算总共需要N2 次复数乘法及N(N-1)次复数加法。 在这些运算中乘法运算要比 加法运算复杂，需要的运算时间也多一些。因为复数运算实际 上是由实数运算来完成的， 这时DFT运算式可写成
-第5快速傅里叶度换 X(k)=2 x(n)WN 2IRe[x(n)1+jIm[x(n)I)(Re[W]+j Im[W I >Re[x(n)]Re[Wn]-Im[ x(n)Im[Wn] +j(Re[x(n)]Im[WN ]+Im[ x(n)]RelW D) (3-3) 由此可见,一次复数乘法需用四次实数乘法和二次实数加法; 次复数加法需二次实数加法。因而每运算一个X(k需4N次实 数乘法和2N+2(N-1)=2(2N-1)次实数加法。所以,整个DFT运算 总共需要4N次实数乘法和2N2N-)次实数加法
第3章 快速傅里叶变换 (Re[ ( )]Im[ ] Im[ ( )]Re[ ])} {Re[ ( )]Re[ ] Im[ ( )]Im[ ] ( ) ( ) {Re[ ( )] Im[ ( )]}{Re[ ] Im[ ]} 1 0 1 0 1 0 n k N n k N n k N N n n k N N n n k N n k N N n n k N j x n W x n W x n W x n W X k x n W x n j x n W j W + + = − = = + + − = − = − = （3-3） 由此可见，一次复数乘法需用四次实数乘法和二次实数加法； 一次复数加法需二次实数加法。 因而每运算一个X(k)需4N次实 数乘法和2N+2(N-1)=2(2N-1)次实数加法。 所以，整个DFT运算 总共需要4N2次实数乘法和2N(2N-1)次实数加法
-第3快速疼里叶变换一 当然,上述统计与实际需要的运算次数稍有出入,因为某 些W可能是1或j,就不必相乘了,例如W=1,WxN2=-1, W4=j等就不需乘法。但是为了便于和其他运算方法作比较, 般都不考虑这些特殊情况,而是把W都看成复数,当N很大 时,这种特例的影响很小。 从上面的统计可以看到,直接计算DFT,乘法次数和加法 次数都是和N成正比的,当N很大时,运算量是很可观的,有 时是无法忍受的
第3章 快速傅里叶变换 当然，上述统计与实际需要的运算次数稍有出入，因为某 些WN nk可能是1或j，就不必相乘了，例如W0 N =1，W N Ｎ／２=-1， WN N/4=-j等就不需乘法。 但是为了便于和其他运算方法作比较， 一般都不考虑这些特殊情况，而是把WN nk都看成复数，当N很大 时，这种特例的影响很小。 从上面的统计可以看到，直接计算DFT，乘法次数和加法 次数都是和N2成正比的，当N很大时，运算量是很可观的，有 时是无法忍受的
-第3快速疼里叶变换一 例3-1根据式(3-1),对一幅N×N点的二维图像进行DFT变 换,如用每秒可做10万次复数乘法的计算机,当N=1024时,问 需要多少时间(不考虑加法运算时间)? 解直接计算DFT所需复乘次数为(M2)2≈1012次,因此用每秒 可做10万次复数乘法的计算机,则需要近3000小时。 这对实时性很强的信号处理来说,要么提高计算速度,而这 样,对计算速度的要求太高了。另外,只能通过改进对DFT的计 算方法,以大大减少运算次数
第3章 快速傅里叶变换 例3-1 根据式（3-1），对一幅N×N点的二维图像进行DFT变 换，如用每秒可做10万次复数乘法的计算机，当N=1024时，问 需要多少时间（不考虑加法运算时间）？ 解 直接计算DFT所需复乘次数为（N2 ) 2≈1012次，因此用每秒 可做10万次复数乘法的计算机，则需要近3000小时。 这对实时性很强的信号处理来说，要么提高计算速度，而这 样，对计算速度的要求太高了。另外，只能通过改进对DFT的计 算方法，以大大减少运算次数
-第5快速傅里叶度换 322改善途径 能否减少运算量,从而缩短计算时间呢?仔细观察DFT 的运算就可看出,利用系数Wx的以下固有特性,就可减少运 算 (1)W的对称性 m)* )=W nk (2)W的周期性 nk (n+Nk n(k+N)
第3章 快速傅里叶变换 3.2.2 改善途径 能否减少运算量，从而缩短计算时间呢？仔细观察DFT 的运算就可看出， 利用系数WＮ nk的以下固有特性，就可减少运 算量： （1） WN nk的对称性 nk N nk WN W − = * ( ) （2） WN nk的周期性 ( ) n(k N ) N n N k N n k WN W W + + = =
-第3快速疼里叶变换一 (3)W的可约性 nk W=w nmk k nk/m 另外 N/m (N-n)k W,WN2=-1W(+N2)=-W 这样,利用这些特性,使DFT运算中有些项可以合并,并能 使DFT分解为更少点数的DFT运算。而前面已经说到,DFT的运 算量是与M成正比的,所以N小越有利,因而小点数序列的 DFT比大点数序列的DFT的运算量要小。 快速傅里叶变换算法正是基于这样的基本思想而发展起来的 它的算法形式有很多种,但基本上可以分成两大类,即按时间抽 取( D ecimation in Time,缩写为DIT)法和按频率抽取 ( Decimation-in F requency,缩写为法s
第3章 快速傅里叶变换 （3） WN nk的可约性 n k m N m n k N nmk mN n k WN W W W / / = , = 另外 k N k N N N N n k N N n k N n N k WN = W = W W = − W = −W ( − ) ( − ) − / 2 ( + / 2) , 1, 这样，利用这些特性，使DFT运算中有些项可以合并，并能 使DFT分解为更少点数的DFT运算。而前面已经说到，DFT的运 算量是与N2成正比的，所以N越小越有利，因而小点数序列的 DFT比大点数序列的DFT的运算量要小。 快速傅里叶变换算法正是基于这样的基本思想而发展起来的。 它的算法形式有很多种，但基本上可以分成两大类，即按时间抽 ( Ｄecimation in Time，缩写为DIT）法和按频率抽取 （Decimation in Ｆrequency， 缩写为DIF）法
-第5快速傅里叶度换 3.3按时间抽取(DIT)的基-2FFT算法 3.31算法原理 设序列x(m)长度为N,且满足№=2M,M为正整数。按n的奇偶 把x(n)分解为两个M2点的子序列: 1)=x,(x)′=0l2…M x(2F)三x1(r (3-4) x(2r+
第3章 快速傅里叶变换 3.3 按时间抽取（DIT）的基-2 FFT算法 3.3.1 算法原理 设序列x(n)长度为N，且满足N=2 M ，M为正整数。按n的奇偶 把x(n)分解为两个N/2点的子序列： 1 2 0,1, , (2 1) ( ) (2 ) ( ) 2 1 = − + = = N r x r x r x r x r （3-4）