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

Q五,、N为合数的厂算法 基-2FFT算法:N=2 当N≠2时 ◆补零使满足N=2 直接DFT方法/CZ方法:当要求准确的N点 DFT,且N是素数时 混合基FFT算法:N是复合数

¨ 直接DFT方法 / CZT方法：当要求准确的N点 DFT，且N是素数时 五、N为复合数的FFT算法 ——混合基算法 基-2FFT算法： 2 L N  2 L 当N  时 ¨ 补零使满足 2 L N  ¨ 混合基FFT算法：N是复合数

1、整数的多基多进制表示形式 (1)二进制:24=N 自然序n=(n1=n2…n2nn)2 其中n=0,1 i=0.…·L-1 倒位序[P(n)2=(nn…n=22-)2 )1n=n1-12-+n1-2-2+…+n22+n12+n [p(n)ln=n1241+n12+…+n-22+n

1、 整数的多基多进制表示形式  1 2 2 1 0  L L 2 n n n n n n 自然序        0 1 2 2 1 2 L L 2  n  n n n n  n    倒位序      1 2 2 10 12 2 2 2 2 1 2 0 L L n nL nL n n n               1 2 0 1 2 1 10 2 2 2 L L  n n n nL nL                2 L （1）二进制：  N 0,1 i 其中 n  i  0,,L 1

(2)r进制:N=r n=(n, n L L-2 其中n2=0 [p(n)=(nn2…n121n i=0.…·L-1 L F+n1F+…+n2F十n1+n ()l=n41+n12+…+n127+n 10

（2）r进制： L N  r   1 2 2 1 10 1 2 2 1 0 L L L L n n r n r n r n r n            1 2 0 1 2 1 10 L L L L  n n r n r n r n                L 1 L 2 2 1 0  r n n n n n n     0, , 1 i 其中 n   r  i  0,,L 1    0 1 2 L 2 L 1 r r  n  n n n n  n      

(3)多基多进制(混合基):N=B…r o=n-1(23…)+n2(r4…)+…+nF+n 其中n,-1=0,l 0.1. 即n1=0,12…,r2-1 0.…,L-1 [p(m) =(nan1…nn L-1)n…n [p(m)]=n(n∵-)+n(2…2)+…+m+n2

（3）多基多进制（混合基）： N 1 2 L  rr r   1 2 1 2 1 0 L L L rr r n n n n n        10 L 1  2 3 L  L 2  3 4 L  1 L 0 n n r r r n r r r n r n         1 1 0 1 , 1 L n r 其中   ，，  2 2 0,1, , 1 L n r     0 0,1, , 1 L n  r    0,1, , 1 i L i n r 即     i  0,,L 1   0  1 2 1  1  1 2 2  2 1 1 10 L L L L  n n rr r n rr r n r n                     2 1 2 1 0 1 2 1 L L r r r L L r r r  n n n n n          

例:N=4×4=r2(n)0=n2+n0=4n1+n0 (m)=n+n1=4n+ 10 n=0.12.3 (5)=4×1+1=(1) n1=0,12,3 [P(5)l。=(1)x4=4×1+1=(5) (6)o=4×1+2=(12) 4×4 [()l0=(21)=4×2+1=(9) (1)=4×2+3=(23) [p(1)]l=(32) 4×3+2=(14 4×4

例： 1 2 N  4 4  rr     10 4 4 5 4 1 1 11            10 4 4 10  5 11 4 1 1 5               10 4 4 6 4 1 2 12          10 4 4 11 4 2 3 23            10 4 4 10  6 21 4 2 1 9                 10 4 4 10 p 11 32 4 3 2 14             10 1 2 0 1 0 n  n r  n  4n  n   0 1 1 0 1 10  n   n r  n  4n  n   0 n  0,1,2,3 1 n  0,1,2,3