循環(huán)卷積_DFT求線性卷積 (1)

1、專題：專題：循環(huán)卷積、用循環(huán)卷積、用DFT求線性卷積求線性卷積首先，我們要理解周期卷積僅僅針對離散傅里葉級數(shù)，循環(huán)首先，我們要理解周期卷積僅僅針對離散傅里葉級數(shù)，循環(huán)卷積（又稱圓周卷積）僅僅針對離散傅里葉變換。這里的卷積（又稱圓周卷積）僅僅針對離散傅里葉變換。這里的“循環(huán)循環(huán)”是針對周期序列而言，我們要始終記住，離散傅里是針對周期序列而言，我們要始終記住，離散傅里葉變換的序列葉變換的序列x(n)是周期序列是周期序列 的主值序列。的主值序列。而線性卷積是針對有限長序列，要用而線性卷積是針對有限長序列，要用DFT求線性卷積，必然求線性卷積，必然要求周期序列在一個(gè)周期內(nèi)求卷積能和有限長序列求線性卷要

2、求周期序列在一個(gè)周期內(nèi)求卷積能和有限長序列求線性卷積等值。因此我們求積等值。因此我們求N點(diǎn)長度的循環(huán)卷積必然要和線性卷積點(diǎn)長度的循環(huán)卷積必然要和線性卷積長度一致。起碼長度一致。起碼N要不少于線性卷積的長度。要不少于線性卷積的長度。)(nx 有限長序列的循環(huán)卷積（又稱圓周卷積）有限長序列的循環(huán)卷積（又稱圓周卷積） (1) 定義定義n設(shè)x1(n) 和x2(n) 是兩個(gè)長度為 L、M的有限長序列，它們的N點(diǎn)循環(huán)卷積x3(n) 定義為： 注意：其中N=MaxL,M)()()()()()(1021213nRmnxmxnxnxnxNNmn注意：如果其中一個(gè)序列如果其中一個(gè)序列(或者兩個(gè)序列）的長度沒有所或

3、者兩個(gè)序列）的長度沒有所求求N點(diǎn)循環(huán)卷積的長度長，那在該序列后面補(bǔ)零，直到長點(diǎn)循環(huán)卷積的長度長，那在該序列后面補(bǔ)零，直到長度達(dá)到度達(dá)到Nn(c) 用解析式計(jì)算 n此式可用矩陣表示為：)()()()()()(10nRmnhmxnhnxnyNNmNN ) 1() 2() 2() 1 () 0 ( ) 0 () 3() 2() 1() 1() 4() 3() 2() 3 () 0 () 1 () 2() 2() 1() 0 () 1 () 1 () 2() 1() 0 () 1() 2() 2() 1 () 0 (NxNxxxxhNhNhNhNhNhNhNhhhhhhNhhhhNhNhhNyNyyy

4、yNNNNN注意矩陣的對角線為 然后每列往下依次是1、2、3.循環(huán)移位)0(hn h矩陣這個(gè)N階方陣中的元素都是n由0到N-1區(qū)間的h(n)，這是通過求模(n-m)N 而得到的。在實(shí)際運(yùn)用時(shí)只需要按照h矩陣中元素排列的規(guī)律直接寫出這個(gè)矩陣。n 例例 設(shè) x1(n) = 1,2,3,4,5，x2(n)=6,7,8,9，計(jì)算 5 點(diǎn)循環(huán)卷積 。n 解： x2(n) 為 4 點(diǎn)序列，在其尾部填零使其成為 5 點(diǎn)序列，再進(jìn)行循環(huán)卷積運(yùn)算。)()()(213nxnxnx10070859510054321 6 7 8 9 00 6 7 8 99 0 6 7 88 9 0 6 77 8 9 0 6)4()3

5、()2() 1 ()0(33333xxxxx 循環(huán)卷積與線性卷積的關(guān)系循環(huán)卷積與線性卷積的關(guān)系n我 們 已 經(jīng) 知 道 ， 可 以 用 DFT 來 求 循環(huán)卷積，即 ，因此只要找到循環(huán)卷積與線性卷積之間的關(guān)系，就可以解決用DFT求線性卷積的問題。 )()()()(kHkXIDFTnhnx用用DFTDFT求線性卷積求線性卷積nDFT不僅可以用來對信號(hào)進(jìn)行頻譜分析，而且還可以用來計(jì)算序列的線性卷積。 n設(shè)x(n) 長度為N1，h(n) 長度為N2，則線性卷積n之長為N = N1+N2-1。為了便于用矩陣表示，我們在序列x(n) 的后面添N2-1個(gè)0，使x(n) 的長度變?yōu)镹，這樣，線性卷積為： n

6、用矩陣表示為：10),()()()()(Nm1Nn0 mnhmxnhnxny)()()(nhnxny0000) 1() 1 () 0 () 0 () 1 () 2() 1(000) 0 () 2() 1(00) 0 () 1 () 2 (00) 0 () 1 () 1(0) 0 () 2() 1() 0 () 1 () 0 () 1() 2() 1()() 1() 1 () 0 (12222222222NxxxhhNhNhhNhNhhhhhhNhhNhNhhhhNyNyNyNyNyyyn 與循環(huán)卷積的矩陣表示相比較，可以看出，即使進(jìn)行線性卷積的兩個(gè)序列長度也都是N，其結(jié)果也與循環(huán)卷積不同：兩個(gè)

7、表示式中h矩陣不但元素的排列不同，而且矩陣的大小也不同。事實(shí)上，如果x(n)和h(n)的長度都為N，則它們的循環(huán)卷積yN(n)之長度為N，而它們的線性卷積y(n)之長度為2N-1。n 但是，在一定的條件下，可以使循環(huán)卷積與線性卷積的結(jié)果相同?？紤]兩個(gè)有限長序列的線性卷積：設(shè)x(n)的非零區(qū)間為0nN1-1, h(n)的非零區(qū)間為0nN2-1，則線性卷積y(n)=x(n)*h(n)的長度為N=N1+N2-1，非零區(qū)間是0nN-1。n 現(xiàn)在來設(shè)法構(gòu)造這兩個(gè)序列x(n) 與h(n) 的循環(huán)卷積，使其結(jié)果與線性卷積相同。n在x(n) 后面補(bǔ)充N2-1個(gè)0，使x(n)長度變?yōu)?N，x(n)：x(0)、x

8、(1)、x(N1-1)、0、0、0。n在h(n) 后面補(bǔ)充N1-1個(gè)0，使h(n)長度變?yōu)?N，h(n)：h(0)、h(1)、h(N2-1)、0、0、0。n再將h(n) 進(jìn)行周期延拓，周期為N： rrNnhnh)()(n為了計(jì)算x(n)與h(n)的循環(huán)卷積yN(n)，我們先計(jì) 算 與 的周期卷積 ： )(nx)(nh)(nyN rrNmrNmNmNmNrNnymrNnhmxrNmnhmxmnhmxmnhmxny)()()()()()()()()()(10101010n 此式說明，周期卷積 是x(n)與h(n)的線性卷積y(n) 的周期延拓。由于 與 的周期都為N，因此它們的周期卷積 的周期也為

9、N，正好等于y(n)的長度，即上式中以N為周期的周期延拓沒有發(fā)生混疊，線性卷積y(n)正好是周期卷積 的一個(gè)周期。 )(nyN)(nyN)(nyN)(nx)(nhn而循環(huán)卷積又是周期卷積的主值序列，因此，此時(shí)循環(huán)卷積yN(n)與線性卷積y(n)完全相同，即： 1010)()()()()()()()(NmNNNNnmnhmxnynRnynhnxnyn 例例 設(shè)兩個(gè)有限長度序列：x(n), 0n7；y(n), 0n19。令X ( k ) 和 Y ( k ) 分 別 表 示 它 們 的 2 0 點(diǎn) D F T ， 而 序 列r(n)=IDFTX(k)Y(k)。試指出r(n)中的哪些點(diǎn)相當(dāng)于線性卷積g

10、(n)=x(n)*y(n)中的點(diǎn)。n 解：設(shè)R(k)=X(k)Y(k)，于是 ，并且r(n)之長度為20。又設(shè)g(n)=x(n)*y(n)，則線性卷積g(n)之長度為8+20-1=27。循環(huán)卷積r(n)是周期卷積 的主值序列，而 又是線性卷積g(n)的周期延拓，延拓的周期就是周期卷積的周期20。 )()()(nynxnr)(nr)(nrn由于2027，即延拓的周期小于線性卷積的長度，故延拓時(shí)必然發(fā)生線性卷積的混疊，即 的每一個(gè)周期的前27-20=7個(gè)值都是g(n)的前一個(gè)周期的后7個(gè)值與后一個(gè)周期的前7個(gè)值的混疊，也就是說，循環(huán)卷積r(n) 的20個(gè)值中，后13個(gè)值才與g(n)中間部分的13個(gè)值相同。因此，對于循環(huán)卷積r(n)，（0n19），只有7n19這13個(gè)點(diǎn)相