數(shù)字信號處理快速付里葉變換FFT_第1頁
數(shù)字信號處理快速付里葉變換FFT_第2頁
數(shù)字信號處理快速付里葉變換FFT_第3頁
數(shù)字信號處理快速付里葉變換FFT_第4頁
數(shù)字信號處理快速付里葉變換FFT_第5頁
已閱讀5頁,還剩22頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡介

1、第四章快速(kui s)付里葉變換(FFT)Fast Fouriet Transformer共二十七頁第一節(jié) 引 言一、快速(kui s)付里葉變換FFT有 限 長 序 列 通 過 離 散 傅 里 葉 變 換 (D F T) 將 其 頻 域 離 散 化 成 有 限 長 序 列 . 但 其 計(jì)算(j sun) 量 太 大, 很 難 實(shí) 時 地 處 理 問 題 , 因 此 引 出 了 快 速 傅 里 葉 變 換(FFT) . FFT 并 不 是 一 種 新 的 變 換 形 式 ,它 只 是 DFT 的 一 種 快 速 算 法 . 并 且 根 據(jù) 對 序 列 分 解 與 選 取 方 法 的 不 同

2、而 產(chǎn) 生 了 FFT 的 多 種 算 法 . FFT 在 離 散 傅 里 葉 反 變 換 、 線 性 卷 積 等 方 面 也 有 重 要 應(yīng) .共二十七頁二、FFT的產(chǎn)生(chnshng) 1965年庫利-圖基在計(jì)算數(shù)學(xué)(Mathematic of Computation )雜志上發(fā)表了著名(zhmng)的“機(jī)器計(jì)算付里級數(shù)的一種算法”文章,提出一種快速計(jì)算DFT的方法和計(jì)算機(jī)程序-揭開了FFT發(fā)展史上的第一頁。促使FFT算法產(chǎn)生原因還有1967年至1968年間FFT的數(shù)字硬件制成,電子數(shù)字計(jì)算機(jī)的條件, 使DFT的運(yùn)算大簡化了。 FFT出現(xiàn)后使DFT的運(yùn)算大大簡化,運(yùn)算時間一般可縮短一二個

3、數(shù)量級之多,從而使DFT的運(yùn)算在實(shí)際中真正得到了廣泛的應(yīng)用。 共二十七頁三、本章主要(zhyo)內(nèi)容1.直接計(jì)算DFT算法存在的問題(wnt)及改進(jìn)途徑。2.多種DFT算法時間抽取算法DIT算法頻率抽取算法DIF算法線性調(diào)頻Z變換即CZT法)3.FFT的應(yīng)用共二十七頁第二節(jié)直接計(jì)算(j sun)DFT算法存在的問題及改進(jìn)途徑共二十七頁一、直接(zhji)計(jì)算DFT計(jì)算量問題提出: 設(shè)有限長序列x(n),非零值長度為N,計(jì)算(j sun)對x(n)進(jìn)行一次DFT運(yùn)算,共需多大的運(yùn)算工作量?共二十七頁1.比較(bjio)DFT與IDFT之間的運(yùn)算量其中(qzhng)x(n)為復(fù)數(shù), 也為復(fù)數(shù)所以D

4、FT與IDFT二者計(jì)算量相同。共二十七頁2.以DFT為例,計(jì)算(j sun)DFT復(fù)數(shù)運(yùn)算量計(jì)算一個X(k)(一個頻率(pnl)成分)值,運(yùn)算量為例k=1則要進(jìn)行N次復(fù)數(shù)乘法+(N-1)次復(fù)數(shù)加法所以,要完成整個DFT運(yùn)算,其計(jì)算量為:N*N次復(fù)數(shù)相乘+N*(N-1)次復(fù)數(shù)加法共二十七頁3.一次復(fù)數(shù)乘法換算(hun sun)成實(shí)數(shù)運(yùn)算量復(fù)數(shù)運(yùn)算要比加法運(yùn)算復(fù)雜,需要的運(yùn)算時間長。一個復(fù)數(shù)乘法(chngf)包括4個實(shí)數(shù)乘法和2個實(shí)數(shù)相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad) 4次實(shí)數(shù)乘法2次實(shí)數(shù)加法共二十七頁4.計(jì)算DFT需要(xyo)的實(shí)數(shù)運(yùn)算量每運(yùn)算一個X(k)的值,需

5、要進(jìn)行4N次實(shí)數(shù)相乘和 2N+2(N-1)=2(2N-1)次實(shí)數(shù)相加.整個DFT運(yùn)算量為:4N2次實(shí)數(shù)相乘和2N(2N-1)次實(shí)數(shù)相加.由此看出(kn ch):直接計(jì)算DFT時,乘法次數(shù)與加法次數(shù)都是和N2成比例的。當(dāng)N很大時,所需工作量非??捎^。共二十七頁例1:當(dāng)N=1024點(diǎn)時,直接計(jì)算DFT需要:N2=1048576次,即一百多萬次的復(fù)乘運(yùn)算這對實(shí)時性很強(qiáng)的信號處理(如雷達(dá)信號處理)來講,它對計(jì)算速度有十分苛刻的要求-迫切需要改進(jìn)DFT的計(jì)算方法,以減少總的運(yùn)算次數(shù)。例2:石油勘探,24道記錄,每道波形(b xn)記錄長度5秒,若每秒抽樣500點(diǎn)/秒,每道總抽樣點(diǎn)數(shù)=500*5=2500

6、點(diǎn)24道總抽樣點(diǎn)數(shù)=24*2500=6萬點(diǎn)DFT運(yùn)算時間=N2=(60000)2=36*108次共二十七頁二、改善DFT運(yùn)算(yn sun)效率的基本途徑能否減少運(yùn)算量,從而縮短計(jì)算時間呢?仔細(xì)觀察DFT的運(yùn)算就可看出, 利用系數(shù)Wnk的以下(yxi)固有特性,就可減少運(yùn)算量: (1) WNnk的對稱性 (2) WNnk的周期性 (3) WNnk的可約性 共二十七頁將長序列(xli)DFT利用對稱性和周期性分解為短序列DFT因?yàn)?yn wi)DFT的運(yùn)算量與N2成正比的如果一個大點(diǎn)數(shù)N的DFT能分解為若干小點(diǎn)數(shù)DFT的組合,則顯然可以達(dá)到減少運(yùn)算工作量的效果。共二十七頁把N點(diǎn)數(shù)據(jù)(shj)分成

7、二半:其運(yùn)算量為:再分二半:+=+=這樣一直分下去(xi q),剩下兩點(diǎn)的變換。共二十七頁快速付里時變換(binhun)(FFT)就是在此特性基礎(chǔ)上發(fā)展起來的,并產(chǎn)生了多種FFT算法,其基本上可分成兩大類:按抽取方法分: 時間抽取法(DIT) 頻率抽取法(DIF)按“基數(shù)”分: 基-2FFT算法;基-4FFT算法;混合基FFT算法;分裂基FFT算法其它方法:線性調(diào)頻Z變換(CZT法)共二十七頁第三節(jié)基-2按時間(shjin)抽取的FFT算法庫利-圖基算法Decimation-in-Time(DIT)(Coolkey-Tukey)共二十七頁一.算法(sun f)原理(基2FFT)(一)N/2點(diǎn)D

8、FT1.先將x(n)按n的奇偶分為兩組作DFT,設(shè)N=2L ,不足時,可補(bǔ)些零。這樣(zhyng)有: n為偶數(shù)時: n為奇數(shù)時:共二十七頁由于(yuy): 所以,上式可表示為:n為偶數(shù)(u sh)n為奇數(shù)共二十七頁 其中,2.兩點(diǎn)結(jié)論: (1) X1(k),X2(k)均為N/2點(diǎn)的DFT。 (2) X(k)=X1(k)+W X2(k)只能確定(qudng)出 X(k)的k= 個;即前一半的結(jié)果。kN共二十七頁 同理, 這就是說,X1(k),X2(k)的后一半,分別(fnbi) 等于其前一半的值。3.X(k)的后一半(ybn)的確定由于 (周期性),所以:共二十七頁 可見,X(k)的后一半(y

9、bn),也完全由X1(k),X2(k)的前一半所確定。 *N點(diǎn)的DFT可由兩個N/2點(diǎn)的DFT來計(jì)算。又由于(yuy) ,所以共二十七頁實(shí)現(xiàn)上式運(yùn)算(yn sun)的流圖稱作蝶形運(yùn)算(yn sun) 前一半(ybn)4.蝶形運(yùn)算 后一半(N/2個蝶形)(前一半)(后一半)1 1 11-1由X1(k)、X 2(k)表示X(k)的運(yùn)算是一種特殊的運(yùn)算-碟形運(yùn)算共二十七頁(1)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):復(fù)加次數(shù):(2)兩個(lin )N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):復(fù)加次數(shù): (3)N/2個蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù):復(fù)加次數(shù): 5.計(jì)算(j sun)工作量分析復(fù)乘:復(fù)加:總共運(yùn)算量:按奇

10、、偶分組后的計(jì)算量:N點(diǎn)DFT的復(fù)乘為N2 ;復(fù)加N(N-1);與分解后相比可知,計(jì)算工作點(diǎn)差不多減少 一半。共二十七頁 例如(lr) N=8 時的DFT,可以分解為兩個N/2=4點(diǎn)的DFT.具體方法如下: (1)n為偶數(shù)時,即 分別記作: 共二十七頁 (2) n為奇數(shù)(j sh)時,分別記作:共二十七頁 x1(0)=x(0) x1(1)=x(2) N/2點(diǎn) x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2點(diǎn) x2(2)=x(5) DFT x2(3)=x(7) X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)對X1(k)和X2 (k)進(jìn)行蝶形運(yùn)算,前半部為 X(0)-X(3),后半部分為X(4)-X(7) 整個(zhngg)過程如下圖所示:共二十七頁內(nèi)容摘要第四章快速付里葉變換(FFT)Fast Fouriet Transformer。一、直接計(jì)算DFT計(jì)算量。所以,要完成整個DFT運(yùn)算,其計(jì)算量為:。一個復(fù)數(shù)乘法包括4個實(shí)數(shù)乘法和2個實(shí)數(shù)相法。整個DFT運(yùn)算量為:4N2次實(shí)數(shù)相乘和2N(2N-1)次實(shí)數(shù)相加.。由此看出:直接計(jì)算DFT時,乘法次

溫馨提示

  • 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)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論