式(365)和式(36)把原来N点DFT的计算分解成两个N2点DFT的计 算。照此可进一步把每个N2点DFT的计算再各分解成两个N4点 DFT的计算。具体说来,是把{x(0),x(2),x(4),x6}和x(1),x(3), x5,X7分为0),×4)1x(2),x6和{1),x(5)X3,x7)。这样, 原信号序列被分成{x0),x4)|x(2),x(6)×(1),x(5)x(3),x(7}4个2项 信号。G(k)和Hk)分别计算如下 N/4-1 ()=∑g()W2=∑g(2W2+(4+1)w N/4-1 N/4-1 =∑(2)W,+W∑g(l+1)W4 0 M(k)+W致N(k) (3.67) N/4-1 Gk+ N ∑g(2D)w以++W+)·∑g(2+1)W以 N/4-1 =∑g(2)w4-W∑g(2l+1)WA 368) M(k)-W砖N N (k),k=0,1, 1
式(3.65)和式(3.66)把原来N点DFT的计算分解成两个N/2点DFT的计 算。照此可进一 步把每个N/2点DFT的计算再各分解成两个N/4点 DFT的计算。具体说来，是把{x(0)，x(2)，x(4)，x(6)}和{x(1)，x(3)， x(5)，x(7)}分为{x(0)，x(4) | x(2)，x(6)}和{x(1)，x(5) | x(3)，x(7)}。这样， 原信号序列被分成{x(0)，x(4) | x(2)，x(6) I x(1)，x(5) I x(3)，x(7)}4个2项 信号。G(k)和H(k)分别计算如下: (3.67) (3.68)
N/4-1 (k)=∑h()W+W∑h(21+1)W川 0 (369) P(k)+wQ(k) N/4-1 N/4-1 (+2)-24020w22+)W 3.70) P(k)-wwQck) 这样,用式(367)~(3704个公式就可计算图315中的两组N2点 DFT。图316所示的是其中一组GK的计算 x(0) M(0) 点 DFT c(1) x(2) NO 点 G(2) x(6) D C(3) Ww. -1 图316 将 N点DFT计算分解为两个点DFT的计算渡程图(N=8
(3.69) (3.70) 这样，用式(3.67)～(3.70)4个公式就可计算图3.15中的两组N/2点 DFT。图3.16所示的是其中一组G(k)的计算
将图3.16与图3.15所示的信号流程图合并,便得到图3.17所示的信 号流程图。 点 X(0) DET X(1) x(2) N X(2) 4 点 DET X(3) N 点 X(4) 4 x(5) DET X(5) wo W (3)oN X(6) 4 点 x(7) DET X(7) 图3.17将图3.16移入图315的结果 因为N=8,所以上图中N4点的DFT就是2点的DFT,不能再分解了
将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信 号流程图。 因为N=8，所以上图中N/4点的DFT就是2点的DFT，不能再分解了