数字信号处理[第四章 快速傅里叶变换(FFT)]

1、2 离散傅里叶变换（离散傅里叶变换（DFTDFT） 10( )( ), 0,1,1NnkNnX kx n WkN101( )( ), 0,1,1NnkNkx nX k WnNN0121(1)(0)(1)(2)(1)NNNNNXxWxWxWx NW32NjknnkNWem lNmNNWW周期性：2NmmNNWW对称性：45时域抽取法时域抽取法FFTFFT（DIT-FFTDIT-FFT） 频域抽取法频域抽取法FFTFFT（DIF-FFTDIF-FFT） 基基2 2快速傅里叶算法快速傅里叶算法IDFTIDFT的高效算法的高效算法6时域抽取法时域抽取法FFTFFT（DIT-FFTDIT-FFT） 2M

2、N 设：122( )(2 ) ( )(21) 0,1,1Nx rxrx rxrr( )( )( )knknNNnnX kx n Wx n W偶数奇数22222/2NNjkrkrNjkrkrNWeeW/2 1/2 12(21)00(2 )(21)NNk rkrNNrrxr WxrW/2 1/2 1221200( )( )NNkrkkrNNNrrx r WWx r W/2 1/2 11/22/200( )( )NNkrkkrNNNrrx r WWx r W12( )( )kNX kW Xk712( )( )( )kNX kX kW Xk12()( )( )2kNNX kX kW Xk2NkkNNW

3、W 蝶形运算1( )X k2( )Xk( )X k()2NX k 1( )x r2( )x r(2 )xr (21)xr 试画出试画出N N8 8的的DFTDFT的一次时域抽取分解图的一次时域抽取分解图kNW18(1)X-1-1-1-1-1-1-1-11(0)(0)xx1(1)(2)xx1(2)(4)xx1(3)(6)xx2(0)(1)xx2(1)(3)xx2(2)(5)xx2(3)(7)xx1(0)X2(0)X1(1)X1(2)X1(3)X2(1)X2(2)X2(3)X/ 2NDFT点/ 2NDFT点0NW1NW2NW3NW(0)X(4)X(2)X(3)X(5)X(6)X(7)X931414

4、( )(2 ) ( )(21) 0,1,1Nx lxlx lxll/4 1/4 12(21)11/21/200( )(2 )(21)NNk lklNNllX kxl WxlW222422/2/4NNjklklNjklklNWeeW/4 1/4 13/4/24/400( )( )NNklkklNNNllx l WWx l W3/24( )( )kNXkWXk13/24()( )( )4kNNX kXkWXk4/2/2NkkNNWW 25/26( )( )( )kNXkXkWXk25/26()( )( )4kNNXkXkWXk10(1)X-1-1-1-1-1-1-1-12(0)X1(1)X1(2)

5、X1(3)X2(1)X2(2)X2(3)X0NW1NW2NW3NW(0)X(4)X(2)X(3)X(5)X(6)X(7)X1(0)X13(0)(0)(0)xxx/ 4NDFT点/ 4NDFT点/ 4NDFT点/ 4NDFT点14(2)(1)(0)xxx3(0)X4(0)X0/2NW-1-113(4)(2)(1)xxx14(6)(3)(1)xxx3(1)X4(1)X1/2NW-1-125(1)(0)(0)xxx26(3)(1)(0)xxx25(5)(2)(1)xxx26(7)(3)(1)xxx5(0)X6(0)X0/2NW-1-15(1)X6(1)X1/2NW-1-111(1)X-1-1-1-1

6、-1-1-1-12(0)X1(1)X1(2)X1(3)X2(1)X2(2)X2(3)X0NW1NW2NW3NW(0)X(4)X(2)X(3)X(5)X(6)X(7)X1(0)X13(0)(0)(0)xxx14(2)(1)(0)xxx3(0)X4(0)X0/2NW-1-113(4)(2)(1)xxx14(6)(3)(1)xxx3(1)X4(1)X1/2NW-1-125(1)(0)(0)xxx26(3)(1)(0)xxx25(5)(2)(1)xxx26(7)(3)(1)xxx5(0)X6(0)X0/2NW-1-15(1)X6(1)X1/2NW-1-10/4NW-1-10/4NW-1-10/4NW-

7、1-10/4NW-1-112)(1)(1AX-1-1-1-1-1-1-1-1(4)A(1)A(2)A(3)A(5)A(6)A(7)A0NW1NW2NW3NW)(0)(0AX)(4)(4AX)(2)(2AX)(3)(3AX)(5)(5AX)(6)(6AX)(7)(7AX(0)A)(0)(0 xA)(2)(2xA(0)A(2)A0NW-1-1)(4)(1xA)(6)(3xA(1)A(3)A2NW-1-1)(1)(4xA)(3)(6xA)(5)(5xA)(7)(7xA(4)A(6)A0NW-1-1(5)A(7)A2NW-1-10NW-1-10NW-1-10NW-1-10NW-1-113DIT-FFT

8、算法与直接计算DFT运算量的比较2MN 设：M级蝶形12每个蝶形需要 次复数乘，次复数加2N每级有个蝶形运算222log;(2)log22MANNCMN CN MNN（ ）=14DIT-FFT的运算规律及编程思想12( )( )( )kNX kX kW Xk12()( )( )2kNNX kX kW XkkNW122( ),(),( ),( )NX kX kX kXk15 一、原位计算一、原位计算)(1)(1AX-1-1-1-1-1-1-1-1(4)A(1)A(2)A(3)A(5)A(6)A(7)A0NW1NW2NW3NW)(0)(0AX)(4)(4AX)(2)(2AX)(3)(3AX)(5)

9、(5AX)(6)(6AX)(7)(7AX(0)A)(0)(0 xA)(2)(2xA(0)A(2)A0NW-1-1)(4)(1xA)(6)(3xA(1)A(3)A2NW-1-1)(1)(4xA)(3)(6xA)(5)(5xA)(7)(7xA(4)A(6)A0NW-1-1(5)A(7)A2NW-1-10NW-1-10NW-1-10NW-1-10NW-1-1利用同一存储单元存储蝶形计算输入、输出数据16二、旋转因子二、旋转因子pNW旋转因子的指数L表示运算级数，=1,2,M/4210LpJJNNLWWWJ，/2220,1LpJJNNLWWWJ，230,1,2,3LpJJNNLWWWJ，120,1,2

10、,21LpJLNLWWJ级，22222LML ML MM LpJJNJNWWWW120,1,2,21M LLpJJ17三、蝶形运算规律三、蝶形运算规律1111( )( )()()( )()pLLLNpLLLNXJXJXJB WXJBXJXJB WL表示运算级数，=1,2,M( )( )LXJX J表示第L级运算后数组元素的值120,1,21MLLpJJ；1222LpLMLNBW，同一对应着间隔为点的个蝶形18四、编程思想及程序框图四、编程思想及程序框图开始开始送入送入x(n),Mx(n),MN=2N=2M M倒序倒序L=1L=1，M MJ=0J=0，B-1B-1B=2B=2L-1L-1P=2P

11、=2M-LM-LJ J( )( )()()( )()pNpNX kX kX kB WX kBX kX kB W输出输出结束结束k=J,N-1,2k=J,N-1,2L L( )( )()()( )()pNpNX kX kX kB WX kBX kX kB W19四、序列的倒序四、序列的倒序)(1)(1AX-1-1-1-1-1-1-1-1(4)A(1)A(2)A(3)A(5)A(6)A(7)A0NW1NW2NW3NW)(0)(0AX)(4)(4AX)(2)(2AX)(3)(3AX)(5)(5AX)(6)(6AX)(7)(7AX(0)A)(0)(0 xA)(2)(2xA(0)A(2)A0NW-1-1

12、)(4)(1xA)(6)(3xA(1)A(3)A2NW-1-1)(1)(4xA)(3)(6xA)(5)(5xA)(7)(7xA(4)A(6)A0NW-1-1(5)A(7)A2NW-1-10NW-1-10NW-1-10NW-1-10NW-1-120 000 0 x （）210( , , )x n n n00 n 偶01 n 奇10n 11n 10n 11n 20n 21n 20n 21n 20n 21n 20n 21n 100 4x （ ）010 2x （）110 6x （ ）001 1x （ ）101 5x （ ）011 3x （ ）111 7x （ ）21 0 00 0 0 0 0 00 0

13、 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0 1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 22LH=N/2LH=N/2J=LHJ=LHN N1 1=N-2=N-2I=1I=1，N N1 1I=JI=JT=X(I)T=X(I)A(I)=X(J)A

14、(I)=X(J)A(J)=TA(J)=TK=LHK=LHJKJ=3,实数乘法运算减少13(2)4(3)2(2)(2) 10222MNNRMNM35一类一类蝶形单元运算：包括蝶形单元运算：包括所有所有旋转因子旋转因子 蝶形单元类型越多，编程就越复杂，但乘法运算的减少量是可观的。 1.1.多类蝶形运算多类蝶形运算二类二类蝶形单元运算：去掉蝶形单元运算：去掉 旋转因子旋转因子1rNW 三类三类蝶形单元运算：再去掉蝶形单元运算：再去掉 旋转因子旋转因子rNWj 四类四类蝶形单元运算：再处理蝶形单元运算：再处理 旋转因子旋转因子(1) 2 / 2rNWj36 2.2.旋转因子的生成旋转因子的生成cos(

15、2/)sin(2/)mNWm Njm N一种方法是在每级运算中一种方法是在每级运算中直接产生直接产生；二种方法是在二种方法是在FFTFFT程序开始前程序开始前预先计算预先计算出旋转因子，出旋转因子，存放在数组中，作为存放在数组中，作为旋转因子表旋转因子表，在程序执行，在程序执行中直中直接查表接查表。37 3.3.实序列的实序列的FFTFFT算法算法122( )(2 ) ( )(21) 0,1,1Nx nxnx nxnn12( )( )( )y nx njx n( )( )( )epopY kYkYk11( ) ( )( )epYkDFT x nX k22( )( )( )opYkDFT jx

16、njXk122( )( )( )0,1,kNNX kX kW Xkk，2()( )1,2,1NX NkXkk，38分裂基分裂基FFTFFT算法算法,/ 4,4npqpNq当且时10101044,03,01NNnpnnnnnn3910011/4 13()410000( )( )()4NNNknnknNNnnnNX kx n Wxnn W 10104Nnpnnnn0101/4 1310400()4NknknNnnNWxnn W1112444NNjknknNNknWeW00/4 1004040230404 ()()43 ()()24NknknkkNNx n Wx nWNNx nWx nWW10104

17、4,01,03Nkkkkk1001010100/4 141000402(4)3(4)(4)0404(4) ()()43 ()()24NkknkkkkkknNNXkkx nx nWNNx nWx nWW401001010100/4 141000402(4)3(4)(4)0404(4) ()()43 ()()24NkknkkkkkknNNXkkx nx nWNNx nWx nWW11244441jnknkWe0000100/4 1004023(4)0404 ()()43 ()()24NknkkkknNNx nx nWNNx nWx nWW101044,01,03Nkkkkk0000/4 10402

18、3(4)44(4) ( )()43 ()()24Nknkkk knNNXkkx nx nWNNx nWx nWW10,kk nn410000/4 104023(4)44(4) ( )()43 ()()24Nknkkk knNNXkkx nx nWNNx nWx nWW003k/4 1403(4 ) ( )()()()424NknNnNNNXkx nx nx nx nW0002304440,1kkkkWWW0002304441,1,kkkkWj WWj /4 1403(41) ( )()()()424Nkn nNnNNNXkx njx nx njx nW0002304442,1,1,1kkkkW

19、WW /4 14203(42) ( )()()()424NknnNnNNNXkx nx nx nx nW/4 14303(43) ( )()()()424NknnNnNNNXkx njx nx njx nW0002304443,1,kkkkWj WWj 42/4 1403(4 ) ( )()()()424NknNnNNNXkx nx nx nx nW/4 14203(42) ( )()()()424NknnNnNNNXkx nx nx nx nW/2 120(2 ) ( )()2NknNnNXkx nx nW/2 12220(2 )( ),( )( )()2NknNnNXkx n Wx nx

20、nx n43/4 1403(41) ( )()()()424Nkn nNnNNNXkx njx nx njx nW/4 14303(43) ( )()()()424NknnNnNNNXkx njx nx njx nW/4 1/4 11424440014234(41)( ),(43)( ),3( ) ( )()()()4243( ) ( )()()()424NNknknNNnnnNnNXkx n WXkxn WNNNx nx njx nx njx nWNNNxnx njx nx njx nW44214234( )( )()23( ) ( )()()()2443( ) ( )()()()244nN

21、nNNx nx nx nNNNx nx nx njx njx nWNNNxnx nx njx njx nWL形蝶形图一个一个N N点点DFTDFT可分解成一个可分解成一个N/2N/2点点DFTDFT和两个和两个N/4N/4点点DFTDFT45(1)x(1)2Nx(1)4Nx3(1)4Nx2( )( )()2Nx nx nx n2(1)x2(1)4Nx/ 2ND F T点143( ) ( )()()()244nNNNNx nx nx njx njx nW-1-1-1-1-j-j1NW14(1)x/4ND F T点-1-13NW24(1)x/4ND F T点243( ) ( )()()()244n

22、NNNNxnx nx njx njx nW(1)(1)2Nxx3(1)(1)44NNxx3 (1)(1)44NNj xx46242431( )( )()23( ) ( )()()()2443( ) ( )()()()244nNnNNx nx nx nNNNx nx nx njx njx nNNNxnx nx njxWnjx nW24每个L形需要 次复数乘， 次复数加2MN 设：M-1级L形Ljjl第 级有 个 形142jjlNl1011()1 () 4262jiijiNNl 21log212211222() log( 1)3332399NMMNMjjNClMNN47 * ()X NkXk共轭对

23、称性：( )( )( )( )( )( )riepopx nx njx nX kXkXk计算出计算出X(kX(k) )的前的前N/2N/2个值，则后个值，则后N/2N/2个值可求个值可求 直接对实序列进行实数域变换的直接对实序列进行实数域变换的离散哈特莱变换离散哈特莱变换48102( ) ( )( )()NHnXkDHT x nx n casknN( )cossincas1012( )( )( )()NHHnx nIDHT XkXk casknNN10101012( )()2( )1()2)NNHnNnxcaXk casknNNskNcasknNN491011001012 ()122( )2(

24、 )()()(NnNNnNcasknNNxcaskcasknNNxcaskNN1022()()NncaskcasknNN1022cos()sin22()cos()sin()NnkkknknNNNN1022cos()sin()22cos()s22sin()coin()s(22cos()sin() )NnkkNNkkNNknknNNknknNN1022cos()sin()Nnk nk nNN22221()()()()01111 2222NNNNNjk njk njk njk nneeeejj, =n0, n N22222101110221NNNNNNjkjknjkjkjkn Nneeeee, =n

25、 0, n N( )x n501022( ) ( )( )cos()sin()NHnXkDHT x nx nknknNN10122( )( )( )cos()sin()NHHnx nIDHT XkXkknknNNN1022co( ) ( )( )s()sin()NnX kDFT x nx nknjknNN1022cos()sin()1( )( )( )NnknjknNNx nIDFT X kX kN DHTDHT的核函数是的核函数是DFTDFT核函数的实部与虚部之和核函数的实部与虚部之和51( )( )( )HHeHoXkXkXk1( )( )()21( )( )()2HeHHHoHHXkXk

26、XNkXkXkXNk1022( ) ( )( )cos()sin()NHnXkDHT x nx nknknNN10102( )( )cos()2( )( )sin()NHenNHonXkx nknNXkx nknN1022co( ) ( )( )s()sin()NnX kDFT x nx nknjknNN( )( )( )11( )()( )()22HeHoHHHHX kXkjXkXkXNkj XkXNk( )Re( )lim( )HXkX kX k521.DHT1.DHT是实值变换是实值变换2.DHT2.DHT的正反变换具有相同形式的正反变换具有相同形式DHTDHT的主要优点：的主要优点：3

27、.DHT3.DHT与与DFTDFT间的关系简单间的关系简单53 1122( )( )( )( )HHDFT x nXkDFT x nXk1212( )( )( )( )HHDHT ax nbx naXkbXk54 ( )( ) ()()HHDFT x nXkDFT x NnXNk1022()( )cos()sin()NHnXNkx nknknNN55102 ()()()NnDHT x Nnx Nn casknN102( )()Nnx n cask NnN1022( )cos()sin()Nnx nk Nnk NnNN1022( )cossinNnx nknknNN22cos()cosk Nnk

28、nNN22sin()sink NnknNN 102()( )() NHnXNkx n casNk nN1022( )cos()sin()Nnx nknknNN56 ( )( )HDFT x nXk00022cos()sin()()( )( )()NNHHnknknNx nRnXkNXNk00022cos()sin()()( )( )()NNHHnknknNx nRnXkNXNk5710002 ()( )()( )()NNNNNnDFT x nnRnx nnRn casknN1002( )()Nnx n cask nnN0nnn1000002222( )()()(coscossins)()222

29、incossin2()()()()sincosNnx nknknknknNNNNknknknknNNNN02( )cos()HXkknN02()sin()HXNkknN58 11112222( )()( )()HHDFTx nx NnXkXNk ( )( ) ()()HHDFT x nXkDFT x NnXNk11112222( )()( )()HHDFTx nx NnXkXNk59 1122( )( )( )( )HHDFT x nXkDFT x nXk122121( )( )()()()()HHeHHox nx nXK XKXNK XK121212( )( )()()()()HHeHHox

30、 nx nXK XKXNK XK60( )( )( )11( )()( )()22HeHoHHHHX kXkjXkXkXNkj XkXNk1212 ( )( )( )( )DFT x nx nX kXk11222112221122211222( )( )( )()( )( )()( )( )()( )( )()HeHHHeHHHoHHHoHHX kXkXkXNkXkXkXNkXkXkXNkXkXkXjkjN61()HXK ( )Re( )lim( )HXkX kX k11222112221122211222( )( )( )()( )( )()( )( )()( )( )()HeHHHeHHH

31、oHHHoHHX kXkXkXNkXkXkXNkXkXkXNkXkXkXjkjN11221222112212221( )( )( )()( )1( )( )()( )( )( )()()22HeHHHoHHHeHHHoHHHXkXkXkXNkXkXkXNkXkXkXNkXkXkXNk21()()HHoXNK XK21()()HHeXK XK12( )( )x nx n62DHTDHT的快速算法（的快速算法（FHTFHT）：）：102( ) ( )( )()NHnXkDHT x nx n casknN2MN 设：012( )(2 ) ( )(21) 0,1,1Nx rxrx rxrr221100

32、22( )(2 )(2 )(21)(21)NNHrrXkxr cask rxrcaskrNN22211010011022( )()( )()/ 2/2cos()2sin(22( )()/ 2NNNrrrx r caskrx r caskrNNkx r caskNNrNk()cos() sincascascas22,/ 2krkNN63222110100110222( )( )()cos()( )()/ 2/ 222sin()( )()/ 2NNNHrrrXkx r caskrkx r caskrNNNkx r caskrNN0( )HXk21cos()( )HNk Xk212sin()()NHNk Xk( )HXk 22( )cos();