同济大学：《数字信号处理（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

例:N=4×3×2 sn,rn2+n13+0=3×2n、+)n.x [p(n)ln=n+n1+n2=4×3m+4n1+ 0,1,2,3 0,1,2 0.1 (23)0=3×2×3+2×2+1=(321)2 「D(23 0=(23 4×3×1+4×2+3=(23 2×3×4 10 (3)=3×2×0+2×1+1=(01 43x 110 4×3×1+4×1+0=(18 0 (14)0=3×2×2+2×1+0=(210 [P(14)l。=(012)23x4×3×0+4×1+2=(6)

  10 2 2 3 1 3 0 2 1 0 n  n r r  n r  n  3 2n  2n  n   0 1 2 1 1 2 0 1 0 10  n   n rr  n r  n  4 3n  4n  n   0 n  0,1 2 n  0,1,2,3 1 n  0,1,2 1 2 3 例：N  43 2  rr r     10 4 3 2 23 3 2 3 2 2 1 321                10 2 3 4 10  23 123 4 3 1 4 2 3 23                   10 4 3 2 3 3 2 0 2 1 1 011                10 2 3 4 10  3 110 4 3 1 4 1 0 18                   10 4 3 2 14 3 2 2 2 1 0 210                10 2 3 4 10  14 012 4 3 0 4 1 2 6              

2、N=的快速算法 n1=0.1 N=rn n=n,2+no n为r;进制 0,1, 1 N=Fk=万+k=0,…,n-1 k为r进制 k=0.1 N=P2行r列n1行序号n列序号 N=F行2列k0行变量k列变量

2、N  r1r2的快速算法 N 1 2  rr 1 2 0 n  n r  n 1 1 2 0 2 0,1, , 1 0,1, , 1 n r n r n r          为 进制 1 2 1 0 1 0 1, , 1 0,1, , 1 k r k r k r          ， N  r2r1 k  k1r1  k0 为 进制 N 1 2  rr N 2 1  r r r1行 r2列 1 n 行序号 0 n 列序号 1r 2 行r 列 0 k 行变量 1 k 列变量

X(k)=X(rk,+ko)=X(k,ko)=2x(n)wN ∑∑x(n1+n。) (2n+0)(k+k) 0=01=0 ∑∑x(n1,n)WNW何 0=0n1=0 ∑x(mn,n)H WnWw团 i ∑[X(k k. n )W noko w o =∑X1(kn)Wm=X2(,k) o=0

        1 1 1 0 1 0 0 , N nk N n X k X r k k X k k x n W             2 1 2 1 0 1 1 0 0 1 1 1 2 1 0 0 0 r r r n n r k k N n n x r n n W            2 1 2 1 0 1 0 1 0 0 1 2 1 1 0 1 1 1 1 0 0 0 , r r r n k r n k n k rr n k N N N N n n x n n W W W W         2 1 1 0 0 0 0 1 1 2 0 1 1 1 1 0 0 0 , r r n k n k n k r N r n n x n n W W W                     2 0 0 0 1 2 0 1 1 0 0 0 , r n k n k N r n X k n W W            2 0 1 2 0 1 ' 1 0 0 2 0 1 0 , , r n k r n X k n W X k k     

N=r;的DFT算法 1)改写x(m)成x(m1,n0) n,=0.1 x(n)=x(r2n,+no)=x(n, no) n=0.1…z-1 )做个点DFT,得X1(ko,m) n为参量,输入变量n,输出变量k的点DFT (3)N个X1(k,n)×W(旋转因子)→>X1(ko,m0) ()做个2点DF7,得X2(k0,k) k为参量,输入变量n,输出变量k的2点DFT 5)整序X(k,k0)=X(k)k=nk+k

N  r1r2 的DFT 算法 (1) 改写 xn 成 x n1 ,n0  xn  x r2n1  n0   x n1 ,n0  1 1 0 2 0,1, , 1 0,1, , 1 n r n r          (2) 做 个 点DFT ，得 为参量，输入变量 ，输出变量 的 点 DFT 2r 1r   1 0 0 X k ,n 0 n 1 n 0 k 1r (3) N个 X1 k0 ,n0  WN n0k0（旋转因子）   ' 1 0 0  X k ,n (4) 做 个 点DFT，得 为参量，输入变量 ，输出变量 的 点DFT 1r 2r   2 0 1 X k ,k 0 k 1 k 0 n 2r (5) 整序     1 0 X k ,k  X k 1 1 0 k  r k  k

例N 4×2=8 2n,+ 0,1,2,3 0.1 k=4k,+k k,=0.1 kn=0,1,2,3 X1(kn)=∑x(n1,n形M=∑x(1,n0)W4 ni X1(,n0)=X1(ko,n0) nok (k2,n) X2(kk)=∑X(,n0)W=∑X1(0,n0 0=0 X(ki, ko)=X(k)

1 2 例 N  rr  4 2  8 1 0 n  2n  n 1 0 0,1,2,3 0,1 n n      1 0 k  4k  k 1 0 0,1 0,1,2,3 k k            1 1 0 1 0 1 1 1 1 3 1 0 0 1 0 1 0 4 0 0 , , , r n k n k r n n X k n x n n W x n n W              0 0 0 0 ' 1 0 0 1 0 0 1 0 0 8 , , , n k n k X N k n  X k n W  X k n W       2 0 1 0 1 2 0 0 1 1 ' ' 2 0 1 1 0 0 1 0 0 2 0 0 , , , r n k n k r n n X k k X k n W X k n W            1 0  X k ,k  X k