信號分析與處理（修訂版） 課件 吳京 【ch010】快速傅里葉變換

高等院校公共課系列精品教材第十章快速傅里葉變換高等院校公共課系列精品教材電子信息科學與工程類改進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é)點所連