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