版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
高等院校公共課系列精品教材第十章快速傅里葉變換高等院校公共課系列精品教材電子信息科學與工程類改進DFT計算的方法0101改進DFT計算的方法一、直接計算DFT的特點根據定義,長度為N的有限長序列x(n)的DFT為由上式看出DFT的計算中只包含乘法和加法運算。如果x(n)為復數序列,則根據上式完成N點X(k)的運算次數分析如表10.1所示。01改進DFT計算的方法可見,一次復數乘法包括了四次實數乘法和二次實數加法;一次復數加法則需要二次實數加法。所以對某一k值,計算X(k)需要4N次實數乘法2N+2(N-1)=2(2N-1)次實數加法。一個完整的
N點DFT運算共需要4N2次實數乘法和2N(2N-1)次實數加法。當N較大時,計算DFT需要消耗大量
的時間,很難滿足系統(tǒng)的實時性要求。所以改進DFT算法,提高運算效率是非常必要的。一、直接計算DFT的特點復數運算是由實數運算來完成的,可以寫成01改進DFT計算的方法二、減少運算量的方法的特點,可以減少DFT的運算次數。觀察DFT運算可以看出,利用旋轉因子有如下特性。(1)對稱性:周期性:可約性:(4)特殊值:按時間抽取(DIT)的FFT算法0202按時間抽取(DIT)的FFT算法一、算法原理設序列長度為N=2M(M為整數)。如果給定長度不滿足這個條件,可以通過補零滿足要求。這種長度N為2的整數冪的FFT,稱為基2-FFT。根據其形狀又稱其為蝶形運算單元。圖中左側X1(k)和X2(k)為輸入,右側為輸出??梢钥闯?每個蝶形運算單元,需要一次復數乘法及兩次復數加(減)法。完成一個蝶形運算需要一次復數乘法和兩次復數加法。02按時間抽取(DIT)的FFT算法二、時間抽取FFT的運算量由8點時間抽取FFT流圖可見,一個N=2M點序列的DFT經過M次分解,可以分解成M級蝶
形運算,每一級都由N/2個蝶形運算組成。因此全部N點的FFT共有號N/2×M個蝶形運算。每個蝶形運算需要一次復數乘法和二次復數加法運算。所以N點的FFT所需的運算次數如下。復數乘法:復數加法:而直接計算DFT需要N2次復數乘法和N(N-1)次復數加法。02按時間抽取(DIT)的FFT算法三、時間抽取法的運算特點1.蝶形運算一個N=2M點序列的DFT經過M次分解,全部運算都變?yōu)榈芜\算。每個蝶形運算單元完成下述基本遞推運算:2.原位運算原位運算就是將蝶形運算的結果仍然保存在原輸入量的存儲單元中。即某一列的
N個數據送到存儲器后,經蝶形運算,其結果為另一列數據,它們以蝶形為單位仍存儲在這一組存儲器中,直到最后輸出,中間無需其他存儲器。每列的N/2個蝶形運算全部完成后,再開始下一列的蝶形運算。02按時間抽取(DIT)的FFT算法三、時間抽取法的運算特點倒位序所謂倒位序,就是將二進制數的最高有效位到最低有效位的位序進行顛倒排列而得到的二進制數。倒位序的二進制數通常又稱倒序數。蝶形運算兩節(jié)點間距離第m級蝶形運算可寫成的確定在時域抽取法的FFT運算流圖中,每一級都有N/2個蝶形運算,每個蝶形運算都要乘以旋轉因子 。每一級旋轉因子都不相同,但排列卻很有規(guī)律。按頻率抽取(DIF)的FFT算法0303按頻率抽取(DIF)的FFT算法每個蝶形運算需要一次復數乘法和二次復數加法運算。所以頻率抽取法運算量與時間抽取法相同,都需要復數乘法 次,復數加法:NM=Nlog2N次。一、算法原理03按頻率抽取(DIF)的FFT算法二、運算特點頻率抽取法的運算特點與時間抽取法基本相同,都是通過蝶形運算完成,也是原位運算,其輸人是正常位序,輸出為倒位序。按流圖轉置定理,即將流圖的所有支路方向取反,交換輸入輸出,系數保持不變,可得到流圖的轉置形式。頻率抽取法和時間抽取法是兩種等價的FFT運算。FFT算法流圖并不唯一,在上面兩種FFT的算法流圖的基礎上稍作變換,可以得到其他形式的FFT流圖。這是因為對任何流圖只要保證各節(jié)點所連
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 湘教版九年級上期信息技術教案
- 川教版信息技術六年級下冊全冊教案【新教材】
- 2024年金融信息化行業(yè)發(fā)展前景分析:金融信息化國內市場規(guī)模約為1500億元
- 2024-2025學年小學科學一年級上冊大象版(2024)教學設計合集
- 2024-2025學年中職中職專業(yè)課西餐74 旅游大類教學設計合集
- 2024年教師師德師風個人總結
- 2024-2025學年初中信息技術(信息科技)七年級全冊河北大學版(2012)教學設計合集
- 2024-2025學年初中勞動七年級上冊人教版教學設計合集
- 小學數學“通分”說課稿
- 2024年3月上半年四川綿陽三臺縣招考聘用教師84人筆試歷年典型考點解題思路附帶答案詳解
- GB/T 3487-2024乘用車輪輞規(guī)格系列
- GB/T 22517.2-2024體育場地使用要求及檢驗方法第2部分:游泳場地
- 2024年秋季學期新外研版三年級上冊英語課件 Unit 2 第4課時 Hit it big Wrap up Let's explore1
- 湖北聯(lián)投集團2024校園招聘【298人】易考易錯模擬試題(共200題)試卷后附參考答案
- 慶祝第75個國慶節(jié)共筑中國夢大國華誕繁盛共享課件
- Unit 4 My Favourite Subject Section A Pronunciation 1-2f 教學設計 2024-2025學年人教版英語七年級上冊
- 南充市大學生鄉(xiāng)村醫(yī)生招聘筆試真題2023
- LNG加氣站2024年度安全教育培訓計劃
- 4曹沖稱象 公開課一等獎創(chuàng)新教學設計(2課時)
- 安慶衛(wèi)生系統(tǒng)考試真題
- 2024年中級纖維檢驗員職業(yè)鑒定考試題庫(含答案)
評論
0/150
提交評論