数字信号课件：DSP第四章2.ppt

1、knNW1454)54(494WWWW1898178258WWWW利用以上特性,得到改进DFT直接算法的方法.22)()()(NNNkXkXkX把N点数据分成二半：其运算量为：2)2(N2)2(N2N再分二半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N这样一直分下去，剩下两点的变换两点的变换。 12221xrx rxrxr0,1,.,/2 1rN将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。 111000NNNnknknkNNNnnnX kx n Wx n Wx n Wn为偶数n为奇数/2 1/

2、2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNNWWWW 又要运算一个蝶形结，需要一次乘法 ， 两次加法。)(2kXWkN)()() 2/()()()(2121kXWkXNkXkXWkXk

3、XkNkN22/2/2/2NNN2/2 1/2N NNN运算量减少了近一半1314(2 )( )(21)( )xlx lxlx l0,1,.,/4 1lN13/2413/24( )( )( )()( )( )4kNkNX kXkWXkNX kXkWXk0,1,.,14Nk N / 2仍为偶数，进一步分解：N / 2 N / 425/2625/26( )( )( )()( )( )4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 同理：其中：552( )( )(2 )XkDFT x lDFT xl662( )( )(21)XkDFT x lDFT xl0,1,.,/4 1lN2/2k

4、kNNWW统一系数：0003322301033223(0)(0)(1)(0)(4)(1)(0)(1)(0)(4)NNXxWW xxW xXxWW xxW x/4 1133/43/400( )( )( )NlklkNNllXkx l Wx l W0,1k 0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x/4 1144/44/400( )( )( )NlklkNNllXkx l Wx l W0,1k 每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组

5、具有相同的结构，相同的 因子分布，第m级的组数为：rNW2mN例：N=8=23，分3级。m=1级,分成四组,每组系数为m=2级,分成二组,每组系数为m=2级,分成一组,每组系数为080204/WWWN28082012/02/,WWWWWWNNNN382818083210,WWWWWWWWNNNNrNW002280102444880123888882N10201301,2,3,0,121W ,0,1,.1,2mkkkkmkmWkWWmWkWWWWmWkWW WWmWkNk由上可知：级，级，级，看出：第 级的系数为或NWk2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点D

6、FT两个2点DFT两个2点DFT两个2点DFT两个2点DFT两个4点DFT两个4点DFT两个N/2点DFTX1(k).X2(k)X(k) 由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法”.x(n)2log22FNNmLN复数乘法：2logFaNLNN复数加法：222()2()loglog2FFmDFTNNNmFFTNN比较DFT NFNMNm2log22NFNMNa2logNN2log1111( )( )( )( )( )( )rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m级迭代，k，j表示数据所在的行数02Wx

7、(0)x(4)X3(0)X3(1)中放在一个暂存器中放在单元中，将放在单元例：将RWAxAx08) 1 ()4()0()0(单元送回单元送回将) 1 ()4()0()0()4()0(0808AxWxAxWxx(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)A(5)=x(5)A(6)=x(6)A(7)=x

8、(7)180818084,32,1WRWRWRWR暂存器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 n具体执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一

9、个中间存储单元。n01234567n04261537 在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现-称为“整序”或“重排”（采用码位倒读）且注意：(1)当n=n时，数据不必调换；(2)当nn时，必须将原来存放数据x(n)送入暂存器R，再将x(n)送入x(n),R中内容送x(n).进行数据对调。(3)为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。nn时，调换。1111111( )( )(2)(2)( )(2)mrmmmNmmrmmmNXkXkXkWXkXkXkWrNW

10、的确定2( )2L mrkrNW系数 ：N / 2个存储单元4点基2时间抽取FFT算法流图1 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm)4 , 3 , 1 , 2()(nx计算4点序列 的 DFT，并在每个节点上标注每一级计算结果 112)2()0()1(532)2()0()0(00 xxQxxQ341) 3() 1 () 1 (541) 3() 1 ()0(11xxQxxQ1055)0()0()0(10QQX1041(1)(1)(1)13XQW Qj 0021(2)(0)-(0)550XQW Q1041(3)(1)-(1)13XQW Qj 3 , 2 , 1 , 0),31, 0 ,31,10()(kjjkX