大学化学第二章课件

1、六、基 -4FFT算法 当混合基FFT算法中 时， 即为基-4FFT算法，n、k都为4进制数 12 4 L rrr 个 点DFT 乘N个旋转因子 1 r 1 N r 个 点DFT 乘N个旋转因子 2 r 2 N r 个 点DFT L r L N r X k整序 2 164N 10 10 4 4 nnn kkk 1 00 00 1 01 33 44 10 00 , n kn kn k NNN nn X kx n n WWW 1 0 1 3 100104 0 1) , n k n Xk nx n n W 0 0 100100 2) , n k N Xk nXk n W 0 1 0 3 201100

2、4 0 3) , n k n Xk kXk n W 0000 1040404040 0,0,1,2,3,XnW xnW xnW xnW xn 0123 1040404040 1,0,1,2,3,XnW xnW xnW xnW xn 10 ,n k1) 的4点DFT 1 0 1 3 100104 0 , n k n Xk nx n n W 0246 1040404040 2,0,1,2,3,XnW xnW xnW xnW xn 0202 40404040 0,1,2,3,W xnW xnW xnW xn 0369 1040404040 3,0,1,2,3,XnW xnW xnW xnW xn 0

3、321 40404040 0,1,2,3,W xnW xnW xnW xn 0000 100 4444 0123 100 4444 0202 100 4444 0321 100 4444 0,0, 1,1, 2,2, 3,3, XnxnWWWW XnxnWWWW XnxnWWWW XnxnWWWW 0 0 0 0 0, 1 111 1, 11 2, 1111 3, 11 xn xnjj xn xnjj 的四进制数 按二进制倒位序排列成 0 k0,1,2,3 0,2,1,3 100 100 100 100 0,0, 1 111 2,1, 1111 1,2, 11 3,3, 11 Xnxn Xnx

4、n Xnxnjj Xnxnjj 0 0 100100 2) , n k N X k n WXk n 01 ,n k 3)的4点 DFT 0 0 0 00000 201016 4444 0123 201016 4444 20202 201016 4444 30321 201016 4444 ,0,0 ,1,1 ,2,2 ,3,3 k k k XkX kWWWWW XkX kWWWWW XkX kWWWWW XkX kWWWWW 0 0 0 0 1016 1016 2 1016 3 1016 ,0 1 111 ,1 11 ,2 11 11 ,3 11 k k k X kW X kWjj X kW X kWjj 2 3 31log 48 F N mLNN 0 1 N W 一个4点FFT不需乘法，只需3次乘旋转因子 （ 除外） 2