结论 FFT算法就是不断的把长序列DFT分解为几个短序 列DFT,并利用W和对称性和周期性来减少DT的 运算量。 快速付里叶变换(FFT)就是在此特性基础上发 展起来的,并产生了多种FFT算法,其基本上可 分为两大类: (1)按抽取方法分为:时域抽取法①IT;频域 抽取法(IF) (2)按“基数”分为:基-2F門T算法;基-4FFT 算法;混合基F門T算法;分裂基FFT算法
结论 FFT算法就是不断的把长序列DFT分解为几个短序 列DFT，并利用 对称性和周期性来减少DFT的 运算量。 快速付里叶变换（FFT）就是在此特性基础上发 展起来的，并产生了多种FFT算法，其基本上可 分为两大类： （1）按抽取方法分为：时域抽取法(DIT)；频域 抽取法(DIF) （2）按“基数”分为：基-2FFT算法；基-4FFT 算法；混合基FFT算法；分裂基FFT算法 kn WN
61基2时间抽取法 ●算法原理 设序列点数N=2M,M为整数。若不满足,则补零。 N为2的整数幂的FFT算法称基-2FF工算法。 ◎将序列x()按n的奇偶分成两组: 偶序列x()=x(2r) 奇序列x2(r)=x(2r+ 1)r=04…,N 即一组由偶数序号组成,另一组由奇数序号组成。 注意其长度为N/2 17
6.1 基2时间抽取法 17 算法原理 设序列点数 N = 2M ，M 为整数。若不满足，则补零。 将序列 x(n) 按 n 的奇偶分成两组： N 为 2 的整数幂的 FFT 算法称基-2 FFT算法。 即一组由偶数序号组成，另一组由奇数序号组成。 1 2 ( ) (2 ) 0,1, , 1 ( ) (2 1) 2 x r x r N r x r x r 偶序列 奇序列 注意其长度为 N/2
X(k)=∑x(m)W=∑xm形N+∑x(m)W n为偶数 n为奇数 N/2-1 ∑x(2r)W3+∑x(2r+1)w1 r+1)k =∑x(2r)2+W∑x(2r+1)2 X, (k+WRX.k 2
18 1 0 ( ) ( ) N n nk X k x n WN 为偶数 n为奇数 nk N n nk x(n)WN x(n)W / 2 1 0 (2 1) / 2 1 0 2 (2 ) (2 1) N r r k N N r rk x r WN x r W / 2 1 0 / 2 / 2 1 0 / 2 (2 ) (2 1) N r rk N k N N r rk x r WN W x r W 1 2 k X k W X k N
当k?’+1,,N-1时,令在、N+,L=0,2 NN N 观察 分为三部分 X(k)=X,(K)+WN X,(k) x, )=2) x(2r)WNa 第 第三第二 则 X1(k)=X1(+D=∑x(2r)W rl N ∑ x(2r)WN=X,) e =e =1 19
19 1 1 2 2 , , , N N 当 k N 时 0 1 2 2 , , , N N 令 k l l 观察 1 2 ( ) ( ) ( ) k X k X k WN X k 分 为 三部分 第 一 第三 第 二 则 2 2 2 1 1 2 2 ( ) 2 2 1 1 0 0 1 2 1 0 2 ( ) ( ) (2 ) (2 ) 2 (2 ) ( ) N N N N N N N r l r rl r r N rl N r N X k X l x r W x r W W x r W X l 2 2 2 2 2 2 1 N j r N N r j r W e e N N -1 2 kr 1 N 2 r=0 X (k) = x(2r)W
同理 X2(k)=X( N +D)=X2() 而 2丌N e 1) 因此 X(=X,(K)+WNX,(k) X(k+)=X1(k)-WX2(k) k=0,1,…,--1 2 因此:整个X(k)的计算,可以分解为前、后半部分的运算 而只要求出前一半,就可以由上式求出整个序列
20 因此：整个 X(k) 的计算，可以分解为前、后半部分的运算 。而只要求出前一半，就可以由上式求出整个序列。 同理 2 2 2 2 ( ) ( ) ( ) N X k X l X l 而 2 ( ) 2 2 2 ( 1) N N N l j k l j N W W W W e e N N N N 因此 1 1 2 2 ( ) ( ) ( ) ( ) ( ) ( ) 2 k N k N N X k X k W X X k k X k W X k 0,1, , 1 2 N k