數(shù)字信號(hào)處理第四章-快速傅里葉變換

1FFT:FastFourierTransform1965年，JamesW.Cooley和JohnW.Tukey在《計(jì)算數(shù)學(xué)》（《MathematicsofComputation》）上發(fā)表了“一種用機(jī)器計(jì)算復(fù)序列傅立葉級(jí)數(shù)的算法（AnalgorithmforthemachinecalculationofcomplexFourierseries）”論文。自此之后，新的算法不斷涌現(xiàn)。一種是對(duì)N等于2的整數(shù)次冪的算法，如基2算法，基4算法。另一種是N不等于2的整數(shù)次冪的算法，例如Winagrad算法，素因子算法。4.1FFT：引言Dr.JamesW.CooleyWorkedatIBMWatsonResearchCenterinYorktownHeights,N.Y..AfterhisretirementfromIBMin1991,hejoinedtheElectricalEngineeringDepartmentattheUniversityofRhodeIsland.24.2FFT：直接計(jì)算DFT的問題及改進(jìn)N點(diǎn)有限長(zhǎng)序列x(n)的DFT變換對(duì)的定義為：

其中假設(shè)x(n)是復(fù)序列，同時(shí)X(k)一般也是復(fù)數(shù)。3復(fù)數(shù)乘法復(fù)數(shù)加法每一個(gè)X(k)NN–1N個(gè)X(k)(N點(diǎn)DFT)N2N(N–1)實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2每一個(gè)X(k)4N2N+2(N–1)=2(2N–1)N個(gè)X(k)(N點(diǎn)DFT)4N22N(2N–1)4.2FFT：直接計(jì)算DFT的問題及改進(jìn)復(fù)乘的加法次數(shù)復(fù)加的加法次數(shù)4如N=512、1024和8192時(shí)，DFT的乘法運(yùn)算

N2=5122=218=262144（26萬次）

N2=10242=220=1048576（105萬次）

N2=81922=226=67108864（6千7百萬次）對(duì)于大N，在實(shí)際中是不能接受的，無法“實(shí)時(shí)”應(yīng)用DFT。一般地，在計(jì)算機(jī)中，一次加法比一次乘法所需時(shí)間要短;在DSP中，由于乘法用特殊的硬件電路專門完成，因此乘法和加法所需機(jī)器周期相同。Cooley與Turkey提出的FFT算法，大大減少了計(jì)算次數(shù)。如N=512時(shí)，F(xiàn)FT的乘法次數(shù)約為2000次，提高了約128倍，而且簡(jiǎn)化隨N的增加而巨增，因而，用數(shù)值方法計(jì)算頻譜得到實(shí)際應(yīng)用。4.2FFT：直接計(jì)算DFT的問題及改進(jìn)5FFT：WNkn

的性質(zhì)x(0)x(2)x(1)x(3)-1-1-1-1W41X(0)X(1)X(2)X(3)6以4點(diǎn)DFT為例：直接計(jì)算需要：42=16

次復(fù)數(shù)乘。而按周期性及對(duì)稱性，可以將DFT表示為：只需要

1

次復(fù)數(shù)乘FFT：WNkn

的性質(zhì)7FFT算法分類:時(shí)間抽選法DIT:Decimation-In-Time頻率抽選法DIF:Decimation-In-FrequencyFFT：基本思想基本思路：雖然存在不同的FFT方法，但其核心思想大致相同，即通過迭代，反復(fù)利用低點(diǎn)數(shù)的DFT完成高點(diǎn)數(shù)的DFT計(jì)算，以此達(dá)到降低運(yùn)算量的目的。迭代：利用WNkn

的周期性、特殊點(diǎn)和對(duì)稱性，合并DFT計(jì)算中很多重復(fù)的計(jì)算，達(dá)到降低運(yùn)算量的目的。低點(diǎn)數(shù)：將傅氏變換DFT分解成相繼小的DFT計(jì)算，即N變小，而計(jì)算量與N2

成正比。8算法原理設(shè)序列點(diǎn)數(shù)N=2M，M為整數(shù)。若不滿足，則補(bǔ)零。

將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。即一組由偶數(shù)序號(hào)組成，另一組由奇數(shù)序號(hào)組成。4.3FFT：基2時(shí)間抽選法注意其長(zhǎng)度為N/2910偶數(shù)取樣點(diǎn)DFT為：

奇數(shù)取樣點(diǎn)DFT為：

①k的整個(gè)范圍為0～(N-1)，而X1(k)、X2(k)是由N/2個(gè)樣點(diǎn)形成的DFT，x(2r)和x(2r＋1）的長(zhǎng)度為N/2；②由這兩個(gè)偶數(shù)和奇數(shù)N/2個(gè)時(shí)域樣值可以計(jì)算出前N/2個(gè)DFT系數(shù)，也可以計(jì)算出后N/2個(gè)DFT系數(shù)。③問題：這前后N/2個(gè)DFT有無關(guān)系？k取N/2～(N-1)時(shí)，X1(k)、X2(k)、WN

情況如何？11觀察則12因此：整個(gè)X(k)的計(jì)算，可以分解為前、后半部分的運(yùn)算。而只要求出前一半，就可以由上式求出整個(gè)序列。同理而因此13上式表示為信號(hào)流程圖：此信號(hào)流程圖也稱為蝶形流程圖偶數(shù)點(diǎn)的DFT奇數(shù)點(diǎn)的DFT14以N=8為例，其信號(hào)流程圖：偶數(shù)序列奇數(shù)序列15N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/416同理17以N=8為例，其信號(hào)流程圖為N/2點(diǎn)DFTN/2點(diǎn)DFT18由于N=2M，這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,119每一次分解都是按時(shí)間域輸入序列的奇偶性次序，分解為兩個(gè)半長(zhǎng)的子序列，所以稱為按時(shí)間抽取法。仍以N=8為例：注：復(fù)數(shù)乘法5次，原來64次；復(fù)數(shù)加法為24次，原來56次。m=0級(jí)m=1級(jí)m=2級(jí)20

2m

點(diǎn)DFT的基2時(shí)間抽選計(jì)算過程可見：為什么引入FFT？出發(fā)點(diǎn)：考慮W因子的特點(diǎn)和性質(zhì)，簡(jiǎn)化算法。DIT-FFT算法：時(shí)間域輸入信號(hào)逐級(jí)分解為奇偶序列。上式中位序調(diào)整第0級(jí)蝶形復(fù)合第1級(jí)蝶形復(fù)合第m-1級(jí)蝶形復(fù)合x(n)……X(k)21例

使用基2時(shí)間抽選法FFT流圖，計(jì)算下列數(shù)據(jù)的8點(diǎn)DFT：x=[4,-3,2,0,-1,-2,3,1]4-320-1-23142-13-30-214-123-3-201355-1-5-11-1355j-5-11j85+j-25-j-4-1+j-6-1-j85+j-25-j-4j√26jj√245+j+j√2-2+6j5-j+j√2125+j-j√2-2-6j5-j-j√222蝶形運(yùn)算在FFT信號(hào)流圖中每一級(jí)里節(jié)點(diǎn)都是成對(duì)存在的，計(jì)算時(shí)總是下節(jié)點(diǎn)的值乘以WNr，然后與上節(jié)點(diǎn)的值相加減，形成下一列兩個(gè)節(jié)點(diǎn)值。這種計(jì)算的基本關(guān)系是：式中p,q是上下節(jié)點(diǎn)的序號(hào)。每一級(jí)中每對(duì)節(jié)點(diǎn)稱為對(duì)偶節(jié)點(diǎn)，對(duì)偶節(jié)點(diǎn)的間距為：基2時(shí)間抽選法-蝶形運(yùn)算23同址計(jì)算（同位特性）基2時(shí)間抽選法-同址計(jì)算1)不同級(jí)數(shù)的節(jié)點(diǎn)序號(hào)不變從蝶形運(yùn)算可以看出第m列的xm(p),xm(q)經(jīng)蝶形運(yùn)算后，在第(m+1)列中的節(jié)點(diǎn)序號(hào)不變，即xm+1(p)中的p與xm+1(q)中的q仍分別是xm(p),xm(q)中的p和q值。242)蝶形運(yùn)算是自成獨(dú)立單元蝶形運(yùn)算自成獨(dú)立單元，即xm+1(p)、xm+1(q)只與xm(p)、xm(q)有關(guān)，而與其他節(jié)點(diǎn)的值無關(guān)，同時(shí)xm(p)、xm(q)也不參與另外的蝶形運(yùn)算，后面的運(yùn)算也不再用到前面的數(shù)據(jù)。因此，就可把計(jì)算結(jié)果xm+1(p),xm+1(q)放入計(jì)算前xm(p)、xm(q)的存儲(chǔ)單元中，而不用再建新的存儲(chǔ)單元—同址計(jì)算。同址計(jì)算所需存儲(chǔ)量?jī)H等于給定數(shù)據(jù)所需的存儲(chǔ)量，這可大大節(jié)省存儲(chǔ)單元?；?時(shí)間抽選法-同址計(jì)算25輸入位序重排N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT輸入序列按奇偶分組再分解再奇偶重排直到2點(diǎn)DFT。即FFT輸出自然序列輸入序列x(n)位序重排。基2時(shí)間抽選法-位序重排010011n0n1n226說明：首先把x(n)中的n表示為二進(jìn)制。假定N=8，則 x(n)→x(n2n1n0)ni=0,1FFT的時(shí)間抽選法按n的奇偶分離而形成位置重排的原理如上圖所示。由此可以看出，時(shí)間抽選法FFT的輸入位序重排，輸出分成上下兩部分，輸出結(jié)果為自然順序。實(shí)際操作輸入序列重排實(shí)際上就是完成二進(jìn)制前后位序的相互交換：基2時(shí)間抽選法-位序重排27當(dāng)N=2M時(shí)，共有M=log2N級(jí)蝶形；每級(jí)N/2個(gè)蝶形；每個(gè)蝶形有1次復(fù)數(shù)乘法，2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT/FFT

FFT：基2時(shí)間抽選法-運(yùn)算量28FFT算法上面討論的FFT算法假定N為2的整數(shù)次冪，即N=2M，是基2FFT算法。當(dāng)N=Rv時(shí)，這樣的算法叫做基RFFT算法，而當(dāng)N=R1v1R2v2R3v3時(shí)，叫做混合基算法。當(dāng)N是一個(gè)高度合數(shù)時(shí)，可得到最有效的算法。最受歡迎也最易編程的算法是基2FFT算法。對(duì)于不能分解的質(zhì)數(shù)，或者當(dāng)N不是2的整數(shù)次冪時(shí)，可以在信號(hào)的末尾補(bǔ)0，使其成為高度合數(shù)或2的整數(shù)次冪。MatlabFFT實(shí)現(xiàn)Matlab提供了內(nèi)建的X=fft(x,N)

函數(shù)來計(jì)算矢量x的DFT。fft函數(shù)是機(jī)器碼寫成的，而不是以Matlab指令寫成的，即不存在.m文件。因此，它的執(zhí)行速度很快。采用混合算法。若N為2的冪，則得到高速的基2FFT算法；若N不是2的冪，則將N分解成質(zhì)數(shù)，得到較慢的混合基FFT；若N為質(zhì)數(shù)，則fft函數(shù)采用原始DFT算法。FFT：基2時(shí)間抽選法-Matlab實(shí)現(xiàn)29DFT定義表示為矩陣形式為：FFT：基2時(shí)間抽選法-矩陣表示30令：矩陣WN

為：DFT矩陣簡(jiǎn)單地表示為：特性FFT：基2時(shí)間抽選法-矩陣表示31FFT基2時(shí)間抽選法信號(hào)流圖（N=8）-1W821×8點(diǎn)2×4點(diǎn)4×2點(diǎn)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)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-1-1-1W80W80W82W80W81W82W83C(0)C(1)D(0)D(1)E(0)E(1)F(0)F(1)A(0)A(1)A(2)A(3)B(0)B(1)B(2)B(3)m=0級(jí)m=1級(jí)m=2級(jí)位序重排FFT：基2時(shí)間抽選法-矩陣表示32FFT矩陣形式表示為：1)輸入矢量x與P8

相乘，則只是輸入的位序重排，沒有乘法操作。FFT：基2時(shí)間抽選法-矩陣表示332)第0級(jí)運(yùn)算：2點(diǎn)DFTFFT：基2時(shí)間抽選法-矩陣表示343)第1級(jí)運(yùn)算：4點(diǎn)DFTFFT：基2時(shí)間抽選法-矩陣表示354)第2級(jí)運(yùn)算：8點(diǎn)DFTFFT：基2時(shí)間抽選法-矩陣表示36FFT算法看成是DFT矩陣W8

的分解：這個(gè)因式分解對(duì)應(yīng)于快速算法，因?yàn)榫仃嘑8(8)，F(xiàn)8(4)

，F(xiàn)8(2)和P8

的大部分元素為0，是稀疏矩陣。因此上述每個(gè)矩陣的乘法運(yùn)算最多只需要8次復(fù)乘運(yùn)算，而P8只是置換操作，沒有乘法操作。不同的FFT算法對(duì)應(yīng)于將DFT矩陣WN

分解成不同的稀疏矩陣。FFT：基2時(shí)間抽選法-矩陣表示37算法原理：根據(jù)時(shí)間-頻率的對(duì)偶性時(shí)間抽選法：是把輸入x(n)按奇偶分解成兩個(gè)子序列，即N點(diǎn)x(n)序列→N/2點(diǎn)子序列，而輸出X(k)是按自然順序排列的。頻率抽選法：是把輸入x(n)按照前后對(duì)半分開，而不是奇偶數(shù)分開，而輸出X(k)逐項(xiàng)分解成偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列。DFT變換表達(dá)式為：4.4FFT：基2頻率抽選法(DIF-FFT)如果將輸入x(n)按前后等分，即將求和分成兩部分，范圍分別為：38基2頻率抽選法–算法原理39

按k的奇偶將X(k)分成兩部分：40令:則X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT，記為X1(k)和X2(k)。41x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)42FFT基2頻率抽選法信號(hào)流圖（N=8）逐級(jí)分解，直到2點(diǎn)DFT43基本蝶形運(yùn)算不同DIT:先復(fù)乘后加減，W因子在上下節(jié)點(diǎn)都有體現(xiàn)DIF:先減后復(fù)乘，W因子僅體現(xiàn)在下節(jié)點(diǎn)FFT：基2時(shí)間和頻率抽選法的異同44運(yùn)算量相同同址計(jì)算FFT：基2時(shí)間和頻率抽選法的異同DIF輸出位序重排，DIT輸入位序重排45DIT和DIF的基本蝶形互為信號(hào)流圖轉(zhuǎn)置DITDIFFFT：基2時(shí)間和頻率抽選法的異同46輸入倒位序，輸出自然序（DIT）輸入自然序，輸出倒位序（DIF）輸入輸出均自然序各級(jí)具有相同幾何形狀輸入倒位序，輸出自然序輸入自然序，輸出倒位序FFT：基2抽選法-其它形式的流圖47

FFT：基2抽選法-其它形式的流圖48FFT：基2抽選法-其它形式的流圖49FFT：基2抽選法-其它形式的流圖50FFT：基2抽選法-其它形式的流圖51FFT：基2抽選法-其它形式的流圖52DFT和IDFT的定義：4.5FFT：IDFT快速算法(IFFT)DFT和IDFT的區(qū)別：①因子W的指數(shù)相差一個(gè)負(fù)號(hào)；②相差一個(gè)因子1/N。FFT算法中的分組方式、排序方式以及蝶形運(yùn)算結(jié)構(gòu)都可用于IFFT算法的設(shè)計(jì)，而這就是可依據(jù)現(xiàn)有的FFT算法直接得出IFFT算法的原因。53FFT和IFFT基本蝶形運(yùn)算之間的關(guān)系設(shè)有序列x(n)，其DFT為X(k)，則IDFT為:

在FFT的時(shí)間抽選法中:

4.5FFT：IDFT快速算法(IFFT)對(duì)于IFFT算法，輸入是X(k)和X(k+N/2)，輸出是X1(k)和X2(k)。解上式可以得到X1(K)、X2(K)：X(k)X(k+N/2)X1(k)X2(k)-1548點(diǎn)DIT-IFFT算法-1x(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)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-10.5W8-00.5W8-20.5W8-00.5W8-10.5W8-20.5W8-3-1-10.5W8-00.5W8-20.50.50.50.50.50.50.50.50.50.50.50.5說明：1）分組過程是按時(shí)間序列x(n)的奇偶性在時(shí)域上展開的，故稱此法為時(shí)間抽選算法DIT-IFFT；2）1/N的分解，N=2m

。4.5FFT：IDFT快速算法(IFFT)558點(diǎn)DIF-IFFT算法4.5FFT：IDFT快速算法(IFFT)56用FFT程序求IFFT的方法直接法：利用DIT、DIF的FFT程序，改變參量①把X(k)作為輸入序列，而輸出序列就是x(n)；②把因子WNkn

改為WN-kn

；③輸入序列的每一個(gè)元素除以N。4.5FFT：IDFT快速算法(IFFT)57流程如下：

共軛法共軛FFT共軛乘1/N4.5FFT：IDFT快速算法(IFFT)58DFT不適用于：DFT是均勻分布在Z平面單位圓上N點(diǎn)處的頻譜，如果取樣點(diǎn)不均勻時(shí)，則很麻煩。只研究信號(hào)的某一頻段，要求對(duì)該頻段取樣密集，提高分辨率(如窄帶信號(hào)的頻譜分析）；研究非單位圓上的取樣值（如頻譜峰值探測(cè)）；需要準(zhǔn)確計(jì)算N點(diǎn)DFT，且N為大的素?cái)?shù)；當(dāng)x(n)是短時(shí)間序列時(shí)，則得到的頻率分辨率2pi/N是很低的。提高頻譜密度的辦法：用補(bǔ)零的方法增加點(diǎn)數(shù)，但DFT的點(diǎn)數(shù)又大大增加，使計(jì)算工作量增大。CZT算法：對(duì)z變換采用螺旋線取樣，chirp-z變換(線性調(diào)頻z變換，Chirpz-transform)4.9線性調(diào)頻z變換CZT及其快速算法59CZT的定義設(shè)x(n)為已知時(shí)間序列，其Z變換的形式為：式中復(fù)變量z為：這里s為拉普拉斯變量，是個(gè)實(shí)數(shù)CZT：定義60

按照上式計(jì)算Z[x(n)]必然是從z的實(shí)軸開始，為得到任意起始點(diǎn)和以螺旋線規(guī)律變化的z值，做如下假設(shè)：

其中，A、W為任意復(fù)數(shù)，θ0為A的起始角（第1個(gè)取樣點(diǎn)（k=0）），A0為A起始半徑，φ0

為在Z平面中相鄰的zk

（即zk

和zk+1

）之間的夾角，W0

為任意正數(shù)值。M為要分析的點(diǎn)數(shù)，不一定等于N。61CZT表達(dá)式1）取樣點(diǎn)沿螺旋線按角度間隔φ0分布，φ0>0時(shí)，取樣軌跡逆時(shí)針旋轉(zhuǎn)；φ0<0時(shí)，取樣軌跡逆時(shí)針旋轉(zhuǎn)。2）zk

周線是一條螺旋線：W0

表示螺旋線的伸展率；W0>1，隨著k的增加，向內(nèi)盤旋，朝向原點(diǎn)；W0<1，隨著k的增加，向外盤旋；3)若W0=1，一段圓弧，若同時(shí)A0=1，則為單位圓一部分，此時(shí)CZT[x(n)]=DFT[x(n)]（M=N）。62CZT表示為線性卷積形式：利用布魯斯坦(Bluestein)提出的等式

把在CZT[x(n)]中的Wnk

因子展開，得：CZT：快速算法計(jì)算量：直接計(jì)算M點(diǎn)的CZT，需要MN次復(fù)數(shù)乘法，M(N-1)次復(fù)數(shù)加法，需要快速算法。把上述運(yùn)算轉(zhuǎn)換為線性卷積形式，從而可以采用FFT算法，提高運(yùn)算速度。63CZT：快速算法令則式中64CZT：快速算法g(n)和h(n)的取值范圍：65CZT：快速算法h(n)x(n)g(n)X(zk)序列：可以想像為頻率隨時(shí)間（n）線性增長(zhǎng)的復(fù)指數(shù)序列，在雷達(dá)中這類信號(hào)，稱為線性調(diào)頻信號(hào)（chirpSignal)，因此，這里z變換稱為線性調(diào)頻z變換。該信號(hào)的瞬時(shí)頻率Ωi=2Ωt正比于時(shí)間t，因此，該信號(hào)的頻率隨時(shí)間線性增長(zhǎng)。類比：66取值范圍n：0～N-1，k：0～M-1因果序列g(shù)(n)的長(zhǎng)度為N，而序列h(n)的長(zhǎng)度為N+M-1，并位于區(qū)間內(nèi)-(N-1)~(M-1)，所以卷積后的序列y(n)的長(zhǎng)度為2N+M-2，且位于區(qū)間內(nèi)–(N-1)～（N＋M－2）。實(shí)際上只要得到區(qū)間0～(M-1）內(nèi)的線性卷積結(jié)果就能夠完成CZT的計(jì)算。CZT：快速算法67用循環(huán)卷積代替線性卷積且不產(chǎn)生混迭失真的條件是：循環(huán)卷積的點(diǎn)數(shù)（周期）應(yīng)大于或等于2N＋M－2，但CZT只需要前0～(M－1)值，對(duì)以后的其它值是否混迭并不關(guān)心。因此，可將循環(huán)卷積的點(diǎn)數(shù)縮減到最小為N+M-1。為了基2FFT運(yùn)算，取L>=N+M-1，L=2m

。CZT：快速算法68g(n)、h(n)序列的構(gòu)造為了進(jìn)行循環(huán)卷積，把h(n)以周期L進(jìn)行周期拓展，再取主值序列，從而得到圓周卷積的一個(gè)序列。從n=M開始補(bǔ)L－（N＋M－1）個(gè)零或任意值，補(bǔ)到n=L-N處。從n=L－N＋1到L－1，取h(n)的周期拓展序列h(L-n)。進(jìn)行循環(huán)卷積的另一個(gè)序列g(shù)(n)只需要補(bǔ)零到L即可。69h(n)的構(gòu)造：70CZT快速算法下面說明上述計(jì)算方案的具體實(shí)現(xiàn)，既然X(zk)可用線性卷積表示，我們就可以用DFT來計(jì)算線性卷積部分，只不過DFT換成FFT，從而得到CZT的快速算法。L點(diǎn)DFTH(k)h(n)構(gòu)造長(zhǎng)度M＋N-1長(zhǎng)度Ng(n)補(bǔ)零L點(diǎn)DFTG(k)G(k)H(k)L=N+M-1L點(diǎn)IDFTy(k)7172線性卷積求解小結(jié)：時(shí)域直接求解

補(bǔ)N-N1個(gè)零x(n)N點(diǎn)DFT補(bǔ)N-N2個(gè)零h(n)N點(diǎn)DFTN點(diǎn)IDFTy(n)=x(n)*h(n)z變換法DFT法4.10FFT的應(yīng)用：線性卷積求解73上面介紹的是兩個(gè)有限長(zhǎng)序列x1(n)、x2(n)的線性卷積。但有時(shí)其中某個(gè)序列會(huì)很長(zhǎng)或無限長(zhǎng)，若等長(zhǎng)序列存儲(chǔ)或輸入完后再做卷積運(yùn)算，將產(chǎn)生問題：

(1)存儲(chǔ)量過大，運(yùn)算量也太大；(2)等待輸入的時(shí)間很長(zhǎng)，引起不能忍受的延遲；(3)采用DFT/FFT快速算法的效率降低具體方法：重疊保留法、重疊相加法

解決此問題的思路：

把長(zhǎng)序列分段，每一分段分別與短序列進(jìn)行卷積——分段卷積。FFT的應(yīng)用：分段卷積74誤差分析在分析分段卷積之前，我們首先分析兩個(gè)有限長(zhǎng)度序列的循環(huán)卷積的誤差情況。設(shè)x(n)為N1

點(diǎn)序列，h(n)為N2

點(diǎn)序列，由前面分析知道，線性卷積y(n)和循環(huán)卷積yC(n)關(guān)系為：DFT的應(yīng)用：分段卷積一般地講，循環(huán)卷積是線性卷積的一種混疊形式，即是線性卷積以周期N延拓后取主值周期。但當(dāng)N≥N1+N2-1，沒有混迭產(chǎn)生，此時(shí)線性卷積y(n)和循環(huán)卷積yN(n)相等。75為了用DFT計(jì)算線性卷積，必須選擇適當(dāng)?shù)腘，但實(shí)際中卻可能做不到這一點(diǎn)，尤其是當(dāng)一個(gè)序列的長(zhǎng)度很大而存儲(chǔ)空間有限時(shí)。當(dāng)選擇比所需要的小的N值進(jìn)行循環(huán)卷積時(shí)，會(huì)引入誤差。下面我們計(jì)算此誤差的大小。首先N≥max(N1,N2)，假設(shè)此時(shí)，循環(huán)卷積yc(n)的取值范圍為而線性卷積y(n)的非零范圍為76有上式可知，誤差為：77

因?yàn)閙ax(N1,N2)≤N≤（N1＋N2－1），上面的求和式中只剩下對(duì)應(yīng)于r=±1的項(xiàng)，其它的r值超出了max(N1,N2)≤N≤（N1＋N2－1）。因此，

一般來講，如果x(n)和h(n)為因果序列，則y(n)也為因果序列，即：因此78它說明當(dāng)

時(shí)，樣本n處的誤差與線性卷積中第n+N

個(gè)樣本相等，即混疊部分的樣值。（N1+N2–1）個(gè)樣本后，線性卷積結(jié)果為零。這說明循環(huán)卷積中的頭L個(gè)樣本存在誤差（混疊），混疊長(zhǎng)度L等于線性卷積長(zhǎng)度和循環(huán)卷積長(zhǎng)度之差，而剩下的則為正確的線性卷積樣本。

0循環(huán)卷積長(zhǎng)度N(N1+N2-1)-Ny(n)線性卷積長(zhǎng)度N1+N2-1循環(huán)卷積的錯(cuò)誤樣本（混疊部分）79此結(jié)論在用分段處理法實(shí)現(xiàn)長(zhǎng)卷積時(shí)是非常有用的。錯(cuò)誤樣本數(shù)=線性卷積長(zhǎng)度–

循環(huán)卷積長(zhǎng)度N1N20假設(shè)N=N2(N1+N2-1)-N=N1-1e(n)=0e(n)=y(n+N)y(n)yC(n)h(n)x(n)N1+N2-1N1-1點(diǎn)有誤差與線性卷積相同

假設(shè)L=N1-180例設(shè)x1(n)和x2(n)是兩個(gè)四點(diǎn)序列：

x1(n)={1,2,2,1}，x2(n)={1,-1,-1,1}計(jì)算當(dāng)N=6，5，4時(shí)的循環(huán)卷積，并在每種情況下，驗(yàn)證它們的誤差。解：顯然，線性卷積為7點(diǎn)x3(n)={1,1,-1,-2,-1,1,1}

當(dāng)N=6，得到6點(diǎn)序列的循環(huán)卷積為：因此81當(dāng)N=5時(shí)，得到5點(diǎn)序列的循環(huán)卷積為當(dāng)N=4時(shí)，得到4點(diǎn)序列的循環(huán)卷積為82重疊保留法——對(duì)輸入x(n)預(yù)處理基本思路假設(shè)把序列x(n)分成多段N點(diǎn)序列，一個(gè)系統(tǒng)的脈沖響應(yīng)為M點(diǎn)序列，M<N。由上面的結(jié)論可知，輸入分段序列和脈沖響應(yīng)之間的N點(diǎn)循環(huán)卷積產(chǎn)生該段的輸出序列，其中前M-1個(gè)樣本不是正確的輸出值。若將x(n)簡(jiǎn)單地分成互不重疊的各段，則所得的輸出序列會(huì)有不正確樣本區(qū)間存在。輸入數(shù)據(jù)如何分段？結(jié)果如何處理？DFT的應(yīng)用：重疊保留法MNy

(n)h(n)x(n)M-1點(diǎn)誤差正確的點(diǎn)MNM-1點(diǎn)誤差正確的點(diǎn)83為了解決這個(gè)問題，將x(n)分為長(zhǎng)度N1

的分段，然后每段再往前多?。∕-1）個(gè)樣本，即第k段的最后M-1點(diǎn)保留下來作為第(k+1)段的前M-1點(diǎn)，各段長(zhǎng)變?yōu)椋?/p>

其中最前面的一段x0(n)，在其前面補(bǔ)上M-1個(gè)零，使其長(zhǎng)度也為N。其中任一段xk(n)與h(n)進(jìn)行N點(diǎn)卷積運(yùn)算。

循環(huán)卷積：DFT的應(yīng)用：重疊保留法相應(yīng)的周期卷積 的周期為：N=N1+M-1線性卷積：84yk(n)的長(zhǎng)度為：N1N’M-1M-1x0(n)nN重疊區(qū)域線性卷積循環(huán)卷積N1N’NM-1M-1n重疊區(qū)域線性卷積x1(n)錯(cuò)誤樣本數(shù)=線性卷積長(zhǎng)度–

循環(huán)卷積長(zhǎng)度

=[N1+2(M-1)]–[N1+(M-1)]=M-185將每一段所得到的循環(huán)卷積的前M-1個(gè)值去掉，保留后面的N1

個(gè)值，再將各段保留的N1個(gè)值前后拼接起來，就得到所要求的線性卷積y(n)。因此，循環(huán)卷積

yk’(n)的前M-1個(gè)值是線性卷積yk(n)前面的M-1個(gè)值與yk-1(n)后面M-1個(gè)值的混迭，是錯(cuò)誤的樣本。

循環(huán)卷積yk’(n)的后N1個(gè)值才與yk(n)中間的

N1個(gè)值相同。86

這種通過將與相重疊的部分舍去，即舍去循環(huán)卷積yk’(n)中前M-1項(xiàng)，保留后面的N1

個(gè)數(shù)值，來得到所求結(jié)果的方法稱為重疊保留法，有的書中又稱為重疊舍去法。8788例設(shè)x(n)=(n+1),0≤n≤9,h(n)={1,0,-1}，按N=6用重疊舍去法計(jì)算

y(n)=x(n)*h(n)解：由于M=3，必須使每一段與前一段重疊兩個(gè)樣本，x(n)為10點(diǎn)序列，需要在開頭加(M-1)=2個(gè)零。因?yàn)镹=