數(shù)字信號(hào)處理教學(xué)課件第四章 快速傅立葉變換
《數(shù)字信號(hào)處理教學(xué)課件第四章 快速傅立葉變換》由會(huì)員分享,可在線閱讀,更多相關(guān)《數(shù)字信號(hào)處理教學(xué)課件第四章 快速傅立葉變換(101頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、Fast Fourier Transform 第一節(jié)第一節(jié) 直接計(jì)算直接計(jì)算DFTDFT的問(wèn)題及改進(jìn)途徑的問(wèn)題及改進(jìn)途徑1、問(wèn)題的提出、問(wèn)題的提出 設(shè)有限長(zhǎng)序列設(shè)有限長(zhǎng)序列x(n),非零值長(zhǎng)度為,非零值長(zhǎng)度為N,若,若對(duì)對(duì)x(n)進(jìn)行一次進(jìn)行一次DFT運(yùn)算,共需運(yùn)算,共需多大的運(yùn)算多大的運(yùn)算工作量工作量?計(jì)算成本計(jì)算成本?計(jì)算速度計(jì)算速度?2.DFT的運(yùn)算量的運(yùn)算量 回憶回憶DFT和和IDFT的變換式:的變換式:10)(1)()(10 NnWkXNkXIDFTnxNknk10)()()(10 NkWnxnxDFTkXNnnkN1)x(n)為為復(fù)數(shù)復(fù)數(shù),也為也為復(fù)數(shù)復(fù)數(shù)。2)DFT與與IDFT的
2、計(jì)算量相當(dāng)。的計(jì)算量相當(dāng)。nkNjnkNeW 2 注意:注意:計(jì)算機(jī)運(yùn)算時(shí)(編程實(shí)現(xiàn)):計(jì)算機(jī)運(yùn)算時(shí)(編程實(shí)現(xiàn)):0k0)1(0100)1()1()0()0(NNNNWNxWxWxX1k 0111(1)1(1)(0)(1)(1)NNNNXxWxWx NW 2k 0 212(1)2(2)(0)(1)(1)NNNNXxWxWx NW 1Nk0111(1)1(1)(0)(1)(1)NNNNNNNX NxWxWx NW 10)()()(10 NkWnxnxDFTkXNnnkN以以DFT為例:為例:復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(gè)一個(gè)X(k)NN 1N個(gè)個(gè)X(k)(N點(diǎn)點(diǎn)DFT)N 2N(N 1)實(shí)
3、數(shù)乘法實(shí)數(shù)乘法實(shí)數(shù)加法實(shí)數(shù)加法一次復(fù)乘一次復(fù)乘42一次復(fù)加一次復(fù)加2一個(gè)一個(gè)X(k)4N2N+2(N 1)=2(2N 1)N個(gè)個(gè)X(k)(N點(diǎn)點(diǎn)DFT)4N 22N(2N 1)10()NnkNnx n W運(yùn)算量運(yùn)算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)例:計(jì)算一個(gè)例:計(jì)算一個(gè) N點(diǎn)點(diǎn)DFT,共需,共需N2次復(fù)乘次復(fù)乘。以做一次。以做一次 復(fù)乘復(fù)乘1s計(jì),若計(jì),若N=4096,所需時(shí)間為,所需時(shí)間為ss1716777216)4096(2 例:石油勘探,有例:石油勘探,有24個(gè)通道的記錄,每通道波形記個(gè)通道的記錄,每通道波形記 錄長(zhǎng)度為錄長(zhǎng)度為5秒,若每秒抽樣秒,若每秒抽樣5
4、00點(diǎn)點(diǎn)/秒,秒,1)每道總抽樣點(diǎn)數(shù):)每道總抽樣點(diǎn)數(shù):500*5=2500點(diǎn)點(diǎn) 2)24道總抽樣點(diǎn)數(shù):道總抽樣點(diǎn)數(shù):24*2500=6萬(wàn)點(diǎn)萬(wàn)點(diǎn) 3)DFT復(fù)乘運(yùn)算時(shí)間:復(fù)乘運(yùn)算時(shí)間:N2=(60000)2=36*108次次ss360010*36)60000(82 由于計(jì)算量大,且要求由于計(jì)算量大,且要求相當(dāng)大的內(nèi)存相當(dāng)大的內(nèi)存,難以實(shí)現(xiàn)實(shí)難以實(shí)現(xiàn)實(shí)時(shí)處理時(shí)處理,限制了,限制了DFT的應(yīng)用。長(zhǎng)期以來(lái),人們一直在尋的應(yīng)用。長(zhǎng)期以來(lái),人們一直在尋求一種能求一種能提高提高DFT運(yùn)算速度運(yùn)算速度的方法。的方法。FFT便是便是 Cooley&Tukey 在在1965 年提出的的快速年提出的的快速算法,它
5、可以使運(yùn)算速度提高幾百倍,從而使數(shù)字信號(hào)算法,它可以使運(yùn)算速度提高幾百倍,從而使數(shù)字信號(hào)處理學(xué)科成為一個(gè)新興的應(yīng)用學(xué)科。處理學(xué)科成為一個(gè)新興的應(yīng)用學(xué)科。第二節(jié)第二節(jié) 改善改善DFTDFT運(yùn)算效率的基本途徑運(yùn)算效率的基本途徑knNW 1、利用、利用DFT運(yùn)算的系數(shù)運(yùn)算的系數(shù) 的固有對(duì)稱性和周期的固有對(duì)稱性和周期 性,改善性,改善DFT的運(yùn)算效率。的運(yùn)算效率。1)對(duì)稱性)對(duì)稱性 2)周期性)周期性 3)可約性)可約性()()nkN n kn N kNNNWWW周期性 nkmnkNmNWW可約性/nknk mNN mWW2jmnkmNe221NjjNee 0/2(/2)11Nk NkNNNNWWWW
6、 特殊點(diǎn):nkNW 的特性2jnknkNNWe*()()()nknkN n kn N kNNNNWWWW對(duì)稱性NknkNNWWnNnkNNWW2、將長(zhǎng)序列、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短利用對(duì)稱性和周期性分解為短 序列序列DFT的思路的思路 因?yàn)橐驗(yàn)镈FT的運(yùn)算量與的運(yùn)算量與N2成正比的,如果一個(gè)成正比的,如果一個(gè)大大點(diǎn)數(shù)點(diǎn)數(shù)N的的DFT能分解為能分解為若干小點(diǎn)數(shù)若干小點(diǎn)數(shù)DFT的組合的組合,則,則顯然可以達(dá)到顯然可以達(dá)到減少運(yùn)算工作量減少運(yùn)算工作量的效果。的效果。N點(diǎn)點(diǎn)DFTN/2點(diǎn)點(diǎn)DFTN/2點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFTN/4點(diǎn)點(diǎn)DFT.復(fù)乘:復(fù)乘
7、:2N2222 NN22N22224444 NNNN42N FFT算法的基本思想:算法的基本思想:利用利用DFT系數(shù)的特性,合并系數(shù)的特性,合并DFT運(yùn)算中的某些項(xiàng)運(yùn)算中的某些項(xiàng) 把長(zhǎng)序列把長(zhǎng)序列DFT短序列短序列DFT,從而減少運(yùn)算量。,從而減少運(yùn)算量。FFT算法分類算法分類:時(shí)間抽選法時(shí)間抽選法 DIT:Decimation-In-Time頻率抽選法頻率抽選法 DIF:Decimation-In-Frequency第三節(jié)第三節(jié) 按時(shí)間抽選的基按時(shí)間抽選的基2-FFT算法算法1、算法原理、算法原理 設(shè)輸入序列長(zhǎng)度為設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù),將該序列為正整數(shù),將該序列按時(shí)間順序的奇
8、偶分解按時(shí)間順序的奇偶分解為越來(lái)越短的子序列,稱為為越來(lái)越短的子序列,稱為基基2按時(shí)間抽取的按時(shí)間抽取的FFT算法。也稱為算法。也稱為Coolkey-Tukey算法。算法。其中其中基基2表示:表示:N=2M,M為整數(shù)為整數(shù).若不滿足這個(gè)若不滿足這個(gè)條件,可以人為地加上若干零值(條件,可以人為地加上若干零值(加零補(bǔ)長(zhǎng)加零補(bǔ)長(zhǎng))使其)使其達(dá)到達(dá)到 N=2M。先將先將x(n)按按n的奇偶分為兩組,作變量置換的奇偶分為兩組,作變量置換:當(dāng)當(dāng)n=偶數(shù)時(shí),令偶數(shù)時(shí),令n=2r;當(dāng)當(dāng)n=奇數(shù)時(shí),令奇數(shù)時(shí),令n=2r+1;分組,變量置換分組,變量置換2、算法步驟、算法步驟10)()()(10 NkWnxnxD
9、FTkXNnnkN得到:得到:1,.,0)()12()()2(221 Nrrxrxrxrx 帶入帶入DFT中中 10)()()(NnnkNWnxnxDFTkX 12/0)12(12/02)12()2(NrkrNNrrkNWrxWrx 1010)()(NnnkNNnnkNnnWnxWnx為為奇奇數(shù)數(shù)為為偶偶數(shù)數(shù) 12/02212/021)()(NrrkNkNNrrkNWrxWWrx所以所以 12/02212/021)()()(NrrkNkNNrrkNWrxWWrxkX由于由于nNnNjnNjnNWeeW2/2/2222 12/02/212/02/1)()(NrrkNkNNrrkNWrxWWrx)
10、()(21kXWkXkN 1,1,02 Nk1,1,0 Nk?1,1,02 Nk X1(k)、X2(k)只有只有N/2個(gè)點(diǎn),以個(gè)點(diǎn),以N/2為周期;而為周期;而X(k)卻有卻有N個(gè)點(diǎn),以個(gè)點(diǎn),以N為周期。要用為周期。要用X1(k)、X2(k)表達(dá)全部的表達(dá)全部的X(k)值,還必須利用值,還必須利用WN系數(shù)的系數(shù)的周期特性周期特性。rkNkNrNWW2/)2/(2/12/02/112/0)2/(2/11)()()2/(NrrkNNrkNrNWrxWrxkNX )()2/()()2/(2211kXkNXkXkNX后半部分后半部分前半部分前半部分又考慮到又考慮到 的對(duì)稱性:的對(duì)稱性:kNWkNkNN
11、NkNNWWWW 2/)2/()2/()2/()2/(2)2/(1kNXWkNXkNXkNN 有:有:1,1,0)()()(221 NkNkkXWkXkX1,1,0)()(221 NkNkkXWkX后半部分后半部分前半部分前半部分)()()2/(21kXWkXkNXkN )()()(21kXWkXkXkN 1,1,02 Nk)(1kX)(2kXkNW)()(21kXWkXkN)()(21kXWkXkN 蝶形運(yùn)算流圖符號(hào)蝶形運(yùn)算流圖符號(hào)說(shuō)明:說(shuō)明:(1)左邊兩路為輸入左邊兩路為輸入(2)右邊兩路為輸出右邊兩路為輸出(3)中間以一個(gè)小圓表示加、中間以一個(gè)小圓表示加、減運(yùn)算(右上路為相加減運(yùn)算(右上
12、路為相加 輸出、右下路為相減輸輸出、右下路為相減輸 出出)1個(gè)蝶形運(yùn)算需要個(gè)蝶形運(yùn)算需要1次復(fù)乘,次復(fù)乘,2次復(fù)加次復(fù)加復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(gè)一個(gè)N 點(diǎn)點(diǎn)DFTN 2N(N1)一個(gè)一個(gè)N/2點(diǎn)點(diǎn)DFT(N/2)2N/2(N/2 1)兩個(gè)兩個(gè)N/2點(diǎn)點(diǎn)DFTN 2/2N(N/2 1)一個(gè)蝶形一個(gè)蝶形12N/2個(gè)蝶形個(gè)蝶形N/2N總計(jì)總計(jì)N2/2+N/2 N2/2N(N/2-1)+N N2/2運(yùn)算量減少了近一半運(yùn)算量減少了近一半 分解后的運(yùn)算量:分解后的運(yùn)算量:)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN 12/,0 Nk先將先將N=8點(diǎn)的點(diǎn)的DFT分解
13、成分解成2個(gè)個(gè)4點(diǎn)點(diǎn)DFT:可知:可知:時(shí)域上:時(shí)域上: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)給出給出例子:求例子:求 N=23=8點(diǎn)點(diǎn)FFT變換變換 按按N=8N/2=4,做,做4點(diǎn)的點(diǎn)的DFT:N=8點(diǎn)的直接點(diǎn)的直接DFT的計(jì)算量為:的計(jì)算量為:復(fù)乘:復(fù)乘:N2次次=64次次 復(fù)加:復(fù)加:N(N-1)次次=87=56次次)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN 12/,0 Nk
14、此外,還有此外,還有4個(gè)蝶形結(jié),每個(gè)蝶形結(jié)需要個(gè)蝶形結(jié),每個(gè)蝶形結(jié)需要1次復(fù)乘,次復(fù)乘,2次復(fù)加。次復(fù)加。一共是:復(fù)乘一共是:復(fù)乘4次,復(fù)加次,復(fù)加8次。次。得到得到X1(k)和和X2(k)需要:需要:復(fù)乘:復(fù)乘:(N/2)2+(N/2)2次次=32次次 復(fù)加:復(fù)加:N/2(N/2-1)+N/2(N/2-1)=12+12=24次次用分解的方法得到用分解的方法得到X(k)需要:需要:復(fù)乘:復(fù)乘:32+4=36次次 復(fù)加:復(fù)加:24+8=32次次N點(diǎn)點(diǎn)DFT的一次時(shí)域抽取分解圖的一次時(shí)域抽取分解圖(N=8)4點(diǎn)點(diǎn)DFT4點(diǎn)點(diǎn)DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1
15、(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)38W28W18W08W 奇奇序序列列、偶偶序序列列、)6()2()4()0(:)(1xxxxrx 奇奇序序列列、偶偶序序列列、同同理理:)7()3()5()1(:)(2xxxxrx因?yàn)橐驗(yàn)?點(diǎn)點(diǎn)DFT還是比較麻煩,所以再繼續(xù)分解。還是比較麻煩,所以再繼續(xù)分解。若將若將N/2(4點(diǎn)點(diǎn))子序列按奇子序列按奇/偶分解成兩個(gè)偶分解成兩個(gè)N/4點(diǎn)點(diǎn)(2點(diǎn)點(diǎn))子子序列。即對(duì)將序列。即對(duì)將x1(r)和和x2(r)分解成奇、偶兩個(gè)分解成奇、偶兩個(gè)N/4點(diǎn)點(diǎn)(2點(diǎn)點(diǎn))點(diǎn)的
16、子序列。點(diǎn)的子序列。1,0)1.0()()12()()2(44131 lllxlxlxlxN此此處處,奇奇序序列列偶偶序序列列設(shè)設(shè):1,0)1.0()()12()()2(46252 lllxlxlxlxN此此處處,奇奇序序列列偶偶序序列列設(shè)設(shè):那么,那么,X1(k)又可表示為又可表示為 14/0)12(2/114/022/11)12()2()(NlklNNllkNWlxWlxkX 14/04/42/14/04/3)()(NllkNkNNllkNWlxWWlx)()(42/3kXWkXKN 1,.1,0)()()()()()(442/34142/31 NkNNkNkkXWkXkXkXWkXkX
17、14/0)12(2/214/022/22)21()2()(NlklNNllkNWlxWlxkX 14/04/62/14/04/5)()(NllkNkNNllkNWlxWWlx1,.1,0)()()()()()(462/54262/52 NkNNkNkkXWkXkXkXWkXkXX2(k)也可以進(jìn)行相同的分解:也可以進(jìn)行相同的分解:注意:通常我們會(huì)把注意:通常我們會(huì)把 寫成寫成 。kNW2/kNW2)()(62/5kXWkXKN N點(diǎn)點(diǎn)DFT的第二次時(shí)域抽取分解圖的第二次時(shí)域抽取分解圖(N=8)2點(diǎn)點(diǎn)DFT2點(diǎn)點(diǎn)DFT2點(diǎn)點(diǎn)DFT2點(diǎn)點(diǎn)DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3
18、)x(7)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)08W28W08W28WX1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)38W28W18W08WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)4點(diǎn)點(diǎn)DFT4點(diǎn)點(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(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)38W28W18W08W)1()0()()()(32314/04/333xWxWlxl
19、xDFTkXkNlklN )1()0()1()0()1()1()0()0(30233123330233xWxxWxXxWxX 8808WX3(0)X3(1)x(0)=x3(0)x(4)=x3(1)N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖運(yùn)算流圖(N=8)x(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)0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW3、DITFFT算法與直接計(jì)算算法與直接計(jì)算DFT運(yùn)算量的比較運(yùn)算量的比較22log2NNN 1)、N=2M的的DFT運(yùn)算可分成運(yùn)算可分成M級(jí),每一級(jí)有級(jí),每一
20、級(jí)有N/2個(gè)蝶形個(gè)蝶形 ,每個(gè)蝶形有一次復(fù)乘兩次復(fù)加。,每個(gè)蝶形有一次復(fù)乘兩次復(fù)加。NN2log2NN2log2)、所以、所以M級(jí)共有級(jí)共有 次復(fù)乘和次復(fù)乘和 次復(fù)加。次復(fù)加。3)、若直接計(jì)算、若直接計(jì)算DFT,需,需N2次復(fù)乘和次復(fù)乘和N(N-1)次復(fù)加。次復(fù)加。顯然,當(dāng)顯然,當(dāng)N較大時(shí),有:較大時(shí),有:例如,例如,N=210=1024時(shí)時(shí)221048576204.8(/2)log5120NNNFFT算法與直接計(jì)算算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線所需乘法次數(shù)的比較曲線4、DITFFT的運(yùn)算規(guī)律及編程思想的運(yùn)算規(guī)律及編程思想 FFT的每級(jí)(列)計(jì)算都是由的每級(jí)(列)計(jì)算都是由N個(gè)復(fù)數(shù)
21、數(shù)據(jù)(輸入)兩個(gè)復(fù)數(shù)數(shù)據(jù)(輸入)兩兩構(gòu)成一個(gè)蝶型(共兩構(gòu)成一個(gè)蝶型(共N/2個(gè)蝶形)運(yùn)算而得到另外個(gè)蝶形)運(yùn)算而得到另外N個(gè)復(fù)數(shù)個(gè)復(fù)數(shù)數(shù)據(jù)(輸出)。數(shù)據(jù)(輸出)。當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后,每一組運(yùn)算的結(jié)果,當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后,每一組運(yùn)算的結(jié)果,仍然存仍然存放在這同一組存儲(chǔ)器中放在這同一組存儲(chǔ)器中直到最后輸出。直到最后輸出。例:將例:將x(0)放在單元放在單元A(0)中,將中,將x(4)放在單元放在單元A(1)中,中,W80 放在一個(gè)暫存器中。放在一個(gè)暫存器中。將將x(0)+W80 x(4)送回送回A(0)單元單元將將x(0)-W80 x(4)送回送回A(1)單元單元08WX3(0)X3(1)
22、x(0)x(4)1)原位運(yùn)算原位運(yùn)算 (亦稱同址計(jì)算亦稱同址計(jì)算)x(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)0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW回顧:回顧:N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖運(yùn)算流圖(N=8)如上所述,如上所述,N點(diǎn)點(diǎn)DITFFT運(yùn)算流圖中,每級(jí)都有運(yùn)算流圖中,每級(jí)都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子個(gè)蝶形。每個(gè)蝶形都要乘以因子WNP,稱其為,稱其為旋旋轉(zhuǎn)因子轉(zhuǎn)因子,p稱為旋轉(zhuǎn)因子的指數(shù)。稱為旋轉(zhuǎn)因子的指數(shù)。2)旋轉(zhuǎn)因子的變化規(guī)律旋轉(zhuǎn)因子的變化規(guī)律 觀察觀察FFT
23、運(yùn)算流圖發(fā)現(xiàn),第運(yùn)算流圖發(fā)現(xiàn),第L級(jí)共有級(jí)共有2L-1個(gè)不同的個(gè)不同的旋轉(zhuǎn)因子。旋轉(zhuǎn)因子。N=23=8時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下:時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下:L=1時(shí),時(shí),WNp=WN/4J,N/4=21=2L,J=0L=2時(shí),時(shí),WNp=WN/2J,N/2=22=2L,J=0,1L=3時(shí),時(shí),WNp=WNJ,N =23=2L,J=0,1,2,3對(duì)對(duì)N=2M的一般情況,第的一般情況,第L級(jí)的旋轉(zhuǎn)因子為:級(jí)的旋轉(zhuǎn)因子為:12,.,1,012 LJPNJWWLMLMLMLN 222212,.,1,0122 LJNJNPNJWWWLMMLLMJp 2 設(shè)序列設(shè)序列x(n)經(jīng)時(shí)域抽選經(jīng)時(shí)域抽選(倒序倒序)
24、后,存入數(shù)組后,存入數(shù)組X中。中。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn),應(yīng)用原位個(gè)點(diǎn),應(yīng)用原位計(jì)算,則蝶形運(yùn)算可表示成如下形式:計(jì)算,則蝶形運(yùn)算可表示成如下形式:pNLLLpNLLLWBJXJXBJXWBJXJXJX)()()()()()(1111 MJpLLM,.,2,1L12,.,1,0J21 ,式式中中:下標(biāo)下標(biāo)L表示第表示第L級(jí)運(yùn)算,級(jí)運(yùn)算,XL(J)則表示第則表示第L級(jí)運(yùn)算級(jí)運(yùn)算后數(shù)組元素后數(shù)組元素X(J)的值。的值。3)編程思想及流程圖編程思想及流程圖開(kāi)始開(kāi)始送入送入x(n)和和N=2M調(diào)整輸入調(diào)整輸入x(n)的順序的順序for(L=1;L=M;L+)
25、B=2L-1for(J=0;J=B-1;J+)p=J2M-Lfor(k=J;k=N-1;k=k+2L)pNpNWBkXkXBkXWBkXkXkX)()()()()()(輸出結(jié)果輸出結(jié)果結(jié)束結(jié)束4)碼位倒序)碼位倒序 由由N=8蝶形圖看出:原位計(jì)算時(shí),蝶形圖看出:原位計(jì)算時(shí),F(xiàn)FT輸出的輸出的X(k)的次序正好是順序排列的,即的次序正好是順序排列的,即X(0)X(7),但輸?shù)斎肴離(n)都不能按自然順序存入到存儲(chǔ)單元中,而是都不能按自然順序存入到存儲(chǔ)單元中,而是按按x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)的順序存入的順序存入存儲(chǔ)單元,即為亂序輸入,順序輸出
26、。存儲(chǔ)單元,即為亂序輸入,順序輸出。這種順序看起來(lái)相當(dāng)雜亂,然而它是這種順序看起來(lái)相當(dāng)雜亂,然而它是有規(guī)律有規(guī)律的。的。即即碼位倒讀規(guī)則碼位倒讀規(guī)則。自然順序自然順序n二進(jìn)制碼表示二進(jìn)制碼表示碼位倒讀碼位倒讀碼位倒置順序碼位倒置順序n以以N=8為例:為例:0123456700000101001110010111011100010001011000110101111104261537看出:看出:碼位倒讀后碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)A(0)A(1)A(2)A(3)A(4)A(5)
27、A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)倒序規(guī)律倒序規(guī)律正序序列已在數(shù)組正序序列已在數(shù)組A 中,輸中,輸 入入 NLH=N/2 ,J=LH ,N1=N-2J=J-kk=k/2 k=LHJkJ=J+k T=A(I)A(I)=A(J)A(J)=Tfor(i=1;i1:螺線內(nèi)縮:螺線內(nèi)縮 W01:螺線外伸螺線外伸當(dāng)當(dāng)W0=1,則表示半徑為,則表示半徑為A0的一段圓弧的一段圓弧若又有若又有A0=1,則表示單位圓上的一段圓弧,則表示單位圓上的一段圓弧若又有若又有 ,M=N,即為序列的,即為序列的DFT
28、。000,2/N求抽樣點(diǎn)處的求抽樣點(diǎn)處的z變換:變換:1100()()()NNnnnkkknnX zx n zx n A W0,1,.,1kM222 1/2()nknkkn由222()12220()()nk nkNnknX zx n A WWW得 222()12220()knk nNnnWx n A WWNM次復(fù)乘次復(fù)乘 (N-1)M次復(fù)加次復(fù)加22()()nng nx n A W令 22()nh nW0,1,.,1nN221220()()()()*()kkNknX zWg n h knWg kh k則 0,1,.,1kM222()12220()knk nNnknX zWx n A WW2 2
29、、CZTCZT的實(shí)現(xiàn)步驟及運(yùn)算量的估算的實(shí)現(xiàn)步驟及運(yùn)算量的估算 22()()nng nx n A W其中 22()nh nW0,1,.,1nN222()12220()knk nNnknX zWx n A WW0,1,.,1kM():0 1g nN():(1)(1)h nNM1NM 點(diǎn)()*():22h ng nNM()0 1kX zkM12mLNML 且22()01()01nnA Wx nnNg nNnL210()()()LjrnLnG rFFT g ng n e01rL1LNM2mL 1)選擇選擇 ,且,且2)形成形成L點(diǎn)序列點(diǎn)序列g(shù)(n):(3N)求其求其L點(diǎn)點(diǎn)FFT:(L/2*log2L
30、)2/2nnnCA W系數(shù) 22(1)(1)/2/21/211()nnnnnnnnCAWA WW WAC D1/2111/211nnnnDW WAW WWAWD1/21001DWAC3)形成)形成L點(diǎn)序列點(diǎn)序列h(n):222()201()011nL nWnMh nMnLNWLNnL 210()()()LjrnLnH rFFT h nh n e01rL求其求其L點(diǎn)點(diǎn)FFT:(L/2*log2L)(2N)4)求乘積)求乘積()()()Q rH rG r2101()()()()LjrnLnq kIFFT Q rH r G r eL()()()Mq kq k Rk取 22()()kkX zWq k01kM(M)(L)5)求)求L點(diǎn)點(diǎn)IFFT的的 q(k)(L/2*log2L)6)求得抽樣點(diǎn)的)求得抽樣點(diǎn)的z變換變換:23log52FmLLNLM3、CZT算法的優(yōu)點(diǎn)算法的優(yōu)點(diǎn)1)N,M可為任意數(shù),可不等可為任意數(shù),可不等21jNAMNWe5)當(dāng)當(dāng) ,時(shí),時(shí),CZT=DFT,解決了解決了N為素?cái)?shù)的快速算法問(wèn)題為素?cái)?shù)的快速算法問(wèn)題4)z0任意,從任意頻率開(kāi)始,便于窄帶高分辨率分析任意,從任意頻率開(kāi)始,便于窄帶高分辨率分析3)周線可以是螺線,而不一定是圓弧周線可以是螺線,而不一定是圓弧02)任意,易調(diào)整頻率分辨率任意,易調(diào)整頻率分辨率
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)6整理和復(fù)習(xí)2圖形與幾何第7課時(shí)圖形的位置練習(xí)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)6整理和復(fù)習(xí)2圖形與幾何第1課時(shí)圖形的認(rèn)識(shí)與測(cè)量1平面圖形的認(rèn)識(shí)練習(xí)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)6整理和復(fù)習(xí)1數(shù)與代數(shù)第10課時(shí)比和比例2作業(yè)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)4比例1比例的意義和基本性質(zhì)第3課時(shí)解比例練習(xí)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)3圓柱與圓錐1圓柱第7課時(shí)圓柱的體積3作業(yè)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)3圓柱與圓錐1圓柱第1節(jié)圓柱的認(rèn)識(shí)作業(yè)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)2百分?jǐn)?shù)(二)第1節(jié)折扣和成數(shù)作業(yè)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)1負(fù)數(shù)第1課時(shí)負(fù)數(shù)的初步認(rèn)識(shí)作業(yè)課件新人教版
- 2023年六年級(jí)數(shù)學(xué)上冊(cè)期末復(fù)習(xí)考前模擬期末模擬訓(xùn)練二作業(yè)課件蘇教版
- 2023年六年級(jí)數(shù)學(xué)上冊(cè)期末豐收?qǐng)@作業(yè)課件蘇教版
- 2023年六年級(jí)數(shù)學(xué)上冊(cè)易錯(cuò)清單十二課件新人教版
- 標(biāo)準(zhǔn)工時(shí)講義
- 2021年一年級(jí)語(yǔ)文上冊(cè)第六單元知識(shí)要點(diǎn)習(xí)題課件新人教版
- 2022春一年級(jí)語(yǔ)文下冊(cè)課文5識(shí)字測(cè)評(píng)習(xí)題課件新人教版
- 2023年六年級(jí)數(shù)學(xué)下冊(cè)6整理和復(fù)習(xí)4數(shù)學(xué)思考第1課時(shí)數(shù)學(xué)思考1練習(xí)課件新人教版