ch循環(huán)卷積ppt課件(編輯修改稿)
2025-02-02 13:34 本頁面
【文章內(nèi)容簡介】 其 他 的 內(nèi) 插 函 數(shù) 在 這 一 點 上 的 值 為 零，無 影 響）， 即 ?各 抽 樣 點 之 間 的 X(ej?) 值 , 則 由 各 抽 樣 點 的 加 權(quán) 內(nèi) 插 函 數(shù) 在 所 求 點 上 的 值 的 疊 加 而 得到 . ?頻 率 響 應(yīng) 的 內(nèi) 插 函 數(shù) ? (?) 具 有 線 性 相 位 . 2) ( ) , 0 , 1 , . . . 1jkNX e X k k N? ?? ?? ? ?（華中科技大學電信系 27 華中科技大學電信系 28 本節(jié)結(jié)論： 長度為 N的序列 x(n)， 其 N個頻域取樣值 X(k)可以不失真地代表它 ， 而且 X(k)還能完整的表示序列的 Z變換 X(z)和傅里葉變換 X(ej?) 。 頻率取樣理論是用頻率取樣法設(shè)計 FIR數(shù)字濾波器 （ DF） 的理論基礎(chǔ) 。 華中科技大學電信系 29 3. 5 快速傅里葉變換 (FFT) DFT的計算量 ??????????????????????10,)(1)(10,)()(1010NnWkXNnxNkWnxkXNkknNNnknN?1965年庫利 (Cooley)和圖基 (Tukey)在前人的研究成果的基礎(chǔ)上提出了 FFT的算法 。 FFT的出現(xiàn) ， 使計算 DFT的計算量減少了兩個數(shù)量級 ， 極大地推動了 DSP的理論和技術(shù)的發(fā)展 。 當 N很大時 ， 計算量太大 ， 所花的時間也太多 。 ?如果使用 來直接計算 DFT， ?離散傅里葉變換在實際應(yīng)用中是非常重要的 ， 利用它可以計算信號的頻譜 、 功率譜和線性卷積等 。 華中科技大學電信系 30 Cooley and Tukey, 1965 J. W. Cooley and J. W. Tukey, Mathematics of Computation, Vol. 19, pp. 297301, 1965. 華中科技大學電信系 31 DFT的定義： 在導(dǎo)出 FFT算法之前，首先來估計一下直接計算 DFT所需的計算量。 其中 2 22c os sinj NNW e jNN? ???? ? ?華中科技大學電信系 32 將 DFT定義式展開成方程組 將方程組寫成矩陣形式 用向量表示 華中科技大學電信系 33 用復(fù)數(shù)表示： 其中： X為 N維列向量 ， 稱為變換列向量 ， 為復(fù)數(shù)；W為 N N維方陣 ， 稱為系數(shù)矩陣 ， 為復(fù)數(shù)； x為 N維列向量 ， 表示離散時間信號 ， 可以是復(fù)數(shù) 。 {R e [ ] R e [ ] I m [ ] I m [ ] }X W x W x W x? ? ? ? ? ?{R e [ ] I m [ ] R e [ ] I m [ ] }j W x x W+ ? + ?華中科技大學電信系 34 若計算一個 X(k)(一個頻率成分 )的值， 例 k=1則 要進行 N次復(fù)數(shù)乘法 +(N1)次復(fù)數(shù)加法 ????10)()1(NnnNWnxX所以直接計算 N點 DFT， 計算量為： 復(fù)數(shù)乘法次數(shù)： N2次，復(fù)數(shù)加法次數(shù)： N(N1)次 其運算量 相當于： 實數(shù)乘法次數(shù)： 4N2次，實數(shù)加法次數(shù)： 2N2＋ 2N(N1)次 華中科技大學電信系 35 ?FFT算法的改進主要利用了 WNk的兩個性質(zhì)： (1)對稱性 ， 即 (2)周期性 ， 即 ， r為任意整數(shù)。 ?從 看，提高 DFT 10( ) ( ) , ( 0 1 )NnkNnX k x n W k N??? ? ? ??運算速度 ， 唯一可以利用的是 旋轉(zhuǎn)因子 WNk ( ) *k k N kN N NW W W????k r N kNNWW+ ?華中科技大學電信系 36 FFT算法是利用旋轉(zhuǎn)因子的周期性和對稱性，并利用把長序列的 DFT逐次分解為較短序列的 DFT來提高計算速度的。 ?因為 DFT的運算量與 N2成正比的 ?如果一個大點數(shù) N的 DFT能分解為若干小點數(shù)DFT的組合 ， 則顯然可以達到減少運算工作量的效果 。 華中科技大學電信系 37 在本章中我們集中討論兩類基本的 FFT算法 。 第一類：稱為 按時間抽取 (DecimationinTime)的基 2FFT算法 ， 在這類算法中是將時間序列 x(n) 逐次分解 為較短的子序列 。 第二 類： 稱 為 按 頻 率抽 取 ( DecimationinFrequency)的基 2FFT算法 ， 在這類算法中是將離散傅里葉變換系數(shù)序列 X(k)逐次分解 為較短的子序列 。 這兩種算法特別適用于 N等于 2的冪的情況 。 華中科技大學電信系 38 ?DecimationInTime FFT，簡稱時間抽選 FFT算法 ?基本出發(fā)點： 利用旋轉(zhuǎn)因子 WNk的對稱性和周期性，將一個大的 DFT分解成一些逐次變小的 DFT來計算，分解直至 2點的變換。 ?分解過程遵循兩條規(guī)則： ①對時間序列進行偶奇分解； ②對頻率序列進行前后分解。 設(shè) N=2M， M為正整數(shù)。為了推導(dǎo)方便，取 N=23=8，即離散時間信號為 3. 5. 2 時間抽選基 2FFT算法 (庫里 — 圖基算法 ) 華中科技大學電信系 39 按照規(guī)則 (1)，將序列 x(n)分為奇偶兩組，一組序號為偶數(shù)，另
教學課件相關(guān)推薦
鄂ICP備17016276號-1