快速傅里葉變換（FFT）

快速傅里葉變換（FFT）是計算DFT的一種快速有效方法。

1965年J.W.Cooley（IBM）和

J.W.Tukey（MIT）提出了基2FFT算法。

1976年IBM公司的S.Winograd博士利用中國余數(shù)定理(ChineseRemainderTheorem,CRT)推導(dǎo)了WFTA算法，使FFT的計算量進一步下降。

1、DFT運算的特點：每計算一個X(k)值，要進行N次復(fù)數(shù)相乘，和N-1次復(fù)數(shù)相加。一共有N個X(k)，故完成全部DFT運算，需要N2次復(fù)數(shù)相乘和N（N-1）次復(fù)數(shù)相加。在這些運算中，乘法比加法復(fù)雜，需要的運算時間多，尤其是復(fù)數(shù)相乘，每個復(fù)數(shù)相乘包括4個實數(shù)相乘和2個實數(shù)相加，例

首先分析有限長序列x(n)進行一次DFT運算所需的運算量。

又每個復(fù)數(shù)相加包括2個實數(shù)相加，所以，每計算一個

X(k)要進行4N次實數(shù)相乘和2N+2（N-1）=2（2N-1）次實數(shù)相加。因此，整個DFT運算需要4N2實數(shù)相乘和2N（2N-1）次實數(shù)相加。從上面的分析看到，在DFT計算中，不論是乘法和加法，運算量均與N2成正比。因此，N較大時，運算量十分可觀。例，計算N=10點的DFT，需要100次復(fù)數(shù)相乘，而N=1024點時，需要1048576（一百多萬）次復(fù)數(shù)乘法，如果要求實時處理，則要求有很高的計算速度才能完成上述計算量。反變換IDFT與DFT的運算結(jié)構(gòu)相同，只是多乘一個常數(shù)1/N，所以二者的計算量相同。FFT算法的基本思想：考察DFT與IDFT的運算發(fā)現(xiàn)，利用以下兩個特性可減少運算量：1）系數(shù)是一個周期函數(shù)，它的周期性和對稱性可用來改進運算，提高計算效率。例利用這些周期性和對稱性，使DFT運算中有些項可合并；2）利用的周期性和對稱性，把長度為N點的大點數(shù)的DFT運算依次分解為若干個小點數(shù)的DFT。因為DFT的計算量正比于N2，N小，計算量也就小。FFT算法正是基于這樣的基本思想發(fā)展起來的。它有多種形式，但基本上可分為兩類：時間抽取法和頻率抽取法。

又如因此3.3.1按時間抽取的FFT（N點DFT運算的分解）

先從一個特殊情況開始，假定N是2的整數(shù)次方，

N=2M，M：正整數(shù)

首先將序列x（n）分解為兩組，一組為偶數(shù)項，一組為奇數(shù)項，

將DFT運算也相應(yīng)分為兩組：因為故其中注意到，H(k)，G(k)有N/2個點，即k=0，1，…，N/2-1，還必須應(yīng)用系數(shù)wkN

的周期性和對稱性表示X(k)的N/2～N-1點：由得：可見，一個N點的DFT被分解為兩個N/2點的DFT，這兩個N/2點的DFT再合成為一個N點DFT.依此類推，G(k)和H(k)可以繼續(xù)分下去，這種按時間抽取算法是在輸入序列分成越來越小的子序列上執(zhí)行DFT運算，最后再合成為Ｎ點的DFT。

蝶形信號流圖將G(k)和H(k)合成X(k)運算可歸結(jié)為：Wa+bWa-bW-W-1a+bWa-bWWabab蝶形運算的簡化(a)(b)

圖(a)為實現(xiàn)這一運算的一般方法，它需要兩次乘法、兩次加減法?？紤]到-bW和bW兩個乘法僅相差一負(fù)號，可將圖(a)簡化成圖(b)，此時僅需一次乘法、兩次加減法。圖(b)的運算結(jié)構(gòu)像一蝴蝶通常稱作蝶形運算結(jié)構(gòu)簡稱蝶形結(jié)，采用這種表示法，就可以將以上所討論的分解過程用流圖表示。N=23=8的例子。

N/2點DFTG(0)G(1)G(2)G(3)X(0)X(1)X(2)X(3)x(0)x(2)x(4)x(6)N/2點DFTH(0)H(1)H(2)H(3)X(4)X(5)X(6)X(7)x(1)x(3)x(5)x(7)WN1WN2WN3-1-1-1-1兩個4點DFT組成8點DFT按照這個辦法，繼續(xù)把N/2用２除，由于N=2M，仍然是偶數(shù)，可以被２整除，因此可以對兩個N/2點的DFT再分別作進一步的分解。即對{G(k)}和{H(k)}的計算，又可以分別通過計算兩個長度為N/4=2點的DFT，進一步節(jié)省計算量，見圖。這樣，一個８點的DFT就可以分解為四個２點的DFT。N/4點N/4點N/4點N/4點

由四個2點DFT組成8點DFT最后剩下的是2點DFT，它可以用一個蝶形結(jié)表示：這樣，一個8點的完整的按時間抽取運算的流圖由于這種方法每一步分解都是按輸入時間序列是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱為“按時間抽取法”或“時間抽取法”。按時間抽取的8點FFT時間抽取法FFT的運算特點：（1）蝶形運算（2）原位計算（3）蝶形類型隨迭代次數(shù)成倍增加（4）序數(shù)重排

（1）蝶形運算對于N=2M，總是可以通過M次分解最后成為2點的DFT運算。這樣構(gòu)成從x(n)到X(k)的M級運算過程。從上面的流圖可看到，每一級運算都由N/2個蝶形運算構(gòu)成。因此每一級運算都需要N/2次復(fù)乘和N次復(fù)加，這樣，經(jīng)過時間抽取后M級運算總共需要的運算：復(fù)乘復(fù)加

而直接運算時則與N2成正比。例N=2048，N2=4194304，(N/2)log2N=11264，N2/[(N/2)log2N]=392.4。FFT顯然要比直接法快得多。算法的計算復(fù)雜度復(fù)乘次數(shù)復(fù)乘次數(shù)NN2（2）原位計算當(dāng)數(shù)據(jù)輸入到存儲器中以后，每一級運算的結(jié)果仍然儲存在同一組存儲器中，直到最后輸出，中間無需其它存儲器，這叫原位計算。每一級運算均可在原位進行，這種原位運算結(jié)構(gòu)可節(jié)省存儲單元，降低設(shè)備成本，還可節(jié)省尋址的時間。（3）蝶形類型隨迭代次數(shù)成倍增加觀察8點FFT的三次迭代運算:第一級迭代，有一種類型的蝶形運算系數(shù)W08，兩個數(shù)據(jù)點間隔為1第二級迭代，有二種類型的蝶形運算系數(shù)W08、W28，參加運算的兩個數(shù)據(jù)點間隔為2。第三級迭代，有四類蝶形運算系數(shù)W08、W18、W28、W38，參加運算的兩個數(shù)據(jù)點間隔為4。結(jié)論：每迭代一次，蝶形類型增加一倍，數(shù)據(jù)點間隔也增大一倍。每一級的取數(shù)間隔和蝶形類型種類均為2i-1，i=1,2,…M。（4）序數(shù)重排對按時間抽取FFT的原位運算結(jié)構(gòu)，當(dāng)運算完畢時，正好順序存放著X(0)，X(1)，X(2)，…，X(7)，因此可直接按順序輸出，但這種原位運算的輸入x(n)卻不能按這種自然順序存入存儲單元中，而是按x(0)，x(4)，x(2)，x(6)，…，x(7)的順序存入存儲單元，這種順序看起來相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進制表示這個順序時，它正好是“碼位倒置”的順序。例如，原來的自然順序應(yīng)是x(1)的地方，現(xiàn)在放著x(4)，用二進制碼表示這一規(guī)律時，則是在

x(001)處放著x(100)，

x(011)處放著x(110)。

表碼位倒置順序自然順序二進碼表示碼位倒置碼位倒置順序0000000010011004201001023011110641000011510110156110010371111117

在實際運算中，一般直接將輸入數(shù)據(jù)x(n)按碼位倒置的順序排好輸入很不方便，總是先按自然順序輸入存儲單元，然后再通過變址運算將自然順序的存儲轉(zhuǎn)換成碼位倒置順序的存儲，然后進行FFT的原位計算。目前有許多通用DSP芯片支持這種碼位倒置的尋址功能。第一次分偶、奇，根據(jù)最低位n0的0、1狀態(tài)來分，若n0=0，則為偶序列；n0=1則為奇序列，得到兩組序列：

000010100110

001011101111第二次對這兩個偶、奇序列再分一次偶、奇序列，這就要根據(jù)n1的０、１狀態(tài)。若n1=0，則為偶序列；n1=1則為奇序列，得到四組序列：

000100

010110

001101

011111同理，再根據(jù)n2的０、１狀態(tài)來分偶、奇序列，直到不能再分偶、奇時為止。對于N=8,n2已是最高位，最后一次分得結(jié)果為000

100

010

110

001

101

011

1113.3.2按頻率抽取的FFT

（按輸出X(k)在頻域的順序上屬于偶數(shù)還是奇數(shù)分解為兩組）

對于N=2M情況下的另外一種普遍使用的FFT結(jié)構(gòu)是頻率抽取法。對于頻率抽取法，輸入序列不是按偶奇數(shù)，而是按前后對半分開，這樣便將N點DFT寫成前后兩部分：把X（k）進一步分解為偶數(shù)組和奇數(shù)組：令a(n)=x(n)+x(n+N/2)

b(n)=[x(n)-x(n+N/2]wnN這兩個序列都是N/2點的序列，將其代入上兩式，得x

(n)+x

(n+N/2)WNnx

(n)x

(n+N/2)[x

(n)-x

(n+N/2)]WNn-1這正是兩個N/2點的DFT運算，即將一個N點的DFT分解為兩個N/2點的DFT，上式的運算關(guān)系可用下圖表示.

以N=8的頻率抽取為例x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1N/2點DFTa(0)a(1)a(2)a(3)N/2點DFTb(0)b(1)b(2)b(3)WN1WN2WN3X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)按頻率抽取將8點DFT分解成兩個4點DFT按頻率抽取將8點DFT分解成四個2點DFT與時間抽取法一樣，由于N=2M，N/2仍是一個偶數(shù),這樣，一個N=2M點的DFT通過M次分解后，最后只剩下全部是2點的DFT，2點DFT實際上只有加減運算。但為了比較，也為了統(tǒng)一運算的結(jié)構(gòu)，仍用一個系數(shù)為W0N

的蝶形運算來表示。頻率抽取法的流圖是時域抽取法流圖的左右翻轉(zhuǎn)。下圖是N=8的頻率抽取法FFT流圖。

N=8的按頻率抽取FFT運算流圖按時間抽取的8點FFTN=8的按頻率抽取FFT運算流圖頻率抽取法FFT的運算特點：（1）蝶形運算對于任何一個2的整數(shù)冪N=2M，總是可以通過M次分解最后完全成為2點的DFT運算。這樣的M次分解，就構(gòu)成從x(n)到X(k)的M級運算過程。將頻率抽取法的流圖反轉(zhuǎn)，并將輸入變輸出，輸出變輸入，得到的便是時間抽取法流圖（反映了時域，頻域的對稱法）。頻率抽取法也共有M級運算（N=2M），其運算量與時間抽取法相同。（2）原位計算類似于時間抽取法，當(dāng)數(shù)據(jù)輸入到存儲器中以后，每一級運算的結(jié)果仍然儲存在同一組存儲器中，直到最后輸出，中間無需其它存儲器，所以頻域抽取法也可進行原位計算。（3）蝶形類型隨迭代次數(shù)成倍減少(與時間抽取法相反)

第一級迭代中有N/2種蝶形運算系數(shù)，參加蝶形運算的兩個數(shù)據(jù)相隔N/2，隨后每次迭代，蝶形類形比前一級減少一倍，間距也減少一倍，最后一級迭代，蝶形類形只有一種W0N，數(shù)據(jù)間隔為1。由這幾點規(guī)律可以看出，頻率抽取法與時間抽到法是兩種等價的FFT運算。（4）序數(shù)重排它的輸入正好是自然順序。但它的輸出卻是碼位倒置的順序。因此運算完畢后，要通過變址運算將碼位倒置的順序轉(zhuǎn)換為自然順序，然后輸出，變址方法同時間抽取法。3.3.3N為組合數(shù)的FFT（任意基數(shù)的FFT算法）

以上討論的都是以2為基數(shù)的FFT算法，即N=2M，這種情況實際上使用得最多。優(yōu)點：程序簡單，效率高，使用方便。實際應(yīng)用時，有限長序列的長度N很大程度上由人為因素確定，因此多數(shù)場合可取N=2M，從而直接使用以2為基數(shù)的FFT算法。如N不能人為確定,N的數(shù)值也不是以2為基數(shù)的整數(shù)次方,處理方法有兩種:①補零:將x(n)補零,使N=2M.

例如N=30,補上x(30)=x(31)=0兩點,使N=32=25,這樣可直接采用以2為基數(shù)M=5的FFT程序。有限長度序列補零后并不影響其頻譜X(ej

)，只是頻譜的采樣點數(shù)增加了,上例中由30點增加到32點，所以在許多場合這種處理是可接受的。②如要求準(zhǔn)確的N點DFT值，可采用任意數(shù)為基數(shù)的FFT算法,其計算效率低于以2為基數(shù)FFT算法。如N為復(fù)合數(shù)，可分解為兩個整數(shù)p與q的乘積，像前面以2為基數(shù)時一樣，F(xiàn)FT的基本思想是將DFT的運算盡量分小，因此，在N=pq情況下，也希望將N點的DFT分解為p個q點DFT或q個p點DFT，以減少計算量。步驟：分別為0,1,…，Q-1;

分別為0,1,…，P-1。

N點DFT可以重新寫成為考慮到

再令令以P=3，Q=4,N=12為例

(1)先將x(n)通過x(n1Q+n0)改寫成x(n1,n0)。因為

Q=4,n1=0,1,2,n0=0,1,2,3,故輸入是按自然順序的，即x(0,0)=x(0)x(0,1)=x(1)x(0,2)=x(2)x(0,3)=x(3)x(1,0)=x(4)x(1,1)=x(5)x(1,2)=x(6)x(1,3)=x(7)x(2,0)=x(8)x(2,1)=x(9)x(2,2)=x(10)x(2,3)=x(11)(2)求Ｑ個Ｐ點的DFT

（３）X1(k0,n0)乘以W得到X1′(k0,n0)。（４）求P個Ｑ點的DFT，參變量是k0（５）將X2(k0,k1)通過X(k0+k1P)恢復(fù)為X(k)N=12為組合數(shù)時的FFT（１）求Ｑ個P點DFT需要ＱP2次復(fù)數(shù)乘法和Ｑ·P·(P-1)次復(fù)數(shù)加法；（２）乘Ｎ個W因子需要Ｎ次復(fù)數(shù)乘法；（３）求P個Ｑ點DFT需要PQ2

次復(fù)數(shù)乘法和P·Ｑ（Ｑ-1)次復(fù)數(shù)加法。

總的復(fù)數(shù)乘法量:QP2+N+PQ2=N(P+Q+1)；總的復(fù)數(shù)加法量:Q·P(P-1)+P·Q·(Q-1)=N(P+Q-2)例:N=23*29=667,N2=444889,N(P+Q+1)=35351

上述分解原則可推廣至任意基數(shù)的更加復(fù)雜的情況。例如,如果N可分解為m個質(zhì)數(shù)因子p1,p2,…，pm，即

N=p1p2p3…pm其中，當(dāng)N=P1P2…Pm時，共需進行m次遞推變換運算。它們分別是P1、P2、…和Pm點的離散變換，所以總的乘法運算大約為

N(P1+P2+…＋Pm)當(dāng)組合數(shù)

N=P1P2P3…Pm中所有的Pi均為4時，就是基四FFT算法,以N=43為例

第一級運算的一般形式為：3.3.4Chirp-z變換

采用FFT可以算出全部N點DFT值，即z變換X(z)在z平面單位圓上的等間隔取樣值，但要求N為復(fù)合數(shù)。問題的提出：①不需要計算整個單位圓上z變換的采樣，如對于窄帶信號，只需要對信號所在的一段頻帶進行分析，這時,希望頻譜的采樣集中在這一頻帶內(nèi)，以獲得較高的分辨率，而頻帶以外的部分可不考慮。②對其它圍線上的z變換取樣感興趣，例如語音信號處理中，需要知道z變換的極點所在頻率，如極點位置離單位圓較遠(yuǎn)，則其單位圓上的頻譜就很平滑，如果采樣不是沿單位圓而是沿一條接近這些極點的弧線進行，則在極點所在頻率上將出現(xiàn)明顯的尖峰，由此可較準(zhǔn)確地測定極點頻率。③要求能有效地計算當(dāng)N是素數(shù)時序列的DFT。

算法原理：螺旋線采樣是一種適合于這種需要的變換，且可以采用FFT來快速計算，這種變換也稱作Chirp-z變換。已知x(n)，0≤n≤N-1令zk=AW-k

，k=0，…，M-1，M：采樣點數(shù)，A、W：任意復(fù)數(shù)其中：A0表示起始取樣點的半徑長度，通常A0≤1θ0表示起始取樣點z0的相角φ0表兩相鄰點之間的等分角W0螺旋線的伸展率，W0＜1則線外伸，W0＞1則線內(nèi)縮（反時針），W0=1則表示半徑為A0的一段圓弧，若A0=1，這段圓弧則是單位圓的一部分。圖螺旋線采樣

計算z變換在采樣點zk的值

k=0,1,…,M-1顯然，按照以上公式計算出全部M點采樣值需要NM

次復(fù)乘和(N-1)M次復(fù)加，當(dāng)N及M較大時，計算量迅速增加，以上運算可轉(zhuǎn)換為卷積形式，從而可采用FFT進行，這樣可大大提高計算速度。利用zk的表示式代入

nk可以用以下表示式來替換

則定義：則

上式說明，如對信號x(n)先進行一次加權(quán)處理，加權(quán)系數(shù)為，然后通過一個單位脈沖響應(yīng)為h(n)的線性系統(tǒng)，最后，對該系統(tǒng)的前M點輸出再作一次的加權(quán)，就可得到全部M點螺旋線采樣值。

系統(tǒng)的單位脈沖響應(yīng)與頻率隨時間成線性增加的線性調(diào)頻信號相似，因此稱為Chirp-z變換。

xxx(n)g(n)X(zk)算法實現(xiàn)：由于輸入信號g(n)是有限長的，長為N，但序列是無限長的，而計算0～M-1點卷積g(k)*h(k)所需要的h(n)是取值在n=-(N-1)～M-1那一部分的值，因此，可認(rèn)為h(n)是一個有限長序列，長為L=N+M-1。所以，Chirp-z變換為兩個有限長序列的線性卷積g(k)*h(k)，可用循環(huán)卷積通過FFT來實現(xiàn)。

h(n）的主值序列可由h(n)作周期延拓后取0≤n≤L-1部分值獲得，將與g(n)作循環(huán)卷積后，其輸出的前M個值就是Chirp-z變換的M個值。這個循環(huán)卷積的過程可在頻域上通過FFT實現(xiàn)。(1)求h(n)的主值序列Chirp-z變換的計算步驟：(2)用FFT求的傅里葉變換:H(r)=FFT[],L點(3)對x(n)加權(quán)并補零(4)G(r)=FFT[g(n)],L點（5）Y(r)=G(r)·H(r)

,L點（6）y(k)=IFFT[Y(r)],L點（7）,0≤k≤M-1Chirp-z變換的計算步驟：(4)G(k)=FFT[g(n)],L點FFT（5）Y(k)=G(k)H(k)

,L點復(fù)乘（6）y(n)=IFFT[Y(k)],L點FFT（7）,0≤k≤M-1

M點復(fù)乘(2)用FFT求的傅里葉變換:H(k)=FFT[],L點(3)對x(n)加權(quán)并補零N點復(fù)乘(1)求h(n)的主值序列計算量估算：乘法數(shù)估計（1）（2）兩步可以事先計算，不必實時計算。（3）（7）兩步兩次加權(quán)共計N+M次復(fù)乘,形成Y(k)需L次復(fù)乘，一個FFT與一個IFFT需Llog2L次乘，所以總乘法數(shù)：L+N+M+Llog2L，直接計算乘法數(shù):NMN及M較大時，用FFT實現(xiàn)Chirp-Z變換，速度上有很大的改進。例如:

N=1024,

M=128直接計算:

NM=131072Chirp-Z變換(取L=2048)

:

2048+1024+128+2048X11=25728

Chirp-z變換的特點：1）輸入序列的長度N與輸出序列的長度M不需要相等；2）N及M不必是高度復(fù)合數(shù)，二者均可為素數(shù)；3）相鄰采樣點zk

之間的角間隔φ0是任意的，即頻率分辨率是任意的；4）圍線是任意的，不必是Z平面上的圓；5）起始點z0可任意選定，即可從任意頻率上開始對輸入數(shù)據(jù)進行窄帶高分辨率分析；6）若A=1,M=N,,可用Chirp-z變換計算DFT（即使N為素數(shù)）。3.4FFT應(yīng)用中的幾個問題3.4.1用FFT計算IDFT

IDFT：DFT：以上所討論的FFT算法可用于IDFT運算——簡稱為IFFT比較IDFT的定義式：IDFT與DFT的差別：

1）把DFT中的每一個系數(shù)改為，

2）再乘以常數(shù)1/N，則以上所討論的時間抽取或頻率抽取的FFT運算均可直接用于IDFT運算，當(dāng)然，蝶形中的系數(shù)應(yīng)改為。

第二種方法，完全不需要改動FFT程序，而是直接利用它作IFFT?？紤]到故

IFFT計算分三步：①將X(k)取共軛（虛部乘以-1）

②對X*(k)直接作FFT③對FFT的結(jié)果取共軛并乘以1/N，得x(n)。3.4.2實數(shù)序列的FFT

以上討論的FFT算法都是復(fù)數(shù)運算,包括序列x(n)也認(rèn)為是復(fù)數(shù)，但大多數(shù)場合，信號是實數(shù)序列，任何實數(shù)都可看成虛部為零的復(fù)數(shù)，例如，求某實信號x(n)的復(fù)譜,可認(rèn)為是將實信號加上數(shù)值為零的虛部變成復(fù)信號(x(n)+j0)，再用FFT求其離散傅里葉變換。這種作法很不經(jīng)濟，因為把實序列變成復(fù)序列，存儲器要增加一倍，且計算機運行時,即使虛部為零，也要進行涉及虛部的運算，浪費了運算量。合理的解決方法是利用復(fù)數(shù)據(jù)FFT對實數(shù)據(jù)進行有效計算，下面介紹兩種方法。

（1）用

一個N點FFT同時計算兩個N點實序列的DFT

設(shè)x

(n)、y

(n)是彼此獨立的兩個N點實序列,且

X

(k)=DFT[x

(n)]，Y

(k)=DFT[y(n)]

則X(k)、Y(k)可通過一次FFT運算同時獲得。首先將x(n)、y(n)分別當(dāng)作一復(fù)序列的實部及虛部,令

g(n)=x

(n)+jy(n)計算FFT得到G(k)利用離散傅里葉變換的共軛對稱性問題：通過g(n)的FFT運算結(jié)果G(k),由上式也可得到Y(jié)(k)的值。作一次Ｎ點復(fù)序列的FFT，再通過加、減法運算就可以將X(k)與Y(k)分離出來。顯然，這將使運算效率提高一倍。同時計算兩路信號的FFTFFT分離算法RejIm

RejIm

問題：分離算法包含哪幾種運算？

（2）

用一個N點的FFT運算獲得一個2N點實序列的DFT

設(shè)x(n)是2N點的實序列，現(xiàn)人為地將x(n)分為偶數(shù)組x1

(n)和奇數(shù)組x2

(n)

x1

(n)=x(2n)n=0,1,…,N-1

x2

(n)=x(2n+1)

n=0,1,…,N-1

問題：只有一路信號怎么辦？

為求2N點x(n)所對應(yīng)X(k)，需求出X(k)與X1

(k)、X2

(k)的關(guān)系：

而

X(k)=X1(k)+W2NkX2(k)將x1

(n)及x2

(n)組成一個復(fù)序列：y(n)=x1

(n)+jx2

(n)通過N點FFT運算可得到：

Y(k)=X1(k)+jX2(k)，N點根據(jù)前面的討論，得到

1）由x1(n)及x2(n)組成復(fù)序列，經(jīng)FFT運算求得Y(k)，2）利用共軛對稱性求出X1(k)、X2(k)，3）最后利用上式求出X(k),達到用一個N點的FFT計算一個2N點的實序列的DFT的目的。所以3.4.3線性卷積的FFT算法線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一，許多重要應(yīng)用都建立在這一理論基礎(chǔ)上，如卷積濾波等。以前曾討論了用循環(huán)卷積計算線性卷積的方法歸納如下：

將長為N2的序列x(n)延長到L,補L-N2個零，將長為N1的序列h(n)延長到L,補L-N1個零，如果L≥N1+N2-1,則循環(huán)卷積與線性卷積相等,此時,可用FFT計算線性卷積，方法如下:

a.計算X(k)=FFT[x(n)]b.求H(k)=FFT[h(n)]c.求Y(k)=H(k)X(k)k=0～L-1d.求y(n)=IFFT[Y(k)]n=0～L-1

可見，只要進行二次FFT,一次IFFT就可完成線性卷積計算。計算表明,L>32時,上述計算線性卷積的方法比直接計算線卷積有明顯的優(yōu)越性,因此,也稱上述循環(huán)卷積方法為快速卷積法。

上述結(jié)論適用于x(n)、h(n)兩序列長度比較接近或相等的情況,如果x(n)、h(n)長度相差較多,例如,h(n)為某濾波器的單位脈沖響應(yīng),長度有限,用來處理一個很長的輸入信號x(n)，或者處理一個連續(xù)不斷的信號，按上述方法,有三個問題：（1）h(n)要補許多零再進行計算,計算量有很大的浪費，或者根本不能實現(xiàn)。（2）系統(tǒng)的存儲量要求極高。（3）帶來了很大的系統(tǒng)延遲。為了克服上述三個問題，保持快速卷積法的優(yōu)越性,可將x(n)分為許多段,每段的長度與h(n)接近,處理方法有兩種：(1)

重疊相加法

——由分段卷積的各段相加構(gòu)成總的卷積輸出

則輸入序列可表為：于是輸出可分解為：

其中假定xi(n)表示x(n)序列的第i段：問題：

yi(n)如何相加？

1）先對h(n)及xi(n)補零，補到具有N點長度，N=N1+N2-1。一般選N=2M。由于yi(n)的長度為N1+N2-1，而xi(n)的長度為N2，因此相鄰兩段yi(n)序列必然有N1-1點發(fā)生重疊。2）用基2FFT計算yi(n)=xi(n)*h(n)。3）重疊部分相加構(gòu)成最后的輸出序列。計算步驟：a.

事先準(zhǔn)備好濾波器參數(shù)H(k)=DFT[h(n)]，N點b.

用N點FFT計算Xi(k)=DFT[xi(n)]c.

Yi(k)=Xi(k)H(k)d.

用N點IFFT求yi(n)=IDFT[Yi(k)]e.

將重疊部分相加(2)重疊保留法

這種方法和第一種方法稍有不同，即將上面分段序列中補零的部分不是補零，而是保留原來的輸入序列值，這時，如利用DFT實現(xiàn)h(n)和xi(n)的循環(huán)卷積，則每段卷積結(jié)果中有N1-1個點不等于線性卷積值需舍去。

重疊保留法與重疊相加法的計算量差不多，但省去了重疊相加法最后的相加運算。

y0(n)中的[N1-1,N-1]點對應(yīng)于線性卷積

x(n)*h(n)中的[0,N2-1]點y1(n)中的[N1-1,N-1]點對應(yīng)于線性卷積

x(n)*h(n)中的[N2,2N2-1]點y2(n)中的[N1-1,N-1]點對應(yīng)于線性卷積

x(n)*h(n)中的[2N2,3N2-1]點依此類推

，并將yi(n)拼接起來構(gòu)成y

(n)

3.4.4用FFT計算相關(guān)函數(shù)

相關(guān)的概念很重要，互相關(guān)運算廣泛應(yīng)用于信號分析與統(tǒng)計分析，如通過相關(guān)函數(shù)峰值的檢測測量兩個信號的時延差等。

兩個長為N的實離散時間序列x(n)與y(n)的互相關(guān)函數(shù)定義為

則可以證明，rxy(τ)的離散傅里葉變換為

Rxy(k)=X*(k)Y(k)

其中

X(k)=DFT[x(n)],

Y(k)=DFT[y(n)],

Rxy(k)=DFT[rxy(τ)]，0≤k≤N-1互相關(guān)函數(shù)定義為

x(n)及y(n)的卷積公式相比較，我們可以得到相關(guān)和卷積的時域關(guān)系：

因

得

證畢。注意：

當(dāng)x(n)=y(n)時，得到x(n)的自相關(guān)函數(shù)為：

維納——辛欽定理：自相關(guān)函數(shù)與信號功率譜互為傅立葉變換對。

上面的推導(dǎo)表明，互相關(guān)和自相關(guān)函數(shù)的計算可利用FFT實現(xiàn)。由于離散傅里葉變換隱含著周期性，所以用FFT計算離散相關(guān)函數(shù)也是對周期序列而言的。直接做N點FFT相當(dāng)于對兩個N點序列x(n)、y(n)作周期延拓，作相關(guān)后再取主值（類似循環(huán)卷積）。實際一般要求的是兩個有限長序列的線性相關(guān)，為避免混淆，需采用與循環(huán)卷積求線性卷積相類似的方法，先將序列延長補0后再用上述方法。利用FFT求兩個有限長序列的線性相關(guān)：(5)

對R（k）作IFFT，取后N-1項，得取前N項，得（1）

設(shè)x(n)和y(n)的長均為N，求線性相關(guān)；（2）為了使兩個有限長序列的線性相關(guān)可用其循環(huán)相關(guān)代替而不產(chǎn)生混淆，選擇周期L≥2N-1，且L=2m，以使用FFT，將