數(shù)字信號(hào)處理ch3_1時(shí)間抽取FFT0

1、數(shù)字信號(hào)處理數(shù)字信號(hào)處理授課教師：呂曉麗授課教師：呂曉麗 內(nèi) 容 回 顧DFT的優(yōu)點(diǎn)：的優(yōu)點(diǎn)： 開辟了頻域離散化的道路DFT的缺點(diǎn)：的缺點(diǎn)： 運(yùn)算量大，很難實(shí)現(xiàn)實(shí)時(shí)處理v4.1 引言引言v4.2 基基2FFT算法算法v4.3 進(jìn)一步減少運(yùn)算量的措施進(jìn)一步減少運(yùn)算量的措施v4.4 分裂基分裂基FFT算法算法v4.5 離散哈特萊變換離散哈特萊變換(DHT)1, 1 , 0,)()(10NkWnxkXknNNnN N1616323264641281282562565125121024102420482048N N2 225625610241024409640961638416384655366553

2、62621142621141048576104857641943044194304knNWknNWknNNnkNnNkNWWW)()(nkNknNWWnkNNnkNWW2nmknNmkNWW為整數(shù)nNWWnmknNmkN/,/12, 1 , 0) 12()2()(Nrrxrxnx) 12()2()(kXkXkXBCA)()()2(21kXWkXNkXkNBCA)()()(21kXWkXkXkNCB)(2kXA)(1kX)()()(21kXWkXkXkN)()()2/(21kXWkXNkXkN12/1 , 0Nk因此有因此有: 蝶形運(yùn)算符號(hào)蝶形運(yùn)算符號(hào) kNW)(2kX)(1kXkNW)()()

3、(21kXWkXkXkN)()()2(21kXWkXNkXkN 蝶形運(yùn)算符號(hào)蝶形運(yùn)算符號(hào) )(1kX-1kNW)(2kX)()()(21kXWkXkXkN)()()2(21kXWkXNkXkNN=2x(n)=x(0), x(1) 1 ( x) 0( x02W) 1 () 0 () 0 (02xWxX) 1 () 0 () 1 (02xWxXx(0)x(1)x(2)x(3)x(0)x(2)x(1)x(3)X1(0)X1(1)X2(0)X2(1)2點(diǎn)DFT2點(diǎn)DFT04W14WX (0)X (1)X (2)X (3)1 , 0),()()2(241kkXWkXkXk1 , 0),()()(241k

4、kXWkXkXkx(0)x(2)x(1)x(3)X1(0)X1(1)X2(0)X2(1)04W14W04W04WX (0)X (1)X (2)X (3)1 , 0),()()2(241kkXWkXkXk1 , 0),()()(241kkXWkXkXkx(0)x(2)x(1)x(3)04W14W04W04WX (0)X (1)X (2)X (3)1 , 0),()()2(241kkXWkXkXk1 , 0),()()(241kkXWkXkXkx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)4點(diǎn)DFT4點(diǎn)DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0

5、)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)08W18W28W38W3 , 2 , 1 , 0),()()(281kkXWkXkXk3 , 2 , 1 , 0),()()4(281kkXWkXkXk4點(diǎn)DFT4點(diǎn)DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)08W18W28W38W04W14W04W04W3

6、 , 2 , 1 , 0),()()(281kkXWkXkXk3 , 2 , 1 , 0),()()4(281kkXWkXkXk04W14W04W04Wx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)08W18W28W38W08W28W08W08W08W28W08W08WNN2log2復(fù)乘次數(shù)NN 2NN2log2N N2 24 48 81616323264641281282562565125121024102420482048N N2 24 4161664642562561024102440964

7、096163841638465536655362621142621141048576104857641943044194304N N/ /2 2loglog2 2N N1 14 41212323280801921924484481024102423042304512051201126411264計(jì)算量比較表NN2logvFIR濾波器的設(shè)計(jì)濾波器的設(shè)計(jì)v電網(wǎng)諧波參數(shù)的計(jì)算電網(wǎng)諧波參數(shù)的計(jì)算v齒輪減速器故障診斷方面齒輪減速器故障診斷方面08W18W28W38W08W28W08W08W08W28W08W08Wx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X (0)X (1)X (2

8、)X (3)X (4)X (5)X (6)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)A(1)A(2)A(3)A(4)A(5)A(6)A(7)5-11-104W14W04W04W試?yán)迷嚴(yán)肗=4基基2時(shí)間抽取的時(shí)間抽取的FFT流圖計(jì)算流圖計(jì)算8點(diǎn)點(diǎn)序列序列x(n)=1, -1, 1, -1, 2, 1, 1, 2的的DFT。 X1(k)=5, -1, 1, -1, X2(k)=1, -2+3j, 1, -2-3j利用上述公式，可

9、得序列利用上述公式，可得序列x(n)的的DFT X(k)為為X(k)=6, -0.293+3.535j, 1+j, -1.707 + 3.535j, 4, -1.707-3.535j, 1-j, -0.293-3.535j1211-11-121-2+3j1-2-3j3-1200-21-304W14W04W04W 1 1、DIT-FFTDIT-FFT算法原理算法原理 （1 1）明確）明確FFTFFT基本概念基本概念 （2 2）掌握蝶形運(yùn)算流圖）掌握蝶形運(yùn)算流圖 畫法及特點(diǎn)畫法及特點(diǎn) 2、FFT運(yùn)算量運(yùn)算量 (1) 倒位序?qū)崿F(xiàn)n0n1n2x(n2 n1n0)x(000)x(100)x(010)0

10、01 10 01 11)12 x(n n0)x(n2 n10 01 1x(110)x(001)x(101)x(011)x(111)0 01 10 01 10 01 10 01 1x(0)x(2)x(1)x(3)X1(0)X1(1)X2(0)X2(1)2點(diǎn)DFT2點(diǎn)DFT111104W14W02W02WX (0)X (1)X (2)X (3)1 , 0),()()2(241kkXWkXkXk1 , 0),()()(241kkXWkXkXk4點(diǎn)DFT4點(diǎn)DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(

11、3)X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)111108W18W28W38W3 , 2 , 1 , 0),()()(281kkXWkXkXk3 , 2 , 1 , 0),()()4(281kkXWkXkXk4點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38Wx x(0)(0)x x(2)(2)x x(4)(4)x x(6)(6)x x(1)(1)x x(3)(3)x x(5)(5)x x(7)(7)A A(0)(0)A A(1

12、)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)W WN N0 0W WN N1 1W WN N2 2W WN N3 3x x(0)(0)x x(2)(2)x x(4)(4)x x(6)(6)x x(1)(1)x x(3)(3)x x(5)(5)x x(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6

13、)A A(7)(7)A A(0)(0)A A(7)(7)X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)X X(5)(5)X X(6)(6)X X(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/2N/20 0W WN/2N/21 1W WN/2N/20 0W WN/2N/21 14點(diǎn)DFT4點(diǎn)DFTW WN N0 0W WN N1 1W WN

14、 N2 2W WN N3 3x x(0)(0)x x(4)(4)x x(2)(2)x x(6)(6)x x(1)(1)x x(5)(5)x x(3)(3)x x(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(7)(7)X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)X X(5)(

15、5)X X(6)(6)X X(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/2N/20 0W WN/2N/21 1W WN/2N/20 0W WN/2N/21 12點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFTW WN N0 0W WN N1 1W WN N2 2W WN N3 3x x(0)(0)x x(4)(4)x x(2)(2)x x(6)(6)x x(1)(1)x x(5)(5)x

16、x(3)(3)x x(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(7)(7)X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)X X(5)(5)X X(6)(6)X X(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5

17、)(5)A A(6)(6)A A(7)(7)W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/2N/20 0W WN/2N/21 1W WN/2N/20 0W WN/2N/21 1W WN N0 0W WN N1 1W WN N2 2W WN N3 3x x(0)(0)x x(4)(4)x x(2)(2)x x(6)(6)x x(1)(1)x x(5)(5)x x(3)(3)x x(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A

18、A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(7)(7)X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)X X(5)(5)X X(6)(6)X X(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/4N/40 0W WN/2N/20 0W WN/2N/

19、21 1W WN/2N/20 0W WN/2N/21 1W WN N0 0W WN N1 1W WN N2 2W WN N3 3x x(0)(0)x x(4)(4)x x(2)(2)x x(6)(6)x x(1)(1)x x(5)(5)x x(3)(3)x x(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)(4)A A(5)(5)A A(6)(6)A A(7)(7)A A(0)(0)A A(7)(7)X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)X X(5)(5)X X(6)(6)X X(7)(7)A A(0)(0)A A(1)(1)A A(2)(2)A A(3)(3)A A(4)