ch335循環(huán)卷積課件

3.3

利用循環(huán)卷積計算線性卷積（重點）

為快速計算線性卷積，根據(jù)前面討論的DFT的循環(huán)卷積性質(zhì)，以及循環(huán)卷積和線性卷積可能存在的某種關(guān)系。因此，可以考慮利用循環(huán)卷積計算線性卷積。首先需要討論在什么條件下，循環(huán)卷積與線性卷積相等的問題。在許多實際問題中常需要計算線性卷積，例如一個FIR設(shè)x1(n)和x2(n)都是長度為N的有限長因果序列，它們的線性卷積為1它是長為2N-1的序列。2華中科技大學電信系現(xiàn)將x1(n)和x2(n)延長至L(L>N)，延長部分(從N到L-1)均填充為零值，計算x1(n)和x2(n)的L點循環(huán)卷積，得到為了下面分析方便，先將x1(n)和x2(n)以L為周期進行延拓，得到兩個周期序列和它們的周期卷積為3華中科技大學電信系那么，如何確定延拓的周期L呢？因為兩個長度為N的序列的線性卷積是一個長度為2N-1的序列，所以(1)如果L<2N-1，則x3(n)的周期延拓必有一部分非零值序列相重疊，從而產(chǎn)生混疊失真，這時L點的循環(huán)卷積不等于N點的線性卷積。(2)如果L≥2N-1，則x3(n)的周期延拓不會產(chǎn)生混疊失真，這時由此得出結(jié)論：兩個長度為N的序列的線性卷積可用長度為L的循環(huán)卷積來代替，但L必須滿足條件

L≥2N-1。這時N到L之間的值用零填充。若x1(n)和x2(n)長度分別為N和M，則L應(yīng)滿足條件:L≥M+N-1。5華中科技大學電信系例1已知序列x1(n)和x2(n)如下：(1)求x1(n)和x2(n)的25點循環(huán)卷積y1(n)(2)求x1(n)和x2(n)的34點循環(huán)卷積y2(n)解：(1)(2)6華中科技大學電信系例2：已知請問序列y1(n)中的哪些值與序列y2(n)的值相同？解：所以，當n=2,3,4,5,6時，y1(n)=y2(n)7華中科技大學電信系頻率取樣是指對序列的傅里葉變換或系統(tǒng)的頻率特性進行取樣。本節(jié)討論在什么條件下能夠用得到的頻譜取樣值無失真地恢復原信號或系統(tǒng)。設(shè)任意長序列x(n)絕對可和，其Z變換表示為如果在單位圓上對X(z)進行等角距取樣，取樣點數(shù)為M，則得根據(jù)DFT的定義，對X(k)求反變換得9華中科技大學電信系根據(jù)上面兩式可得：∵∴

結(jié)論：在z平面的單位圓上對序列的Z域進行等角距取樣，將導致時間序列的周期延拓。這一結(jié)果與對連續(xù)時間信號取樣導致頻譜周期延拓類似。現(xiàn)在我們來考察xp(n)與原序列x(n)的關(guān)系，看它如何才能代表原序列x(n)。10華中科技大學電信系對比：11華中科技大學電信系當N=5，M=5時，時域延拓恰好無混疊現(xiàn)象，此時原序列可以完全恢復，如下圖所示

圖中，紅色為原信號，藍色為恢復信號。

13華中科技大學電信系當N=5，M=4時，時域延拓存在混疊現(xiàn)象，此時原序列不能完全恢復，如下圖所示

圖中，紅色為原信號，藍色為恢復信號。

思考：當N=5，M=8時，恢復出的信號是什么樣？14華中科技大學電信系15華中科技大學電信系

x(n)－－X(z)－－X(k)－－xp(n)－－xN(n)ZTIDFTZ=WM-k主值17華中科技大學電信系例1：已知序列：若X(z)為x(n)的ZT，如果對X(z)在處采樣后得到：畫出由X(k)的IDFT所得到的序列x1(n)的略圖，說明理由。18華中科技大學電信系解：圖略。說明：IDFT前后的序列長度應(yīng)當相等。19華中科技大學電信系解：圖略21華中科技大學電信系對于有限長序列x(n)，滿足頻域采樣定理時，M點頻域采樣X(k)就足以不失真地代表序列的頻域特性。如何由頻域取樣值恢復出X(z)或X(ejω)？在M=N時，Z變換的取樣即DFT－－X(k)，利用IDFT公式可由X(k)恢復原序列x(n)。因此以下的討論中，令M=N。

因此，由這M個采樣值X(k)應(yīng)能完全地表達整個X(z)函數(shù)及頻率特性X(ejω)。即由M點X(k)可內(nèi)插恢復出X(z)或X(ejω)。22華中科技大學電信系改寫為，其中上式就是用X(z)在單位圓上的N個取樣值X(k)來表示X(z)的內(nèi)插公式，內(nèi)插函數(shù)為F(z)∵∴，23華中科技大學電信系令

其中就是內(nèi)插函數(shù)?！嚅L度為N的序列x(n)的傅里葉變換X(ejw)可通過Z平面單位圓上的N個取樣值，即N個頻域取樣值X(k)來恢復。25華中科技大學電信系一些說明在每個抽樣點上X(ejw)就精確地等于X(k)（因為其他的內(nèi)插函數(shù)在這一點上的值為零，無影響），即各抽樣點之間的X(ejw)

值,則由各抽樣點的加權(quán)內(nèi)插函數(shù)在所求點上的值的疊加而得到.頻率響應(yīng)的內(nèi)插函數(shù)j(w)

具有線性相位.26華中科技大學電信系3.5快速傅里葉變換(FFT)3.5.1DFT的計算量1965年庫利(Cooley)和圖基(Tukey)在前人的研究成果的基礎(chǔ)上提出了FFT的算法。FFT的出現(xiàn)，使計算DFT的計算量減少了兩個數(shù)量級，極大地推動了DSP的理論和技術(shù)的發(fā)展。當N很大時，計算量太大，所花的時間也太多。如果使用來直接計算DFT，離散傅里葉變換在實際應(yīng)用中是非常重要的，利用它可以計算信號的頻譜、功率譜和線性卷積等。29華中科技大學電信系CooleyandTukey,1965J.W.CooleyandJ.W.Tukey,MathematicsofComputation,Vol.19,pp.297-301,1965.30華中科技大學電信系DFT的定義：在導出FFT算法之前，首先來估計一下直接計算DFT所需的計算量。其中31華中科技大學電信系將DFT定義式展開成方程組將方程組寫成矩陣形式用向量表示32華中科技大學電信系用復數(shù)表示：其中：X為N維列向量，稱為變換列向量，為復數(shù)；W為N×N維方陣，稱為系數(shù)矩陣，為復數(shù)；x為N維列向量，表示離散時間信號，可以是復數(shù)。33華中科技大學電信系若計算一個X(k)(一個頻率成分)的值，例k=1則要進行N次復數(shù)乘法+(N-1)次復數(shù)加法所以直接計算N點DFT，計算量為：復數(shù)乘法次數(shù)：N2次，復數(shù)加法次數(shù)：N(N-1)次其運算量相當于：實數(shù)乘法次數(shù)：4N2次，實數(shù)加法次數(shù)：2N2＋2N(N-1)次34華中科技大學電信系FFT算法的改進主要利用了WNk的兩個性質(zhì)：(1)對稱性，即(2)周期性，即，r為任意整數(shù)。從看，提高DFT運算速度，唯一可以利用的是旋轉(zhuǎn)因子WNk

35華中科技大學電信系

FFT算法是利用旋轉(zhuǎn)因子的周期性和對稱性，并利用把長序列的DFT逐次分解為較短序列的DFT來提高計算速度的。因為DFT的運算量與N2成正比的如果一個大點數(shù)N的DFT能分解為若干小點數(shù)DFT的組合，則顯然可以達到減少運算工作量的效果。36華中科技大學電信系在本章中我們集中討論兩類基本的FFT算法。第一類：稱為按時間抽取(Decimation-in-Time)的基2FFT算法，在這類算法中是將時間序列x(n)逐次分解為較短的子序列。第二類：稱為按頻率抽取(Decimation-in-Frequency)的基2FFT算法，在這類算法中是將離散傅里葉變換系數(shù)序列X(k)逐次分解為較短的子序列。這兩種算法特別適用于N等于2的冪的情況。37華中科技大學電信系Decimation-In-TimeFFT，簡稱時間抽選FFT算法基本出發(fā)點：利用旋轉(zhuǎn)因子WNk的對稱性和周期性，將一個大的DFT分解成一些逐次變小的DFT來計算，分解直至2點的變換。分解過程遵循兩條規(guī)則： ①對時間序列進行偶奇分解； ②對頻率序列進行前后分解。設(shè)N=2M，M為正整數(shù)。為了推導方便，取N=23=8，即離散時間信號為3.5.2

時間抽選基2FFT算法(庫里—圖基算法)38華中科技大學電信系按照規(guī)則(1)，將序列x(n)分為奇偶兩組，一組序號為偶數(shù)，另一組序號為奇數(shù)，即分別表示為：根據(jù)DFT的定義39華中科技大學電信系因為WN2=WN/21，所以上式變?yōu)樯鲜街械腉(k)和H(k)都是N/2點的DFT。(3.64)(3.65)所以，前N/2=4個k值的DFT可表示為40華中科技大學電信系后4個k值的X(k)表示為：因為所以(3.66)按照規(guī)則(2)，將X(k)分成前后兩組，即41華中科技大學電信系上式相當于把原來N點的DFT計算分解成兩個N/2點的DFT計算。G(k)是原序列偶數(shù)項g(r)的N/2點DFT；H(k)是原序列奇數(shù)項h(r)的N/2點DFT。(3.66)(3.65)注意：42華中科技大學電信系按照式(3.65)和式(3.66)可畫出圖3.15所示的信號流程圖。43華中科技大學電信系式(3.65)和式(3.66)把原來N點DFT的計算分解成兩個N/2點DFT的計算。照此可進一步把每個N/2點DFT的計算再各分解成兩個N/4點DFT的計算。此時G(k)和H(k)分別計算如下:{x(0)，x(2)，x(4)，x(6)}{x(0)，x(4)|x(2)，x(6)}{x(1)，x(3)，x(5)，x(7)}{x(1)，x(5)|x(3)，x(7)}原信號序列被分成4個2項信號:{x(0)，x(4)|x(2)，x(6)|x(1)，x(5)|x(3)，x(7)}44華中科技大學電信系(3.67)(3.68)45華中科技大學電信系(3.69)(3.70)這樣，用式(3.67)～(3.70)4個公式就可計算圖3.15中的兩組N/2點DFT。圖3.16所示的是其中一組G(k)的計算。46華中科技大學電信系將圖3.16與圖3.15所示的信號流程圖合并，便得到圖3.17所示的信號流程圖。∵N=8，∴上圖中N/4點的DFT就是2點的DFT，不能再分解了。G(0)G(3)H(0)H(3)47華中科技大學電信系將2點DFT的信號流程圖移入圖3.17，得到圖3.19所示的8點時間抽選的完整的FFT流程圖。m=1m=2m=348華中科技大學電信系作圖要素：(1)左邊為輸入(2)右邊為輸出(3)如果在某一支路上信號需要進行相乘運算，則在該支路上標出要相乘的系數(shù)。(4)當支路上沒有系數(shù)時，則該支路的傳輸比為1。49華中科技大學電信系2點DFT2點DFT2點DFT2點DFT2點DFT2點DFT2點DFT2點DFT4點DFT4點DFT4點DFT4點DFT8點DFT8點DFT16點DFTX(k)x(n)16點FFT50華中科技大學電信系將N點DFT先分成兩個N/2點DFT，再是四個N/4點DFT…直至N/2個兩點DFT。每分一次稱為“一級”運算。因為N=2M，所以N點DFT可分成M級如圖3.19所示，依次m=1,2,…,M，共M級“級”的概念51華中科技大學電信系從圖3.19中可看出幾個特點：(1)流程圖的每一級的基本計算單元都是一個蝶形；

(2)輸入x(n)不按自然順序排列，稱為“混序”排列，而輸出X(k)按自然順序排列，稱為“正序”排列，因而要對輸入進行“變址”；(3)由于流程圖的基本運算單元為蝶形，所以可以進行“同址”或“原位”計算。52華中科技大學電信系1.蝶形運算任何一個N為2的整數(shù)冪(即N=2M)的DFT，都可以通過M次分解，最后成為2點的DFT來計算。M次分解構(gòu)成了從x(n)到X(k)的M級迭代計算，每級由N/2個蝶形組成。圖3.20表示了蝶形的一般形式表示。其輸入和輸出之間滿足下列關(guān)系：3.5.3

蝶形、同址和變址計算53華中科技大學電信系∵完成一個蝶形運算需2次復加法和1次復乘法?！嗤瓿蒒=2M點的DFT計算需log2N級迭代計算，每級N/2個蝶形； ∴

∴完成N點的時間抽選FFT的總計算量為：54華中科技大學電信系大多數(shù)情況下復數(shù)乘法所花的時間最多，因此下面僅以復數(shù)乘法的計算次數(shù)為例來與直接計算進行比較。直接計算DFT需要的復數(shù)乘法次數(shù)為aD=N2，于是有例如，當N=1024時，則：aD/

aF≈205，即直接計算DFT所需復數(shù)乘法次數(shù)約為FFT的205倍。即：DFT需205小時，F(xiàn)FT需1小時。顯然，N越大，F(xiàn)FT的速度優(yōu)勢越大。表3.2列出了不同N值所對應(yīng)的兩種計算方法的復數(shù)乘法次數(shù)和它們的比值。55華中科技大學電信系56華中科技大學電信系2．同址(原位)計算

N點FFT，包含log2N級迭代運算，每級由N/2個蝶形計算構(gòu)成。蝶形計算的優(yōu)點是可以進行所謂同址或原位計算?，F(xiàn)在來考察第一級的計算規(guī)律。設(shè)將輸入x(0)，x(4)，x(2)，x(6)，x(1)，x(5)，x(3)，x(7)分別存入計算機的存儲單元M(1),M(2),M(3),…，M(7)和M(8)中。首先，存儲單元M(5)和M(6)中的數(shù)據(jù)x(1)和x(5)進入運算器并進行蝶形運算。注意：流圖中各蝶形的輸入量或輸出量是互不相重的，任何一個蝶形的二個輸入量經(jīng)蝶形運算后，便失去了利用價值，不再需要保存。57華中科技大學電信系第1級運算:x(1)和x(5)運算后，結(jié)果送到M(5)和M(6)保存，x(3)和x(7)運算后，結(jié)果送到M(7)和M(8)保存。第2級運算:M(5)和M(7)運算后，結(jié)果送到M(5)和M(7)保存，M(6)和M(8)運算后，結(jié)果送到M(6)和M(8)保存。所以，蝶形運算后的結(jié)果便可以送到M(5)和M(6)存儲起來。直至完成最后一級運算，中間不需要其它存貯器。同址運算的好處：節(jié)省存貯單元。當N越大，好處越明顯。58華中科技大學電信系M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(8)與圖3.22比較59華中科技大學電信系可以看出，每一級的蝶形的輸入與輸出在運算前后可以存儲在同一地址(原來位置上)的存儲單元中，這種同址運算的優(yōu)點是可以節(jié)省存儲單元，從而降低對計算機存儲量的要求或降低硬件實現(xiàn)的成本。蝶形運算的特點是，首先每一個蝶形運算都需要兩個輸入數(shù)據(jù)，計算結(jié)果也是兩個數(shù)據(jù)，與其它結(jié)點的數(shù)據(jù)無關(guān)，其它蝶形運算也與這兩結(jié)點的數(shù)據(jù)無關(guān)。因此，一個蝶形運算一旦計算完畢，原輸入數(shù)據(jù)便失效了。這就意味著輸出數(shù)據(jù)可以立即使用原輸入數(shù)據(jù)結(jié)點所占用的內(nèi)存。原來的數(shù)據(jù)也就消失了。輸出、輸入數(shù)據(jù)利用同一內(nèi)存單元的這種蝶形計算稱為原位(同址)計算。60華中科技大學電信系3．變址計算從圖3.19所示的流程圖看出，輸入x(n)是“混序”排列的。所謂輸入為“混序”，并不是說輸入是雜亂無章的，實際上它是有規(guī)律的。如果輸入x(n)的序號用二進制碼來表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的“碼位倒置”，表3.3列出了這種規(guī)律。61華中科技大學電信系在實際運算中，按碼位倒置順序輸入數(shù)據(jù)x(n)，特別當N較大時，是很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲，然后通過“變址”運算將自然順序轉(zhuǎn)換成碼位倒置順序存儲。實現(xiàn)這種轉(zhuǎn)換的程序可用圖3.21來說明。62華中科技大學電信系圖中用n表示自然順序的標號，用l表示碼位倒置的標號。當l=n時，x(n)和x(l)不必互相調(diào)換。當l≠n時，必須將x(l)和x(n)互相調(diào)換，但只能調(diào)換一次，為此必須規(guī)定每當l>n時，要將x(l)和x(n)相互調(diào)換，即把原來存放x(n)的存儲單元中的數(shù)據(jù)調(diào)入存儲x(l)的存儲單元中，而把原來存儲x(l)的存儲單元中的數(shù)據(jù)調(diào)入到存儲x(n)的存儲單元中。這樣，按自然序輸入的數(shù)據(jù)x(n)經(jīng)過變址計算后變成了碼位倒置的排列順序，便可進入第1級的蝶形運算。63華中科技大學電信系時間抽選FFT算法的其他形式的流程圖：對于任何流程圖，只要保持各節(jié)點所連支路及其傳輸系數(shù)不變，則不論節(jié)點位置怎樣排列，所得到的流程圖總是等效的，因而都能得到DFT的正確結(jié)果，只是數(shù)據(jù)的提取和存儲次序不同而已。

圖3.2