同济大学：《数字信号处理（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                                     

2)X,(ko, no )Wo=X,(ko, no) 3)(,k)的4点DFT (,0)1「? W4 WA WX(,)ne X(4,1)ww4w2w‖x(1)形 X(2)|w0W2WW‖x(,2)B X(4,3)LWw?w2W⊥x(k,3)」 1X(k20)形 1111 X1(k21)W6 X,(k, 2W 1(k,3)W78

    0 0 ' 1 0 0 1 0 0 2) , , n k X N k n W  X k n 3) n0 ,k1 的4点 DFT                 0 0 0 0 0 0 0 0 2 0 4 4 4 4 1 0 16 0 1 2 3 2 0 4 4 4 4 1 0 16 0 2 0 2 2 2 0 4 4 4 4 1 0 16 0 3 2 1 3 2 0 4 4 4 4 1 0 16 ,0 ,0 ,1 ,1 ,2 ,2 ,3 ,3 k k k X k W W W W X k W X k W W W W X k W X k W W W W X k W X k W W W W X k W                                        0 0 0 0 1 0 16 1 0 16 2 1 0 16 3 1 0 16 1 1 1 1 ,0 1 1 ,1 1 1 1 1 ,2 1 1 ,3 k k k X k W j j X k W X k W j j X k W                      

t) x(nI, n) XI(ko, no) X2(ko, k1) X(k) =x(0,0)一 X2(0,0)=X(0) =x(0,1) X2(0,2)=X(8) F=x(0,2) X2(0,1)=X(4) °。X20.3)=X(12) (1,0) X2(2,0)=X(2) 千→0X(2.2)X(10 (1,2) 2(2,1)=Y(6 (1,3) X2(2,3)=X(14) N(83=x(2,0)→d →。X2(1,0)=X(1) 9)=x(2,1) X2(1,2)=X(9) (1=x(2,2) X2(1,1)=X(5) 11)=x(2,3 X2(1,3)=X(13) 12)=x(3,0) X2(3,0)=X(3) x(13)=x(3,1) X2(3,2)=X(11) (14)=x(3,2) X2(3,1)=X(7) x(15)=x(3,3) X2(3,3)=X(15) 图4-22按时间抽选基-4FFT流图

基-4FFT运算量:N=4 个4点FF不需乘法,只需3次乘旋转因子 (W0=1除外) 每级有N4个4点FFT,共L级(L-1级要乘旋转 因子) m=3××(L-1)≈。Ng2N ∧ N 而基-2 FFT m=-log,N

  2 3 3 1 log 4 8 F N m    L  N N 0 1 WN  一个4点FFT不需乘法，只需3次乘旋转因子 （ 除外） 2 log 2 F N 而基 -2FFT m  N 4 L 基-4FFT运算量： N  每级有N/4个4点FFT，共L级（L-1级要乘旋转 因子）