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

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

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

FFT算法§4-4

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

FFT算法§4-5

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

N為復合數的FFT算法——混合基算法§4-10

線性卷積與線性相關的FFT算法§4-1

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

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

次復數乘法，次復數加法次復數乘法，次復數加法NN24

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

n

的奇偶把

x(n)

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

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

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

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

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

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

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

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

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

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

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

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

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

二進制數倒位序二進制數

倒位序

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

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

把一個N點DFT按k的奇偶分解為兩個N/2點的DFT與時間抽取法的推導過程一樣，由于N=2L，N/2仍是一個偶數，因而可以將每個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的結果X(k)。第L次實際上就是做兩點DFT，它只有加減運算。為了有統一的運算結構，仍然用一個系數為WN0的蝶形運算來表示。8點DFT4點DFT4點DFT2點DFT2點DFT2點DFT2點DFT按頻率抽取的FFT（N=8）信號流圖

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

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

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

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

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

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

DIT的系數相乘出現在加減法運算之前

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

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

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

DIT法與DIF法的基本蝶形是互為轉置的

轉置就是將流圖的所有支路方向都反向，并且交換輸入與輸出，但節點變量值不交換。由DIT與DIF的基本蝶形運算看出，如果將DIT的基本蝶形加以轉置，就得到DIF的基本蝶形;反過來,將DIF的基本蝶形加以轉置，就得到DIT的基本蝶形，因此DIT法與DIF法的基本蝶形是互為轉置的。按照轉置定理，兩個流圖的輸入-輸出特性必然相同因而對每一種按時間抽取的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作為一個子程序塊調用求共軛FFT求共軛實序列的FFT算法一、DFT的性質二、一次N點FFT計算兩個N點實序列設是彼此獨立的N點實數序列可通過一次N點FFT運算獲得具體方法：令：三、一次N點的FFT計算一個2N點的實序列設x(n)是2N點的實數序列令x1(n),x2(n)分別是x(n)的偶數序列和奇數序列令y(n)=x1(n)+jx2(n)得到N點的復數序列2NNN時間抽取蝶形結返回目錄由于x1(n),x2(n)分別是x(n)的偶數序列和奇數序列§4.6

N為復合數的FFT算法——混合基算法若序列的點數1、將補零使N增長到最臨近的一個數值2、若要求準確的N點DFT1）N為質數(素數)a.直接DFT算法b.CZT(線性調頻z變換)方法2）N為復合數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、存儲輸入數據(以行的順序)例如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、乘旋轉因子01230X1’X1’X1’X1’1X1’X1’X1’X1’2X1’X1’X1’X1’4、計算每行M點的DFT01230X2X2X2X21X2X2X2X22X2X2X2X25、讀出計算結果(以列的順序)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為復合數的FFT運算量的估計不計譯序、整序的工作量(1)個點DFT復乘復加(2)乘N個旋轉因子復乘(3)個點DFT復乘復加總計：復乘復加復乘復加時，混合基算法計算量直接計算DFT的計算量復乘復加算法節省的計算量倍數為時，混合基算法計算量復乘復加返回目錄§4.10線性卷積與線性相關的FFT算法以FIR濾波器為例，它的輸出等于有限長單位脈沖響應h(n)與有限長輸入信號x(n)的離散線性卷積

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

1)為了不產生混疊，其必要條件是使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)就代表線性卷積的結果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點當x(n)的點數很多時，即當L>>M，需要采用分段卷積或稱分段過濾的辦法計算卷積。原因：不能等x(n)全部采集后再進行卷積；否則，使輸出相對于輸入有太長的延時，需要太多的存儲空間；此外，若N=L+M-1太大，h(n)必須補很多個零值點，很不經濟，這時FFT法的優點就表現不出來了。將x(n)分成點數和h(n)相仿的段，分別求出每段的卷積結果，然后用某種方式把它們合在一起，得到總的輸出，其中每一段的卷積均采用FFT方法處理。有兩種分段卷積的辦法:重疊相加法和重疊保留法重疊相加法：

設h(n)的點數為M，信號x(n)為很長的序列。將x(n)分為很多段，每段為L點，L選擇和M的數量級相同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)個點發生重疊，即前一段的后(M-1)個點和后一段的前(M-1)個點相重疊。應該將重疊部分相加再和不重疊的部分共同組成輸出y(n)。

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

重疊相加法圖形