乘法及NN1次复数加法运算。当N很大时,运算量相当可。 2、减少运算量的基本途径 因为(a+b)≥a2+b2,所以,把N点DFT分解为几个较短的DFT,可 是乘法次数大大减少。 旋转因子Wm具有明显的周期性和对称性,即 m+IN Wm+=eM =W Wm=WXN-m或者「WA-m=W 因此,可纵通过不断地把长序列的DFT分解成几个短序列的DFT,并利 W如的周期性和对称性来减少运算次数。 42.2时域抽取法基2FFT基本原理 FFT算法大致可以分为的域抽取法FFT(DIFT, Decimation-In- Time fft) 和颜域抽取法( DIF-FFT, Decimation- n-Frequency FFT)两大类。首先介绍 DIT-FFT算法。 1、序列分解 设序列x(n)的长度为N,且满足 N=2M,M为自然数 按n的奇偶把x(n)分解为两个点的子序列 x()=x(2).r=01-…N-1 x()2=x(2x+1,r=0.1…,1 则x(m)的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 为