數(shù)字信號處理快速傅里葉變換ppt課件

《數(shù)字信號處理快速傅里葉變換ppt課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)字信號處理快速傅里葉變換ppt課件（51頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

第四章快速傅立葉變換FastFourierTransform 1 主要內(nèi)容 第一節(jié)直接計(jì)算DFT的問題及改進(jìn)途徑第二節(jié)改善DFT運(yùn)算效率的基本途徑第三節(jié)按時(shí)間抽選的基2 FFT算法第四節(jié)按頻率抽選的基2 FFT算法 2 第一節(jié)直接計(jì)算DFT的問題及改進(jìn)途徑 1 問題的提出 設(shè)有限長序列x n 非零值長度為N 若對x n 進(jìn)行一次DFT運(yùn)算 共需多大的運(yùn)算工作量 計(jì)算成本 計(jì)算速度 3 2 DFT的運(yùn)算量 回憶DFT和IDFT的變換式 4 計(jì)算機(jī)運(yùn)算時(shí) 編程實(shí)現(xiàn) 以DFT為例 5 運(yùn)算量 a jb c jd ac bd j bc ad 6 例 計(jì)算一個(gè)N點(diǎn)DFT 共需N2次復(fù)乘 以做一次復(fù)乘1 s計(jì) 若N 4096 所需時(shí)間為 例 石油勘探 有24個(gè)通道的記錄 每通道波形記錄長度為5秒 若每秒抽樣500點(diǎn) 秒 1 每道總抽樣點(diǎn)數(shù) 500 5 2500點(diǎn)2 24道總抽樣點(diǎn)數(shù) 24 2500 6萬點(diǎn)3 DFT復(fù)乘運(yùn)算時(shí)間 N2 60000 2 36 108次 7 由于計(jì)算量大 且要求相當(dāng)大的內(nèi)存 難以實(shí)現(xiàn)實(shí)時(shí)處理 限制了DFT的應(yīng)用 長期以來 人們一直在尋求一種能提高DFT運(yùn)算速度的方法 FFT便是Cooley Tukey在1965年提出的的快速算法 它可以使運(yùn)算速度提高幾百倍 從而使數(shù)字信號處理學(xué)科成為一個(gè)新興的應(yīng)用學(xué)科 8 第二節(jié)改善DFT運(yùn)算效率的基本途徑 1 利用DFT運(yùn)算的系數(shù)的固有對稱性和周期性 改善DFT的運(yùn)算效率 1 對稱性2 周期性3 可約性 9 10 2 將長序列DFT利用對稱性和周期性分解為短序列DFT的思路 因?yàn)镈FT的運(yùn)算量與N2成正比的 如果一個(gè)大點(diǎn)數(shù)N的DFT能分解為若干小點(diǎn)數(shù)DFT的組合 則顯然可以達(dá)到減少運(yùn)算工作量的效果 11 N點(diǎn)DFT 復(fù)乘 12 FFT算法的基本思想 利用DFT系數(shù)的特性 合并DFT運(yùn)算中的某些項(xiàng)把長序列DFT 短序列DFT 從而減少運(yùn)算量 FFT算法分類 時(shí)間抽選法DIT Decimation In Time頻率抽選法DIF Decimation In Frequency 13 第三節(jié)按時(shí)間抽選的基2 FFT算法 1 算法原理 設(shè)輸入序列長度為N 2M M為正整數(shù) 將該序列按時(shí)間順序的奇偶分解為越來越短的子序列 稱為基2按時(shí)間抽取的FFT算法 也稱為Coolkey Tukey算法 其中基2表示 N 2M M為整數(shù) 若不滿足這個(gè)條件 可以人為地加上若干零值 加零補(bǔ)長 使其達(dá)到N 2M 14 先將x n 按n的奇偶分為兩組 作變量置換 當(dāng)n 偶數(shù)時(shí) 令n 2r 當(dāng)n 奇數(shù)時(shí) 令n 2r 1 分組 變量置換 得到 15 帶入DFT中 16 所以 由于 17 X1 k X2 k 只有N 2個(gè)點(diǎn) 以N 2為周期 而X k 卻有N個(gè)點(diǎn) 以N為周期 要用X1 k X2 k 表達(dá)全部的X k 值 還必須利用WN系數(shù)的周期特性 18 又考慮到的對稱性 有 19 蝶形運(yùn)算流圖符號 說明 1 左邊兩路為輸入 2 右邊兩路為輸出 3 中間以一個(gè)小圓表示加 減運(yùn)算 右上路為相加輸出 右下路為相減輸出 1個(gè)蝶形運(yùn)算需要1次復(fù)乘 2次復(fù)加 20 運(yùn)算量減少了近一半 分解后的運(yùn)算量 21 先將N 8點(diǎn)的DFT分解成2個(gè)4點(diǎn)DFT 可知 時(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)FFT變換按N 8 N 2 4 做4點(diǎn)的DFT 22 N 8點(diǎn)的直接DFT的計(jì)算量為 復(fù)乘 N2次 64次復(fù)加 N N 1 次 8 7 56次 此外 還有4個(gè)蝶形結(jié) 每個(gè)蝶形結(jié)需要1次復(fù)乘 2次復(fù)加 一共是 復(fù)乘4次 復(fù)加8次 得到X1 k 和X2 k 需要 復(fù)乘 N 2 2 N 2 2次 32次復(fù)加 N 2 N 2 1 N 2 N 2 1 12 12 24次 用分解的方法得到X k 需要 復(fù)乘 32 4 36次復(fù)加 24 8 32次 23 N點(diǎn)DFT的一次時(shí)域抽取分解圖 N 8 24 因?yàn)?點(diǎn)DFT還是比較麻煩 所以再繼續(xù)分解 若將N 2 4點(diǎn) 子序列按奇 偶分解成兩個(gè)N 4點(diǎn) 2點(diǎn) 子序列 即對將x1 r 和x2 r 分解成奇 偶兩個(gè)N 4點(diǎn) 2點(diǎn) 點(diǎn)的子序列 25 那么 X1 k 又可表示為 26 X2 k 也可以進(jìn)行相同的分解 注意 通常我們會把寫成 27 N點(diǎn)DFT的第二次時(shí)域抽取分解圖 N 8 28 8 8 29 N點(diǎn)DIT FFT運(yùn)算流圖 N 8 30 3 DIT FFT算法與直接計(jì)算DFT運(yùn)算量的比較 1 N 2M的DFT運(yùn)算可分成M級 每一級有N 2個(gè)蝶形 每個(gè)蝶形有一次復(fù)乘兩次復(fù)加 2 所以M級共有次復(fù)乘和次復(fù)加 3 若直接計(jì)算DFT 需N2次復(fù)乘和N N 1 次復(fù)加 顯然 當(dāng)N較大時(shí) 有 31 FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線 32 4 DIT FFT的運(yùn)算規(guī)律及編程思想 FFT的每級 列 計(jì)算都是由N個(gè)復(fù)數(shù)數(shù)據(jù) 輸入 兩兩構(gòu)成一個(gè)蝶型 共N 2個(gè)蝶形 運(yùn)算而得到另外N個(gè)復(fù)數(shù)數(shù)據(jù) 輸出 當(dāng)數(shù)據(jù)輸入到存儲器以后 每一組運(yùn)算的結(jié)果 仍然存放在這同一組存儲器中直到最后輸出 例 將x 0 放在單元A 0 中 將x 4 放在單元A 1 中 W80放在一個(gè)暫存器中 將x 0 W80 x 4 送回A 0 單元 將x 0 W80 x 4 送回A 1 單元 1 原位運(yùn)算 亦稱同址計(jì)算 33 回顧 N點(diǎn)DIT FFT運(yùn)算流圖 N 8 34 如上所述 N點(diǎn)DIT FFT運(yùn)算流圖中 每級都有N 2個(gè)蝶形 每個(gè)蝶形都要乘以因子WNP 稱其為旋轉(zhuǎn)因子 p稱為旋轉(zhuǎn)因子的指數(shù) 2 旋轉(zhuǎn)因子的變化規(guī)律 觀察FFT運(yùn)算流圖發(fā)現(xiàn) 第L級共有2L 1個(gè)不同的旋轉(zhuǎn)因子 N 23 8時(shí)的各級旋轉(zhuǎn)因子表示如下 L 1時(shí) WNp WN 4J N 4 21 2L J 0L 2時(shí) WNp WN 2J N 2 22 2L J 0 1L 3時(shí) WNp WNJ N 23 2L J 0 1 2 3 35 對N 2M的一般情況 第L級的旋轉(zhuǎn)因子為 36 設(shè)序列x n 經(jīng)時(shí)域抽選 倒序 后 存入數(shù)組X中 如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn) 應(yīng)用原位計(jì)算 則蝶形運(yùn)算可表示成如下形式 下標(biāo)L表示第L級運(yùn)算 XL J 則表示第L級運(yùn)算后數(shù)組元素X J 的值 37 3 編程思想及流程圖 38 4 碼位倒序 由N 8蝶形圖看出 原位計(jì)算時(shí) FFT輸出的X k 的次序正好是順序排列的 即X 0 X 7 但輸入x n 都不能按自然順序存入到存儲單元中 而是按x 0 x 4 x 2 x 6 x 1 x 5 x 3 x 7 的順序存入存儲單元 即為亂序輸入 順序輸出 這種順序看起來相當(dāng)雜亂 然而它是有規(guī)律的 即碼位倒讀規(guī)則 39 以N 8為例 看出 碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序 40 倒序規(guī)律 41 對于數(shù)N 在其二進(jìn)制最高位加1 等于加N 2 若已知某個(gè)反序號為J 為求下一個(gè)反序號 可先判J的最高位 1 若為0 則把該位變成1 即加N 2 就得到下一個(gè)反序號 2 若為1 則需判斷次高位 若次高位為0 則把最高位變0 相當(dāng)減去N 2 后 再把次高位變1 即加N 4 若次高位為1 則需判斷次次高位 分析 42 倒序排列算法的流程圖 43 第四節(jié)按頻率抽選的基2 FFT算法 在基2快速算法中 頻域抽取法FFT也是一種常用的快速算法 簡稱DIF FFT 設(shè)序列x n 長度為N 2M 首先將x n 前后對半分開 得到兩個(gè)子序列 其DFT可表示為如下形式 44 45 46 47 DIF FFT一次分解運(yùn)算流圖 N 8 48 DIF FFT二次分解運(yùn)算流圖 N 8 49 DIF FFT運(yùn)算流圖 N 8 50 時(shí)間抽取算法與頻率抽取算法的比較 1 頻率抽選法和時(shí)間抽選法總的計(jì)算量是相同的 2 頻率抽取法和時(shí)間抽取法一樣 都適用于原位運(yùn)算 即蝶形的輸入和輸出占用同一個(gè)存儲單元 3 均存在碼位倒序問題 4 頻率抽選法和時(shí)間抽選法一樣 基本運(yùn)算也是蝶形運(yùn)算 但兩者的蝶形形式略有不同 51