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

3.3

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

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

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

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

圖中，紅色為原信號(hào)，藍(lán)色為恢復(fù)信號(hào)。

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

圖中，紅色為原信號(hào)，藍(lán)色為恢復(fù)信號(hào)。

思考：當(dāng)N=5，M=8時(shí)，恢復(fù)出的信號(hào)是什么樣？14華中科技大學(xué)電信系15華中科技大學(xué)電信系

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

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

其中就是內(nèi)插函數(shù)?！嚅L(zhǎng)度為N的序列x(n)的傅里葉變換X(ejw)可通過(guò)Z平面單位圓上的N個(gè)取樣值，即N個(gè)頻域取樣值X(k)來(lái)恢復(fù)。25華中科技大學(xué)電信系一些說(shuō)明在每個(gè)抽樣點(diǎn)上X(ejw)就精確地等于X(k)（因?yàn)槠渌膬?nèi)插函數(shù)在這一點(diǎn)上的值為零，無(wú)影響），即各抽樣點(diǎn)之間的X(ejw)

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

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

35華中科技大學(xué)電信系

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

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

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

蝶形、同址和變址計(jì)算53華中科技大學(xué)電信系∵完成一個(gè)蝶形運(yùn)算需2次復(fù)加法和1次復(fù)乘法?！嗤瓿蒒=2M點(diǎn)的DFT計(jì)算需log2N級(jí)迭代計(jì)算，每級(jí)N/2個(gè)蝶形； ∴

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

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

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

圖3.2