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

Q,分做算 对偶序号使用基2F算法,对奇序号使用基 4FF算法,称分裂基FFT算法 针对N=2的算法中具有最少乘法次数,且 同址运算 x(n)N=24将x(m)分成三个序列。 x1 (=x(4/+1) N 1=0. (=x(4+3)

七、分裂基FFT算法 对偶序号使用基-2FFT算法，对奇序号使用基- 4FFT算法，称分裂基FFT算法 针对 的算法中具有最少乘法次数，且 同址运算。 2 L N xn N  2 L 将 xn分成三个序列。 x1 r  x2r 0, , 1 2 N r            2 3 4 1 0, , 1 4 3 4 x l x l N l x l x l          

)=(o ∑x(2)W+∑x(41+1)41+x(41+3) r=0 ∑x()WM2+W∑x()W4+W∑x()JW X(k)+W X2(k)+WXs(k) 偶序号的二点DFT 奇序号的一点DFT 4

    1 0 N nk N n X k x n W              1 1 1 2 4 4 2 4 1 4 3 0 0 0 2 4 1 4 3 N N N rk l k l k N N N r l l x r W x l W x l W                    1 1 1 2 4 4 3 1 2 2 4 3 4 0 0 0 N N N rk k lk k lk N N N N N r l l x r W W x l W W x l W                  3 1 2 3 k k X N N  k W X k W X k 偶序号的 点DFT 2 N 奇序号的 点DFT 4 N

利用周期性X()分成四段 K(k)=X1(k)+WK2()+WX(k)k=0 N k X|k+-形x2()+wxx() 4 N Xk+ X, (k)-Wn X2(k) -W X, (k) 3N XIk+ X k+ +jW X2()-jWNk X,(k)

利用周期性 X k 分成四段：         3 1 2 3 k k X N N k  X k W X k W X k     3 1 2 3 4 4 k k N N N N X k X k jW X k jW X k                     3 1 2 3 3 4 4 k k N N N N X k X k jW X k jW X k                       3 1 2 3 2 k k N N N X k X k W X k W X k           0, , 1 4 N k   

X1(0) X(0) 点DF7 0)W X(亏) 点DF7 X3(0) WN 点DFT 图4-23分裂基FFT算法(时间抽选)的第一级流图 图4-24分裂基FFT算法的一个基本蝶形运算

同样对x()、x2(k)、x()作进一步分解 N=16=42X(k)的第一级分解得4个分裂基 x(k)的第二级分解得2个分裂基。 个基4的4点DFT和2个基-2的4点DFT X2(k)和X3(小)的第二级分解分别是基4的4点DFT 基-4的4点DFT 2点DFT 2个分裂基 2点DFT 基-4的4点DFT 4个分裂基 基-4的4点DFT

N 16  4 2 X k的第一级分解得4个分裂基   X2 k   X3   k X1 同样对 k 、 、 作进一步分解。 X2 k和X3 k的第二级分解分别是基-4的4点DFT。   X1 k 的第二级分解得2个分裂基。 一个基-4的4点DFT和2个基-2的4点DFT

x10 X10 x8 1 4」 X12 x12 Ⅺ13 x|2 X14 x101 15l x|6 16 x141 X17 X18 19 X19 J x5」 X10 X11 x|3 X12 X13 x{7 X14 J x[15 Ⅺ15 图4-26N=2=16分裂基FF算法(按时间抽选)的流图 (输入二进制倒位序,输出正常顺序 注:上图只用虚线框表示了一级的到L结构

运算量:N=2 基-2,基-4等基本碟形 结都没有乘法,只有每 L=2 B.=0 个分裂基有两次复乘。 L=3 B.=2 B4=B3+2+2B2=6 B.=B,+222+2B,=18 分裂基碟形数:B=B+22+2B2 mx<og2、3 Nlog n<-Nlog w

基-2，基-4等基本碟形 结都没有乘法，只有每 个分裂基有两次复乘。 运算量： 2 L N  L  2 2 B  0 L  3 3 B  2 L  4 2 4 3 2 2 2 6 L B B B      L  5 2 5 4 3 2 2 18 L B B B      分裂基碟形数： 2 1 2 2 2 L BL BL BL       2 1 log 3 mF  N N 2 2 3 1 log log 8 2  N N  N N