按時(shí)間抽取的FFT算法講義_第1頁
按時(shí)間抽取的FFT算法講義_第2頁
按時(shí)間抽取的FFT算法講義_第3頁
按時(shí)間抽取的FFT算法講義_第4頁
按時(shí)間抽取的FFT算法講義_第5頁
已閱讀5頁,還剩23頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、時(shí)間抽選法時(shí)間抽選法DIT: Decimation-In-Time頻率抽選法頻率抽選法DIF: Decimation-In-Frequency2022-2-2527-2 按按時(shí)間抽取的FFT算法一、按時(shí)間抽取的算法原理二、按時(shí)間抽取的算法特點(diǎn)三、按時(shí)間抽取FFT算法的其他形式2022-2-253一、按時(shí)間抽取的算法原理設(shè)序列點(diǎn)數(shù) N = 2L,L 為整數(shù)。若不滿足,則補(bǔ)零N為2的整數(shù)冪的FFT算法稱基-2FFT算法。將序列x(n)按n的奇偶分成兩組: 12221xrx rxrxr0,1,.,/2 1rN2022-2-254 則則x(n)的的DFT: 111000NNNnknknkNNNnnnX

2、kx n Wx n Wx n Wn為偶數(shù)n為奇數(shù)/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN2022-2-255 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又2022-2-2561212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW

3、 Xk0,1,.,/2 1kN 一個(gè)一個(gè)“蝶形運(yùn)算蝶形運(yùn)算”包含包含1次乘法,次乘法,2次加法次加法2022-2-2572022-2-258復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(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ì)分解后的運(yùn)算量:分解后的運(yùn)算量:運(yùn)算量減少了近一半運(yùn)算量減少了近一半22/2/2/2NNN2/2 1/2N NNN2022-2-259N / 2仍為偶數(shù),進(jìn)一步分解:N / 2 N / 41314(2 )( )(21)( )xl

4、xlxlxl0,1,.,/41lN13/ 2413/ 24()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 102/2kkNNWW統(tǒng)一系數(shù):同理同理:25/ 2625/ 26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 其中:其中:552( )( )(2 )XkDFT xlDFT xl662( )( )(21)XkDFT xlDFT xl0,1,.,/ 41lN這樣逐級分解,直到這樣逐級分解,直到2點(diǎn)點(diǎn)DFT2022-2-2511基2時(shí)間抽取FFT算法流圖N=2xk=x0, x1 1 0002xWxX 1 0 1 12

5、xWxX0 x 1 x0X-102W 1 X 1 002xWx2022-2-25124點(diǎn)基2時(shí)間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點(diǎn)DFT2點(diǎn)DFT111104W14W02W02WX 0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm2022-2-25134點(diǎn)基2時(shí)間抽取FFT算法流圖2022-2-25148點(diǎn)基2時(shí)間抽取FFT算法流圖4點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3 ,

6、2 , 1 , 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm2022-2-25154點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W8點(diǎn)基2時(shí)間抽取FFT算法流圖2022-2-2516基基2時(shí)間抽取時(shí)間抽取FFT算法算法第一級第一級第二級第二級第三級第三級2022-2-2517二、按時(shí)間抽取的算法特點(diǎn)1.計(jì)算速度 當(dāng)N = 2L時(shí),共有L級蝶形,每級N / 2個(gè)蝶形,每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。2log22FNNmLN

7、復(fù)數(shù)乘法復(fù)數(shù)乘法:2logFaNLNN復(fù)數(shù)加法復(fù)數(shù)加法:222()2()loglog2FFmDFTNNNmFFTNN比較比較DFT 2022-2-25182022-2-2519算法的計(jì)算復(fù)雜度算法的計(jì)算復(fù)雜度復(fù)乘次數(shù)NN 2NN2log22022-2-2520例 .如果一臺通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ,每次復(fù)加 ,用它來計(jì)算512點(diǎn)的 ,問直接計(jì)算需要多少時(shí)間,用 運(yùn)算需要多少時(shí)間。 5 s0.5 s DFT x nFFT解:(1)直接利用 計(jì)算: 復(fù)乘次數(shù)為 ,復(fù)加次數(shù)為 。 DFT2N1N N 復(fù)乘所需時(shí)間 626215 105 105121.31072TNs復(fù)加所需時(shí)間 6260.5

8、 1010.5 10512512 10.130816TNNs所以直接利用DFT 計(jì)算所需時(shí)間: 121.441536TTTs2022-2-2521復(fù)乘所需時(shí)間 612625 10log25125 10log 5120.011522NTNs 622620.5 10log0.5 10512log 5120.002304TNNs復(fù)加所需時(shí)間 所以用 FFT 計(jì)算所需時(shí)間 120.013824TTTs(2) 利用 計(jì)算: 復(fù)乘次數(shù)為 ,復(fù)加次數(shù)為 。 FFT2log2NN2logNN222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序00000000100410010102201011063011001141001015510101136110111771112102()nn n n0 122()nn nn2 102( )()x nnn n n2022-2-2523倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x1

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論