第3章离散傅里叶变换2

1、3.3 快速傅里叶变换GFFT 并 不 是 一 种 新 的 变 换 形 式，它 只 是 DFT 的 一 种 快快 速速 算算 法法 。并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法 。计算DFT复数运算量10)() 1 (NnnNWnxX利用 的固有对称性和周期性改善DFT的运算效率knNWknNW的对称性：nkNknNWW*)(knNW的周期性：)()(kNnNkNnNknNWWW1)()(22kjkNNjkNNeeW因为：1, 1 , 0Nk1)()(22njNnNjNnNeeW1, 1 , 0Nn由此可得出：nkNknNNk

2、NnNWWW)()(1sincos)(222/jeWNNjNNkNNkNWW)(2nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW对称性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可约性/nknk mNN mWW0/2(/2) 11Nk NkNNNNWWWW 特殊点：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee 时间抽取基-2FFT算法Decimation-in-Time (DIT)一、算法原理一、算法原理n设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称

3、为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。n其中基数2-N=2M，M为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M。1、算法推导 12221xrx rxrxr0,1,.,/2 1rN将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。 111000NNNnknknkNNNnnnX kx n Wx n Wx n Wn为偶数n为奇数/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrk

4、NNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN12/1 , 0)()()21NkDFTNkXWkXkXkN中的前半部分点又合成（1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNNWWWW 又12/012/022/2)2/(2/2212/012/012/1)2/(2/11)2/(2/2/)()()()2()()()()2(NrNrrkNkNrNNrNrrkNkNrNNkrNrkNkXWrxWrxkNXkXWr

5、xWrxkNXWW后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。)()()(212/)2/kXWkXkXWWWWkNkNkNNNkNN后半部分：又（频域中的N个点频率成分为：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：?结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。v由于N=2L，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个

6、N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算加减运算。例子：求 N=23=8点FFT变换)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出2、蝶形结即蝶式计算结构也即为蝶式信号流图上面频域频域中前/后半部分表示式可以用蝶形信号流图表示。X1(k)X2(k)kNW)()(

7、21kXWkXkN)()(21kXWkXkN作图要素：作图要素：(1)左边两路为输入左边两路为输入(2)右边两路为输出右边两路为输出(3)中间以一个小圆表示加、中间以一个小圆表示加、减运算（右上路为相加输减运算（右上路为相加输出、右下路为相减输出出、右下路为相减输出)(4)如果在某一支路上信号需要进行如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。将相乘的系数标在箭头旁。(5)当支路上没有箭头及系当支路上没有箭头及系数时，则该支路的传输比数时，则该支路的传输比为为1。将N=8点分解成2个4点的DFT的信号流图X(4)X(7)同

8、学们自已写4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXXWXXXWXXX）（）（）（）（如：x1(r)x2(r)奇序列、偶序列、) 6() 2() 4() 0(: )(1xxxxrx奇序列、偶序列、同理：)7() 3 () 5 () 1 (: )(2

9、xxxxrx1014012()()2(4131，），在此（）奇序列（）偶序列若设：LNLLXLxLXLx1014012()()2(6252，），在此（）奇序列（）偶序列同理：LNLLXLxLXLxb 求2点的DFT)()4/()()()()()()()4/10)()() 12()2()()(62/5262/52242/3142/314/0) 12(2/114/022/1111LXWLXNkXLXWLXkXrxLXWLXNkXLLXWLXWLXWLXkXkXrxkNkNkNkNNLkLNNLLkNDFT）也可分解为：同样，（同理：，其中（可分解为：c 一个2点的DFT蝶形流图2点DFT2点DFT

10、x(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W01134413440113441344(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXXW X其中d 另一个2点的DFT蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W01254625460125462546(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXX

11、W X其中同理：(3)将N/4（2点）DFT再分解成2个1点的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，则这里用到对称性这是一蝶形结代入上面流图可知： 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。b 2个1点的DFT蝶形流图1点DFTx(0)1点DFTx(4)X3(0)X3(1)02W进

12、一步简化为蝶形流图：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一个完整N=8的按时间抽取FFT的运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x

13、5(1)x6(1)x6(0)3 按时间抽取FFT算法的特点算法特点1111( )( )( )( )( )( )rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m级迭代，k，j表示数据所在的行数180818084,3,2,1WRWRWRWR暂存器x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(4)=x(4

14、)A(5)=x(5)A(6)=x(6)A(7)=x(7)R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位运算结构运算后，A(0)A(7)正好顺序存放X(0)X(7),可以直接顺序输出。 码位倒序规则以N=8为例：01234567000001010011100101110111自然顺序二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。2 102( )()x nnn n n2 102()nn n n0 122()nn n n2log22FNNmLN2logFaNLNN222()2()log

15、log2FFmDFTNNNmFFTNNNN2log2频率抽取基-2FFT算法Decimation-in-Frequency (DIF)N=2M，M将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半。1/2 1100/2( )( )( )( )NNNnknknkNNNnnn NX kx n Wx n Wx n W/2 1/2 1200( )2NNNnknkNNnnNx n Wx nW/2 1/20( )2NNknkNNnNx nx nWW/2 10( )( 1)2NknkNnNx nx nW 0,1,.,1kN/21NNW k的奇偶将X(k)221krkr0,1,.,/2 1rN

16、/2 120(2 )( )2NnrNnNXrx nx nW/2 1(21)0(21)( )2NnrNnNXrx nx nW/2 1/20( )2NnrNnNx nx nW/2 1/20( )2NnnrNNnNx nx nWW12( )( )2( )( )2nNNx nx nx nNx nx nx nW0,1,.,12Nn 则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N / 2点DFT，记为X1(k)和X2(k)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4

17、)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)1NW0NW2NW3NW311411/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 313414( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n0,1,.,14Nk x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0

18、)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)0/2NW1/2NW0,1,.,14Nk 525626( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n522622/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 0033223330103322333(0)(0)(0)(1)(0)(1)(4)(1)(0)(1)(0)(1)NXXxWW xxxXXxWW xxxW/4 1133/43/400( )( )( )NlklkNNllXkx l Wx l W0,1k x

19、3(n)，x4(n)，x5(n)，x6(n)，n=0,10044224440104422444(2)(0)(0)(1)(0)(1)(6)(1)(0)(1)(0)(1)NXXxWW xxxXXxWW xxxW/4 1144/44/400( )( )( )NlklkNNllXkx l Wx l W0,1k x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)& DIF与DIT比较1DIF与与DIT两种算法均为原位运算。两种算法均为原位运算。算法是两种等价的与次复加次复乘FFTDITD

20、IFNaNmNFNF22lglg2& DIF与DIT比较2快速傅里叶逆变换(IFFT)以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算IFFT的方法。v 利用FFT计算IFFT的思路1IDFTFFTNWWDFTWnxnxDFTkXWkXNkXIDFTnxnkNnkNNknkNNknkN算法都可以拿来运算或频率抽取抽取）那么以上讨论的时间（将运算结果都除以改成运算中的每个系数只要把3)2() 1 ()()()()(1)()(1010v 利用FFT计算IFFT的思路210*10*10*10)()()(1()(1)()(1)()(1)(NnnkNnkNNknkNNknkNNkWnxkXkXDFTNWkXNnxWkXNnxWkXNnx比较与取共轭再取共轭）对它取共轭：此为DFT可用FFT程序v 利用FFT计算IFFT的思路31*01( )( )NnkNkx nXk WN*1*011( )( )( )NnkNkx nXk WDFT XkNN101( )( )NnkNnx nX k WN共轭FFT共轭乘1/ N( )X k*( )Xk( )x n直接调用FFT子程序计算IFFT的方法：快速傅里叶的应用l快速卷积