又因为Wx=1,因此最终可得 X(k)=A(k)+WFB(k) A(k)-WkB(k) k=0,1,2,… (2.211) A(0) X(0) X(1) A(2 X(2) A(3) B(0) X(4) B(1) X(5) B(2) X(6) B(3) X(7) 图498分割一次后的A(k)、B(k)及X(k)之间的关系(N=8)
又因为 2 = −1 ，因此最终可得 N WN ( ) ( ) ( ) ( ) ( ) 1 2 0,1,2, 2 = − = − + = + k N A k W B k N X k X k A k W B k k N k N （2.211） 图4.98 分割一次后的A(k)、B(k)及X(k)之间的关系（N=8）
按照上述思路继续对A(k)和B(k)作奇偶序列分解 令r=2,r=2+1,|=0,1,…N4-1,则有: A(k)=∑x(41)W4+∑x(41+2m241 =0 ∑x(4)W+W∑x(41+2)w =0 令 C()=∑x(4)W k=0.1..N (4212) % D(k)=∑x(4C+2) k=0.1.… 4.213) A(k=c(k)+wk dth )k=01,…M (4214) N Alk =C(k)-Wk∠D(k)k=0,1 1(4215)
按照上述思路继续对A(k)和B(k)作奇偶序列分解。 令r=2l，r=2l+1，l=0,1, …,N/4-1，则有： 令 则 ( ) ( ) ( ) ( ) ( ) ( ) − = − = − = + − = = + + = + + 1 4 0 2 4 1 2 0 4 1 4 0 2 1 2 1 4 0 2 2 4 4 2 4 4 2 N l l k N k N N l l k N N l l k N N l l k N x l W W x l W A k x l W x l W ( ) ( ) 1 4 4 0,1, , 4 1 4 = = − − = C k x W k k N N N o （4.212） ( ) ( ) 1 4 4 2 0,1, , 4 1 4 = + = − − = D k x W k k N N N o （4.213） ( ) ( ) ( ) 1 4 0,1, 2 A k = C k +W D h k = N − k N （4.214） ( ) ( ) 1 4 0,1, 4 2 = − = − + C k W D k k N N A k k N （4.215）
同样,令 E(k)=∑x(4+1)W k=0.1 4.216) Flk x(4C+3)W ck k=0,1,… (4217) 则有: B(k)=E(k)+WF(k)k=0,1,… 4218) k+ N\=E( )-WkF(k)k=0,…y4-1 4.219)
同样，令 则有：( ) ( ) 1 4 4 1 0,1, 4 1 4 = + = − −= E k x W k k N N N o ( ) ( ) 1 4 4 3 0,1, 4 1 4 = + = − −= F k x W k k N N N o （4.216 ） （4.217 ） ( ) ( ) ( ) 1 4 0,1, 2 B k = E k + W F k k = N − kN （4.218 ） ( ) ( ) 1 4 0,1, 4 2 = − = − + E k W F k k N N B k kN （4.219 ）
对于一个N=8的序列,此时的C(k)、D(k)、E(k)和 F(k)均已为两点的序列,无需再分,此时有 x(0) C(0) A(0) X(0) (4) C(1) A(1) X(1) D(0) A(2) X(2) x(6) D(1) A(3) ECo) WR 1B(0) X(3) x(1) X(4) x(5) E(1) B(1)W8 F(0) b(2)W X(5) F(1)W X(6) x(7) B(3)W X(7) 图499FFT时间抽取算法信号流图(N=8) C(0)=x(0)+x(4),E(0)=x(1)+x(5) C(1)=x(0)-x(4),E(1)=x(1)-x(5) D(O)=x(2)+x(6),F(0)=X(3)+x(7) D(1)=x(2)-x(6),F(1)=x(3)-x(7)
对于一个N=8的序列，此时的C(k)、D(k)、E(k)和 F(k)均已为两点的序列，无需再分，此时有 图4.99 FFT时间抽取算法信号流图（N=8） C(0)=x(0)+x(4)，E(0)=x(1)+x(5) C(1)=x(0)-x(4)，E(1)=x(1)-x(5) D(0)=x(2)+x(6)，F(0)=x(3)+x(7) D(1)=x(2)-x(6)，F(1)=x(3)-x(7)
在F「T的整个运算过程中,每两个等式的运算过程 可以用一个形似蝴蝶结的“X形结构图来表示,八 个等式对应于四个蝶形结构,因此这种信号流程图 称为F「的蝶形运算流程图,将这种运算的基本单 元称为蝶形运算单元。 p xm(q) 图4100蝶形运算单元
在FFT的整个运算过程中，每两个等式的运算过程 可以用一个形似蝴蝶结的“X”形结构图来表示，八 个等式对应于四个蝶形结构，因此这种信号流程图 称为FFT的蝶形运算流程图，将这种运算的基本单 元称为蝶形运算单元。 图4.100 蝶形运算单元