DSP第四章2快速付里叶变换FFT - 图文(3)

三、蝶形流图表示蝶形单元：时域中，前后半部表示式用蝶形结表示。x(n)x(n)?x(n?N/2)?x1(n)x(n+N/2)WnN[x(n)?x(n?N/2)]W?x2(n)nN与时间抽取法的推演过程一样，由于N=2L,N/2仍为偶数，所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。例子：求3N=2=8点DIF先将N=8DFT分解成2个4点DFT：（1）先按N=8-->N/2=4，做4点的DIF：Nx1(n)?x(n)?x(n?)2Nnx2(n)?[x(n)?x(n?)]WN2可知：时域上：x(0),x(1),x(2),x(3)为前半序列x(4),x(5),x(6),x(7)为后半序列产生新的子序列：x1(n)、x2(n)频域上：X(0),X(2),X(4),X(6)由x1(n)给出X(1),X(3),X(5),X(7),由x2(n)给出前半部分序列后半部分序列将N=8点分解成2个4点的DIF的信号流图x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WW8108X1(k)x1(n)X(0)X(2)4点X(4)DFTX(6)x2(n)WW8328X2(k)X(1)X(3)4点X(5)DFTX(7)如：x（?x(0)?x(4),x（）?x(1)?x(5),x（?x(2)?x(6),x（）?x(3)?x(7)10）1112）13nnx（?[x(0)?x(4)]WN,x（）?[x(1)?x(5)]WN,20）21nnx（?[x(2)?x(6)]WN,x（）?[x(3)?x(7)]WN22）23(2)N/2(4点)-->N/4(2点)FFT(a)先将4点分解成2点的DIF：?因为4点DIF还是比较麻烦，所以再继续分解。?x1(0)、x1(1)前半部分序列x1(n):??x1(2)、x1(3)后半部分序列?x2(0)、x2(1)前半部分序列同理：x2(n):??x2(2)、x2(3)后半部分序列N?x(n)?x(n?)?x(L)113?N2若设：（L?0??1），在此L?0，1?N4?[x1(n)?x1(n?)]WNn?x（4L）2?N??x2(n)?x2(n?2)?x5(L)N同理：（L?0??1），在此L?0，1?Nn4?[x2(n)?x2(n?)]WN?x（6L）2?（b)一个2点的DIF蝶形流图x3(0)x1(0)x1(1)x1(2)x1(3)2点DFTx3(1)X(0)X(4)W08x4(0)W28X(2)2点DFTx4(1)X(6)其中x3(0)?x1(0)?x1(2),x3(1)?x1(1)?x1(3)