同济大学：《数字信号处理（DSP）》课程教学资源（PPT课件讲稿）第四章 快速傅里叶变换（6/9）

Q六4F算法 当混合基FFT算法中r=n2…=r1=4时, 即为基-4FF算法,n、k都为4进制数 N个点DFT乘N个旋转因子 N个点DFT乘N个旋转因子 N个点DFT整序少X(k)

六、基 -4FFT算法 当混合基FFT算法中 时， 即为基-4FFT算法，n、k都为4进制数 1 2 4 L r  r  r  个r1 点DFT 乘N个旋转因子 1 N r 个r2点DFT 乘N个旋转因子 2 N r 个rL点DFT L N r 整序Xk 

4n,+ N=16=42 k=4k,+k X(k)=∑∑x(n1,n0)WW 0=0n 1)X1(k,n)=∑x(n,n) 0 2)X1(k2n0)=X1(k0,n0)WN 3)X2(kk)=∑X1(k0,n0)W

2 N  16  4 1 0 1 0 4 4 n n n k k k            1 0 0 0 0 1 0 1 3 3 4 4 1 0 0 0 , n k n k n k N N N n n X k x n n W W W          1 0 1 3 1 0 0 1 0 4 0 1) , , n k n X k n x n n W        0 0 ' 1 0 0 1 0 0 2) , , n k X N k n  X k n W     0 1 0 3 ' 2 0 1 1 0 0 4 0 3) , , n k n X k k X k n W   

1)(n,k)的4点DFT X,(k X 1(010)=W4x(0,n)+Wx(1,n0)+W4x(2,n)+W4x(3mn) (h)=W4x(0.n)+W4x(,n1)+W2x(,mn)+W1x(3,n3) X(27)=Wx(m)+W2x(n)+W4x(2,n0)+Wx(3m) Wx(O,n0)+W2x(,n)+W4x(2,n)+W2x(3,n) X1(3n)=W4x(0.n)+W4x(,n0)+Wx(2,m)+Wx(3,n0) Wx(O0n0)+Wx(1,n)+W2x(2,n)+W4x(3m3)

          0 0 0 0 1 0 4 0 4 0 4 0 4 0 X 0,n W x 0,n W x 1,n W x 2,n W x 3,n           0 1 2 3 1 0 4 0 4 0 4 0 4 0 X 1,n W x 0,n W x 1,n W x 2,n W x 3,n 1) n1 ,k0  的4点DFT     1 0 1 3 1 0 0 1 0 4 0 , , n k n X k n x n n W              0 2 4 6 1 0 4 0 4 0 4 0 4 0 X 2,n W x 0,n W x 1,n W x 2,n W x 3,n         0 2 0 2 4 0 4 0 4 0 4 0  W x 0,n W x 1,n W x 2,n W x 3,n           0 3 6 9 1 0 4 0 4 0 4 0 4 0 X 3,n W x 0,n W x 1,n W x 2,n W x 3,n         0 3 2 1 4 0 4 0 4 0 4 0  W x 0,n W x 1,n W x 2,n W x 3,n

X X1(1,n) X(2, n X1(3, no)W4 Wi x(o

                0 0 0 0 1 0 4 4 4 4 0 0 1 2 3 1 0 4 4 4 4 0 0 2 0 2 1 0 4 4 4 4 0 0 3 2 1 1 0 4 4 4 4 0 0, 0, 1, 1, 2, 2, 3, 3, X n W W W W x n X n W W W W x n X n W W W W x n X n W W W W x n                                        0 0 0 0 0, 1 1 1 1 1, 1 1 2, 1 1 1 1 3, 1 1 x n j j x n x n j j x n                           

的四进制数(0.23)按二进制倒位序排列成(0213) X(n)「1 I x(o X1(2,n0)1 1-1x(1,n) X1(1,n -1j‖x(2,n0 x1(3,n x(3 (0,no) X1(0,n10) (1,no) oX1(2,n0) (2,no) XI(1, e) 3,no) X1(3,no) 图4-21一个基-4FFT基本运算的信号流图

k0的四进制数0,1,2,3按二进制倒位序排列成0,2,1,3                 1 0 0 1 0 0 1 0 0 1 0 0 0, 0, 1 1 1 1 2, 1, 1 1 1 1 1, 2, 1 1 3, 3, 1 1 X n x n X n x n X n j j x n X n j j x n                                     