乘法及N(N1执复数加法运算。当N很大时,运算量相当可。 2、减少运算量的基本途径 因为(a+b)≥a2+b2,所以,把N点DFT分解为几个较短的DFT,可 是乘法次数大大减少。 旋转因子W具有明显的周期性和对称性,即 rm+/N 27(m+) 或者[-丁 WN2=-WN 因此,可纵通过不断地把长序列的DFT分解成几个短序列的DFT,并利用 W的期性和对称性水减少运算次数 422时域抽取法基2FFT基本原理 FFT算法大致可以分为时域抽歌法FFT( DIT-FFT, Decimation-In- Time fft) 和频域抽取法( DIF-FFT, Decimation-In-Frequency FFT)两大类。首先介绍 DIT-FFT算法。 1、序列分解 设序列x(n)的长度为N,且满足 N=2M,M为自然数 按n的奇偶把x(n)分解为两个点的子序列 x()=x(2),r=0.1.N x2(r)=x(2r+ 则x(n)的DFT为乘法及 N(N-1)次复数加法运算。当 N 很大时，运算量相当可观。 2、减少运算量的基本途径 ⚫ 因为 ( ) 2 2 2 a b a b +  + ，所以，把 N 点 DFT 分解为几个较短的 DFT，可 是乘法次数大大减少。 ⚫ 旋转因子 m WN 具有明显的周期性和对称性，即 ( ) 2 2 j m lN j m m lN m N N W e e W N N   − + − + = = = (2) * m N m N m m W W W W N N N N − − − = =   或者   (3) 2 N m m W W N N + = − 因此，可以通过不断地把长序列的 DFT 分解成几个短序列的 DFT，并利用 kn WN 的周期性和对称性来减少运算次数。 4.2.2 时域抽取法基 2FFT 基本原理 FFT 算法大致可以分为时域抽取法 FFT（DIT-FFT, Decimation-In-Time FFT） 和频域抽取法（DIF-FFT, Decimation-In-Frequency FFT）两大类。首先介绍 DIT-FFT 算法。 1、序列分解 设序列 x n( ) 的长度为 N，且满足 2 , M N M = 为自然数 ⚫ 按 n 的奇偶把 x n( ) 分解为两个 2 N 点的子序列 1 ( ) (2 , 0,1, , 1 ) 2 N x r x r r = = − 2 ( ) (2 1 , 0,1, , 1 ) 2 N x r x r r = + = − 则 x n( ) 的 DFT 为