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

高等院校公共課系列精品教材第十章快速傅里葉變換高等院校公共課系列精品教材電子信息科學(xué)與工程類改進(jìn)DFT計(jì)算的方法0101改進(jìn)DFT計(jì)算的方法一、直接計(jì)算DFT的特點(diǎn)根據(jù)定義,長(zhǎng)度為N的有限長(zhǎng)序列x(n)的DFT為由上式看出DFT的計(jì)算中只包含乘法和加法運(yùn)算。如果x(n)為復(fù)數(shù)序列,則根據(jù)上式完成N點(diǎn)X(k)的運(yùn)算次數(shù)分析如表10.1所示。01改進(jìn)DFT計(jì)算的方法可見,一次復(fù)數(shù)乘法包括了四次實(shí)數(shù)乘法和二次實(shí)數(shù)加法；一次復(fù)數(shù)加法則需要二次實(shí)數(shù)加法。所以對(duì)某一k值,計(jì)算X(k)需要4N次實(shí)數(shù)乘法2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法。一個(gè)完整的

N點(diǎn)DFT運(yùn)算共需要4N2次實(shí)數(shù)乘法和2N(2N-1)次實(shí)數(shù)加法。當(dāng)N較大時(shí),計(jì)算DFT需要消耗大量

的時(shí)間,很難滿足系統(tǒng)的實(shí)時(shí)性要求。所以改進(jìn)DFT算法,提高運(yùn)算效率是非常必要的。一、直接計(jì)算DFT的特點(diǎn)復(fù)數(shù)運(yùn)算是由實(shí)數(shù)運(yùn)算來(lái)完成的,可以寫成01改進(jìn)DFT計(jì)算的方法二、減少運(yùn)算量的方法的特點(diǎn)，可以減少DFT的運(yùn)算次數(shù)。觀察DFT運(yùn)算可以看出,利用旋轉(zhuǎn)因子有如下特性。(1)對(duì)稱性：周期性：可約性：(4)特殊值：按時(shí)間抽取(DIT)的FFT算法0202按時(shí)間抽取(DIT)的FFT算法一、算法原理設(shè)序列長(zhǎng)度為N=2M(M為整數(shù))。如果給定長(zhǎng)度不滿足這個(gè)條件,可以通過補(bǔ)零滿足要求。這種長(zhǎng)度N為2的整數(shù)冪的FFT,稱為基2-FFT。根據(jù)其形狀又稱其為蝶形運(yùn)算單元。圖中左側(cè)X1(k)和X2(k)為輸入,右側(cè)為輸出?？梢钥闯?每個(gè)蝶形運(yùn)算單元，需要一次復(fù)數(shù)乘法及兩次復(fù)數(shù)加(減)法。完成一個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法。02按時(shí)間抽取(DIT)的FFT算法二、時(shí)間抽取FFT的運(yùn)算量由8點(diǎn)時(shí)間抽取FFT流圖可見,一個(gè)N=2M點(diǎn)序列的DFT經(jīng)過M次分解,可以分解成M級(jí)蝶

形運(yùn)算,每一級(jí)都由N/2個(gè)蝶形運(yùn)算組成。因此全部N點(diǎn)的FFT共有號(hào)N/2×M個(gè)蝶形運(yùn)算。每個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法和二次復(fù)數(shù)加法運(yùn)算。所以N點(diǎn)的FFT所需的運(yùn)算次數(shù)如下。復(fù)數(shù)乘法：復(fù)數(shù)加法：而直接計(jì)算DFT需要N2次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法。02按時(shí)間抽取(DIT)的FFT算法三、時(shí)間抽取法的運(yùn)算特點(diǎn)1.蝶形運(yùn)算一個(gè)N=2M點(diǎn)序列的DFT經(jīng)過M次分解,全部運(yùn)算都變?yōu)榈芜\(yùn)算。每個(gè)蝶形運(yùn)算單元完成下述基本遞推運(yùn)算：2.原位運(yùn)算原位運(yùn)算就是將蝶形運(yùn)算的結(jié)果仍然保存在原輸入量的存儲(chǔ)單元中。即某一列的

N個(gè)數(shù)據(jù)送到存儲(chǔ)器后,經(jīng)蝶形運(yùn)算,其結(jié)果為另一列數(shù)據(jù),它們以蝶形為單位仍存儲(chǔ)在這一組存儲(chǔ)器中，直到最后輸出,中間無(wú)需其他存儲(chǔ)器。每列的N/2個(gè)蝶形運(yùn)算全部完成后,再開始下一列的蝶形運(yùn)算。02按時(shí)間抽取(DIT)的FFT算法三、時(shí)間抽取法的運(yùn)算特點(diǎn)倒位序所謂倒位序,就是將二進(jìn)制數(shù)的最高有效位到最低有效位的位序進(jìn)行顛倒排列而得到的二進(jìn)制數(shù)。倒位序的二進(jìn)制數(shù)通常又稱倒序數(shù)。蝶形運(yùn)算兩節(jié)點(diǎn)間距離第m級(jí)蝶形運(yùn)算可寫成的確定在時(shí)域抽取法的FFT運(yùn)算流圖中,每一級(jí)都有N/2個(gè)蝶形運(yùn)算，每個(gè)蝶形運(yùn)算都要乘以旋轉(zhuǎn)因子 。每一級(jí)旋轉(zhuǎn)因子都不相同,但排列卻很有規(guī)律。按頻率抽取(DIF)的FFT算法0303按頻率抽取(DIF)的FFT算法每個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法和二次復(fù)數(shù)加法運(yùn)算。所以頻率抽取法運(yùn)算量與時(shí)間抽取法相同,都需要復(fù)數(shù)乘法 次，復(fù)數(shù)加法：NM=Nlog2N次。一、算法原理03按頻率抽取(DIF)的FFT算法二、運(yùn)算特點(diǎn)頻率抽取法的運(yùn)算特點(diǎn)與時(shí)間抽取法基本相同,都是通過蝶形運(yùn)算完成,也是原位運(yùn)算，其輸人是正常位序,輸出為倒位序。按流圖轉(zhuǎn)置定理,即將流圖的所有支路方向取反,交換輸入輸出，系數(shù)保持不變,可得到流圖的轉(zhuǎn)置形式。頻率抽取法和時(shí)間抽取法是兩種等價(jià)的FFT運(yùn)算。FFT算法流圖并不唯一,在上面兩種FFT的算法流圖的基礎(chǔ)上稍作變換,可以得到其他形式的FFT流圖。這是因?yàn)閷?duì)任何流圖只要保證各節(jié)點(diǎn)所連