的一种快速算法以后,情况才发生了根本的变化。*4.2基2FFT算法4.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况,对某一个k值,直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。因此,N点DFT的复乘次数等于N2,加法次数N(N-1).当N>>1时,,即N点DFT的乘法和加法运算次数均与N2成正比,当N较大时,运算量相等可观。(4.2.1)*注意:通常将算术乘法和算术加法的次数作为计算复杂性的度量,因为这种方法使用起来很简单。如果在计算机上用软件实现这些算法,则乘法和加法的次数就直接与计算速度有关。但是,在常用的VLSI实现时,芯片的面积和功率要求往往是最重要的考虑因素,而它们有可能与算法的运算次数没有直接的关系。*显然,把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子WmN具有明显的周期性、对称性和可约性。其周期性表现为(4.2.2)其对称性表现为或者*可约性表现在:*4.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两大类:时域抽取法FFT(DecimationInTimeFFT,简称DIT-FFT)和频域抽取法FFT(DecimationInFrequencyFFT,简称DIF-FFT)。下面介绍DIT-FFT算法。设序列x(n)的长度为N,且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列*则x(n)的DFT为由于所以*其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即(4.2.5)(4.2.6)由于X1(k)和X2(k)均以N/2为周期,且,所以X(k)又可表示为(4.2.7)(4.2.8)*图4.2.1蝶形运算符号X1(k)X2(k)WNKX1(k)+WNKX2(k)X1(k)-WNKX2(k)*
全文预览
