數(shù)字信號處理課件第四章

第四章快速傅立葉變換（FFT）§4-2

直接計算DFT的問題及改進的途徑§4-3

按時間抽取(DIT)的基-2

FFT算法§4-4

按頻率抽取(DIF)的基-2

FFT算法§4-5

離散傅立葉反變換(IDFT)的快速計算方法§4-6

N為復(fù)合數(shù)的FFT算法——混合基算法§4-10

線性卷積與線性相關(guān)的FFT算法§4-1

引言快速傅立葉變換(FFT)是DFT的一種快速算法DFT在信號處理中地位非常重要，但直接計算時計算量太大，無法實時實現(xiàn)直到1965年產(chǎn)生了DFT的快速算法后，DFT才真正得到廣泛的應(yīng)用。§4-1引言§4-2直接計算DFT的問題及改進的途徑一、直接計算DFT的問題k=0,1,…,N-1n=0,1,…,N-1二者的差別只在于WN

的指數(shù)符號不同，以及差一個常數(shù)因子1/N，所以IDFT與DFT具有相同的運算量。以后我們只討論DFT的運算量。計算1個X(k)需要:計算N個X(k)需要:1復(fù)乘=次實乘+次實加1復(fù)加=次實加直接計算N點DFT需要：復(fù)數(shù)乘法復(fù)數(shù)加法實數(shù)乘法實數(shù)加法直接計算DFT，乘法次數(shù)和加法次數(shù)都是和N2成正比的，當(dāng)N很大時，運算量是無法忍受的。

次復(fù)數(shù)乘法，次復(fù)數(shù)加法次復(fù)數(shù)乘法，次復(fù)數(shù)加法NN24

22N-1N(N-1)二、改善DFT運算效率的基本途徑利用的特性1、的共軛對稱性2、的周期性3、的可約性利用這些性質(zhì)，可以使DFT運算中有些項可以合并，可以將長序列的DFT分解為短序列的DFT?？焖俑道锶~變換算法分為兩大類：DIT和DIF一、算法原理1、基-2FFT:按

n

的奇偶把

x(n)

分解為兩個N/2點的子序列：

§4-3按時間抽取(DIT)的基-2FFT算法N為2的整數(shù)次冪的FFT2、對于N點序列x(n)

說明:1）一個N點DFT分為2個N/2點DFT

2）兩個N/2點DFT合成1個N點DFT3、

4、問題：使用只能得到的前個點后點需用旋轉(zhuǎn)因子的周期性

前半部分X(k)：后半部分X(k)：N點X(k)可以表示成前點和后點兩部分：即：5、時間抽取蝶形運算流圖符號返回DIF返回例題設(shè)按時間抽取將一個N點DFT分解為兩個N/2點DFT(N=8)

6、計算量節(jié)省一半N點DFTN/2點DFTN/2點DFT7、由于N=2L，因而N/2仍是偶數(shù)，可以進一步把每個N/2點子序列再按其奇、偶分解為兩個N/4點的子序列。

x2(r)也進行同樣的分解：

統(tǒng)一系數(shù)：9、兩點DFT8、四個N/4點的DFT及兩級蝶形運算來計算N點DFT，比只用一次分解,計算量又減少了大約一半。10、這種方法的每一步分解，都是按輸入序列在時間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個更短的子序列，所以稱為“按時間抽取法”。

N點DFTN/2點DFTN/2點DFTN/4點DFTN/4點DFTN/4點DFTN/4點DFT按時間抽取的FFT（N=8）信號流圖

二、按時間抽取的FFT算法與直接計算DFT運算量的比較需要L級蝶形運算，每級有N/2個蝶形結(jié)每個蝶形結(jié)需要1次復(fù)乘，兩次復(fù)加；每級蝶形需要N/2

次復(fù)乘，N次復(fù)加；L級蝶形共需要(N/2)L次復(fù)乘，NL次復(fù)加采用基-2FFT后，N點序列需要的運算量為：直接計算DFT，N點序列需要的運算量為：復(fù)乘：復(fù)加：例：N＝7點DFT直接計算需要多少次復(fù)加、復(fù)乘？采用基-2FFT算法需要多少次復(fù)乘、復(fù)加？

復(fù)乘：復(fù)加：三、按時間抽取的FFT算法的特點1、原位運算（同址運算）每級(每列)計算都是由N/2個蝶形運算構(gòu)成的，每一個蝶形結(jié)構(gòu)完成下述基本迭代運算：蝶形結(jié)的兩個輸出值仍然存放回蝶形的兩個輸入所在的存儲器中！每列N個數(shù)據(jù)存儲在N個存儲單元，經(jīng)蝶形運算后，產(chǎn)生的N個數(shù)據(jù)，仍存儲在這一組N個存儲單元中。這種原位運算結(jié)構(gòu)可以節(jié)省存儲單元，降低成本?；?、倒位序規(guī)律造成倒位序的原因:按時間抽取進行FFT運算倒位序的形成圖3、倒位序的實現(xiàn):通過變址運算實現(xiàn)N=8時的自然順序二進制數(shù)和相應(yīng)的倒位序二進制數(shù)自然順序

二進制數(shù)倒位序二進制數(shù)

倒位序

0123456700000101001110010111011100010001011000110101111104261537圖如果輸入序列的序號用二進制表示:(n2n1n0)，則其倒位序二進制為:(n0n1n2)，這樣原來自然順序時應(yīng)該存放x(n2n1n0)的單元，現(xiàn)在存放的是x(n0n1n2)N=8倒位序的變址處理存儲單元自然順序輸入變址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)自然順序倒位序時，變址4、蝶形運算兩節(jié)點的“距離”當(dāng)輸入為倒位序，輸出為正常順序時，第m級蝶形，每個蝶形的兩節(jié)點“距離”為2m-15、系數(shù)的確定a、系數(shù)變化規(guī)律對于N=2L，一共有L列系數(shù)，第L列系數(shù)有N/2個類型為：。由后向前每推進一列，則系數(shù)類型減半；且為上列系數(shù)中偶數(shù)序號的那一半。返回b、系數(shù)WNr的確定為了完成上式運算，還必須確定出系數(shù)ＷNr①把上式中蝶形運算兩節(jié)點中的第一個節(jié)點標(biāo)號值，即k值，表示成L位（注意N=2L）二進制數(shù)；②把此二進制數(shù)乘上2L-m，即將此L位二進制數(shù)左移L-m位（這里m是指第m級運算），把右邊空出的位置補零，此數(shù)即為所求r的二進制數(shù)。對第m級運算，蝶形運算的兩節(jié)點“距離”為2m-1按時間抽取的FFT(N=8)信號流圖

返回DIF返回對比返回轉(zhuǎn)置返回目錄§4-4按頻率抽取(DIF)的基-2FFT算法一、算法原理頻率抽取法蝶形運算單元對比DIT按頻率抽取的第一次分解N=8

把一個N點DFT按k的奇偶分解為兩個N/2點的DFT與時間抽取法的推導(dǎo)過程一樣，由于N=2L，N/2仍是一個偶數(shù)，因而可以將每個N/2點DFT的輸出再按奇、偶進行分組，這樣就把N/2點DFT進一步分解為N/4點DFT。

N/4點DFT的輸入也是先將N/2點DFT的輸入上下對半分開后通過蝶形運算而形成的.按頻率抽取的第二次分解N=8

這樣的分解可以一直進行到第L次（N=2L）。這N/2個兩點DFT的輸出就是x(n)的N點DFT的結(jié)果X(k)。第L次實際上就是做兩點DFT，它只有加減運算。為了有統(tǒng)一的運算結(jié)構(gòu)，仍然用一個系數(shù)為WN0的蝶形運算來表示。8點DFT4點DFT4點DFT2點DFT2點DFT2點DFT2點DFT按頻率抽取的FFT（N=8）信號流圖

按頻率抽取的FFT（N=8）信號流圖

返回對比返回距離返回轉(zhuǎn)置二、按頻率抽取的FFT算法的特點1、原位運算每級計算是通過(N/2)個蝶形運算完成的。每一個蝶形結(jié)構(gòu)完成下述基本迭代運算：

頻率抽取法蝶形運算單元2、蝶形運算兩節(jié)點間的距離兩節(jié)點間距離為：流圖3、的計算a、系數(shù)變化規(guī)律對于，一共有L列系數(shù)，第一列系數(shù)有N/2個類型，為：。由前向后每推進一列，則系數(shù)類型減半；且為上列系數(shù)中偶數(shù)序號的那一半。對第m級運算，一個蝶形運算的兩節(jié)點“距離”為2L-m

為了完成上兩式運算，還必須確定出系數(shù)ＷNr①把上式中蝶形運算兩節(jié)點中的第一個節(jié)點標(biāo)號值，即k值，表示成L位二進制數(shù)；b、系數(shù)的確定②把此二進制數(shù)乘上2m-1，即將此二進制數(shù)左移m-1位（注意m是第m級運算），把右邊空出的位置補零，此數(shù)即為所求r的二進制數(shù)。按頻率抽取的FFT（N=8）信號流圖

二、時間抽取算法與頻率抽取算法比較不同：1.DIT輸入倒位序,輸出順序

DIF輸入順序,輸出倒位序.2.蝶形運算不同

DIT的系數(shù)相乘出現(xiàn)在加減法運算之前

DIF的系數(shù)相乘出現(xiàn)在減法運算之后.相同:2.兩種算法均可原位運算DITDIF1.都有L列蝶形運算，每列都有N/2

個蝶形結(jié)不是根本區(qū)別順序是可以改變的真正的區(qū)別頻率抽取法(DIF)蝶形運算單元

時間抽取法(DIT)蝶形運算單元

DIT法與DIF法的基本蝶形是互為轉(zhuǎn)置的

轉(zhuǎn)置就是將流圖的所有支路方向都反向，并且交換輸入與輸出，但節(jié)點變量值不交換。由DIT與DIF的基本蝶形運算看出，如果將DIT的基本蝶形加以轉(zhuǎn)置，就得到DIF的基本蝶形;反過來,將DIF的基本蝶形加以轉(zhuǎn)置，就得到DIT的基本蝶形，因此DIT法與DIF法的基本蝶形是互為轉(zhuǎn)置的。按照轉(zhuǎn)置定理，兩個流圖的輸入-輸出特性必然相同因而對每一種按時間抽取的FFT流圖都存在一個按頻率抽取的FFT流圖。即可從DITFFT得到DIFFFT或者從DIFFFT得到DITFFT。DIF與DIT是兩種等價的FFT運算。

返回目錄作141頁24在FFT中:1.用代替2.在L列中每列分別乘一個

?因子3.以X(k)為輸入，x(n)為輸出§4.5離散傅立葉反變換的快速算法（IFFT）方法1：按頻率抽取(DIF)IFFT則：按時間抽取(DIT)FFT按頻率抽取(DIF)FFT按時間抽取(DIT)IFFT→

→

DITFFT

DIFIFFT

→DIFFFTDITIFFT

→方法2:IFFT把FFT作為一個子程序塊調(diào)用求共軛FFT求共軛實序列的FFT算法一、DFT的性質(zhì)二、一次N點FFT計算兩個N點實序列設(shè)是彼此獨立的N點實數(shù)序列可通過一次N點FFT運算獲得具體方法：令：三、一次N點的FFT計算一個2N點的實序列設(shè)x(n)是2N點的實數(shù)序列令x1(n),x2(n)分別是x(n)的偶數(shù)序列和奇數(shù)序列令y(n)=x1(n)+jx2(n)得到N點的復(fù)數(shù)序列2NNN時間抽取蝶形結(jié)返回目錄由于x1(n),x2(n)分別是x(n)的偶數(shù)序列和奇數(shù)序列§4.6

N為復(fù)合數(shù)的FFT算法——混合基算法若序列的點數(shù)1、將補零使N增長到最臨近的一個數(shù)值2、若要求準確的N點DFT1）N為質(zhì)數(shù)(素數(shù))a.直接DFT算法b.CZT(線性調(diào)頻z變換)方法2）N為復(fù)合數(shù)N=ML混合基FFT算法一、算法原理序列長度N滿足：輸入x(n)輸出X(k)可以描述為二維序列行序號列序號行序號列序號01230x(0)x(1)x(2)x(3)1x(4)x(5)x(6)x(7)2x(8)x(9)x(10)x(11)例如二、計算過程1、存儲輸入數(shù)據(jù)(以行的順序)例如01230x(0)x(1)x(2)x(3)1x(4)x(5)x(6)x(7)2x(8)x(9)x(10)x(11)2、計算每列L點的DFT01230X1X1X1X11X1X1X1X12X1X1X1X13、乘旋轉(zhuǎn)因子01230X1’X1’X1’X1’1X1’X1’X1’X1’2X1’X1’X1’X1’4、計算每行M點的DFT01230X2X2X2X21X2X2X2X22X2X2X2X25、讀出計算結(jié)果(以列的順序)01230X2X2X2X21X2X2X2X22X2X2X2X2012345678910113-pointDFT3-pointDFT3-pointDFT3-pointDFT4-pointDFT4-pointDFT4-pointDFT036914710258113-pointDFTn0=03-pointDFTn0=13-pointDFTn0=23-pointDFTn0=3048159261011374-pointDFTk0=04-pointDFTk0=14-pointDFTk0=203691471011582036914710258113-pointDFT4-pointDFT三、N為復(fù)合數(shù)的FFT運算量的估計不計譯序、整序的工作量(1)個點DFT復(fù)乘復(fù)加(2)乘N個旋轉(zhuǎn)因子復(fù)乘(3)個點DFT復(fù)乘復(fù)加總計：復(fù)乘復(fù)加復(fù)乘復(fù)加時，混合基算法計算量直接計算DFT的計算量復(fù)乘復(fù)加算法節(jié)省的計算量倍數(shù)為時，混合基算法計算量復(fù)乘復(fù)加返回目錄§4.10線性卷積與線性相關(guān)的FFT算法以FIR濾波器為例，它的輸出等于有限長單位脈沖響應(yīng)h(n)與有限長輸入信號x(n)的離散線性卷積

y(n)也是有限長序列，其點數(shù)為L+M-1點一、線性卷積的FFT算法設(shè)x(n)為L點，h(n)為M點，輸出y(n)為

1)為了不產(chǎn)生混疊，其必要條件是使x(n)，h(n)都補零值點，補到N≥M+L-1，即:0≤n≤L-1L≤n≤N-1

0≤n≤M-1M≤n≤N-12)然后計算圓周卷積FFT算法就是用圓周卷積來代替線性卷積這時，y(n)就代表線性卷積的結(jié)果N用FFT計算y(n)的步驟如下①計算H(k)=DFT［h(n)］，N點②計算X(k)=DFT［x(n)］,N點③計算Y(k)=X(k)H(k);④計算y(n)=IDFT［Y(k)］，N點當(dāng)x(n)的點數(shù)很多時，即當(dāng)L>>M，需要采用分段卷積或稱分段過濾的辦法計算卷積。原因：不能等x(n)全部采集后再進行卷積；否則，使輸出相對于輸入有太長的延時，需要太多的存儲空間；此外，若N=L+M-1太大，h(n)必須補很多個零值點，很不經(jīng)濟，這時FFT法的優(yōu)點就表現(xiàn)不出來了。將x(n)分成點數(shù)和h(n)相仿的段，分別求出每段的卷積結(jié)果，然后用某種方式把它們合在一起，得到總的輸出，其中每一段的卷積均采用FFT方法處理。有兩種分段卷積的辦法:重疊相加法和重疊保留法重疊相加法：

設(shè)h(n)的點數(shù)為M，信號x(n)為很長的序列。將x(n)分為很多段，每段為L點，L選擇和M的數(shù)量級相同iL≤n≤(i+1)L-1其他n

i=0,1,…

則輸入序列可表示成：用xi(n)表示x(n)的第i段：

每一個yi(n)=xi(n)*h(n)都可用上面討論的快速卷積方法計算。由于xi(n)為L點，而yi(n)為L+M-1點，故相鄰兩段輸出序列必然有(M-1)個點發(fā)生重疊，即前一段的后(M-1)個點和后一段的前(M-1)個點相重疊。應(yīng)該將重疊部分相加再和不重疊的部分共同組成輸出y(n)。

線性卷積的特點是：頭、尾各有(M-1)長的過渡過程因此，將x(n)分段后，其每段的卷積結(jié)果yi(n)都不能完全和相應(yīng)的y(n)相等，需要把上一段的后過渡過程和本段的前過渡過程對應(yīng)相加，才能得到完整的y(n)

重疊相加法圖形