5.序列的倒序 DT一FFT算法的输入序列的排序看起来似乎很乱， 但仔细分析就会发现这种倒序是很有规律的。由于 N=2M,所以顺序数可用M位二进制数(1M2.1o) 表示。 000 0 100 又 010 2 110 6 (n2n no) 001 1 1015 011 3 111 7 图4.2.7形成倒序的树状图N=23)
DIT―FFT算法的输入序列的排序看起来似乎很乱， 但仔细分析就会发现这种倒序是很有规律的。由于 N=2 M ，所以顺序数可用M位二进制数(nM-1nM-2.n1n0 ) 表示。 图4.2.7 形成倒序的树状图(N=23 ) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (n 2 n 1 n 0 ) 2 000 0 4 2 6 1 5 3 7 100 010 110 001 101 011 111 5. 序列的倒序
第4章快速傅立叶变换(FFT) 4.2.5频域抽取法FFT(DIF FFT) 染算法原理 一)N/2点DFT V-1 X(k)=∑x(n)WWk 2=0 N-1 -∑x四w+乞xmm N-1 n=0 =N/2 N-1 (m)w+∑xn+X N-1 2=0 n=(
4.2.5 频域抽取法FFT（DIF_FFT) 算法原理 − = = 1 0 ( ) ( ) N n nk X k x n WN − = − = = + 1 / 2 1 0 ( ) ( ) 2 N n N nk N n nk x n WN x n W N − = + − = = + + 1 0 ( ) 1 0 2 2 2 ) 2 ( ) ( N N N n n k N n n k N W N x n W x n (一)N/2点DFT 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) 氢w+u+w]g w=e=-1,W=(-1) =0 k=0,1,.,W-1
n k N n k WN W N x n x n N N − = = + + 1 0 2 2 ) 2 ( ) ( 1 , 2 = = − − j N W e N k k N N W ( 1) 2 = − n k N n k W N X k x n x n N − = = + − + 1 0 2 ) 2 ( ) ( ) ( 1) ( k = 0,1, ,N −1 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) k为偶数时： X(2r)= x(n)+x(n+ n x(n)+x(n+ )) r=0,1,-1 =0 k为奇数时： (n) X(2r+0=】 [m-+ n(2r+1) x,(n)
nr N n W N X r x n x n N 2 1 0 2 ) 2 (2 ) ( ) ( − = = + + k为偶数时： nr n N N W N x n x n 2 2 1 0 ) 2 ( ) ( − = = + + 0,1, , 1 2 = − N r ( ) x1 n k为奇数时： nr n n N N N W W N x n x n 2 2 1 0 ) 2 ( ) ( − = = − + ( ) x2 n 0,1, , 1 2 = − N r (2 1) 1 0 2 ) 2 (2 1) ( ) ( + − = + = − + n r N n W N X r x n x n N 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换 (FFT) N x(n)=x(n)+x(n+ 2 n=0,1,.,×-1 xw）=w）-n+之w X(2r)= ∑xw N r=0,1,-1 2 X(2r+1)= x2(n)w 先截短的x《n)构造两信号x1(n)和 2(n),做N/2的DFT,即可
0,1, , 1 )] 2 ( ) [ ( ) ( ) 2 ( ) ( ) ( 2 2 1 = − = − + = + + N n N n W N x n x n x n N x n x n x n 0,1, , 1 (2 1) ( ) (2 ) ( ) 2 1 2 0 2 1 2 0 1 2 2 = − + = = − = − = N n r N n n r N n r X r x n W X r x n W N N 先截短的x(n)构造两信号x1 (n)和 x2 (n),做N/2的DFT，即可。 第4章 快速傅立叶变换（FFT）