哈工大信息論講義第7-8章

第七章卷積碼過失控制編碼系統(tǒng)中除了使用分組碼之外，另一類廣泛應(yīng)用的稱為卷積碼，在分組碼的編碼和譯碼過程中，每個碼字的監(jiān)督元只與本碼字的信息元有關(guān)，而與其它碼字的信息元無關(guān)，即分組碼的編碼器是一個無記憶的邏輯電路。但是，卷積碼的編碼過程中，本碼字的監(jiān)督元不僅與本碼字的信息元有關(guān)，而且與前m個碼字的信息元有關(guān)，因此卷積碼的編碼器是一個有記憶的時序電路。卷積碼由于更充分地利用碼字之間的相關(guān)性，可以減少碼字長度，簡化編譯碼電路，并得到較好的過失控制性能，因此卷積碼在通信領(lǐng)域，特別是衛(wèi)星通信，空間通信領(lǐng)域得到廣泛的應(yīng)用。7.1卷積碼的根本原理7.1.1卷積碼的根本概念[例子]：通過一個例子說明卷積碼的一些根本概念；圖7-1給出了一個(3,2,2)卷積碼編碼器的原理圖，圖7-1(3,2,2)卷積碼編碼器原理圖當(dāng)某一時刻，編碼器輸入并行一個信息碼字為mi=[mi(1),mi(2)]，編碼器并行輸出由三個碼元組成的卷積碼的碼字，[ci]=[ci(1),ci(2),ci(3)]=[mi(1),mi(2),pi]。[ci]稱為一個碼字。mi為信息元，pi為監(jiān)督元?？梢钥闯鼍矸e碼的輸入輸出關(guān)系為：ci(1)=mi(1)ci(2)=mi(2)ci(3)=mi(1)+mi(2)+mi-1(2)+mi-2(1)可見，卷積碼當(dāng)前輸出的碼字的監(jiān)督元不僅與當(dāng)前輸入的信息元有關(guān)而且還與前2個碼元有關(guān)。這時編碼器由2級移位存放器構(gòu)成。定義：卷積碼字中碼元的個數(shù)為n0，碼字中信息元個數(shù)為k0，由m級移位存放器構(gòu)成的編碼器稱m為編碼碼字約束長度。有的教材稱m’=m+1為約束長度，(m+1)n0為編碼碼元約束長度。卷積碼記為(n0,k0,m)。定義：R=k0/n0為碼率(Coderate)。它是表示卷積碼的編碼效率。卷積碼的編碼器的一般形式為：圖7-2卷積碼編碼器一般形式看以下卷積碼的約束關(guān)系圖：圖7-3卷積碼的約束關(guān)系在譯碼過程中，譯碼字ci時要利用到ci-1,ci-2，同時譯碼字ci+1,ci+2時還要利用到ci。因此譯碼約束長度一般要大于編碼約束長度，因為：雖然一般理解譯碼字ci時只利用ci-1,ci-2但實際上這時譯出的ci可能譯錯，當(dāng)譯ci+2時同樣是對ci的一種校驗。還可以對cI的譯碼進行修改。這是卷積碼的特別之處。如果卷積碼編碼器的輸入端輸入有頭無尾的一個半無限序列，即信息碼字序列為[m]=m0,m1,m2,…mi…，那么編碼器的輸出也將是一個半無限序列，[C]=c0,c1,c2,…ci,…，稱為卷積碼的碼字序列。卷積碼同樣有系統(tǒng)卷積碼和非系統(tǒng)卷積碼之分。系統(tǒng)卷積碼的碼字中明顯的包含著k0位信息碼元，而非系統(tǒng)卷積碼的信息碼元是隱含在碼字中的。圖7-4(2,1,2)卷積碼編碼器原理圖如下圖，為一個(2,1,2)非系統(tǒng)卷積碼的編碼器；約束關(guān)系為：ci(1)=mi-2+mi-1+mici(2)=mi-2+mi如果輸入的信息序列為：[m]=(m0,m1,m2,……)=(1,1,1,……)那么輸出的碼字序列為：[C]=(11,01,10,……)。7.1.2卷積碼的監(jiān)督矩陣描述同分組碼一樣，卷積碼也可以用生成矩陣和監(jiān)督矩陣來描述。[截短卷積碼的根本監(jiān)督矩陣]：通過一個例子說明：看一個(3,1,2)系統(tǒng)卷積碼，其編碼電路為：圖7-5(3,1,2)系統(tǒng)卷積碼編碼器原理圖n0=3,k0=1,m=2,m’=m+1=3輸入信息序列：m={……mi+1,mi,mi-1,mi-2,……}輸出碼字為：[ci]={mi,pi1,pi2}可以看出其監(jiān)督關(guān)系為：pi1=mi+mi-1pi2=mi+mi-2下面看一下在編碼器一個約束長度的監(jiān)督關(guān)系：0mi-2+0pi-2,1+0pi-2,2+1mi-1+0pi-1,1+0pi-1,2+1mi+1pi,1+0pi,2=01mi-2+0pi-2,1+0pi-2,2+0mi-1+0pi-1,1+0pi-1,2+1mi+0pi,1+1pi,2=0寫成方程的矩陣形式：000100110[Ci]T=[0]100000101其中碼字序列[Ci]為截短卷積碼；[Ci]=[ci-2,ci-1,ci]=[mi-2,pi-2,1,pi-2,2,mi-1,pi-1,1,pi-1,2,mI,pi,1,pi,2]定義其系數(shù)矩陣為：[h]=000100110=[P20P10P0I2]=[h2h1h0]100000101稱為截短卷積碼的根本監(jiān)督矩陣。[P2]=0[P1]=1[P0]=1[0]=0[I2]=10101001根本監(jiān)督矩陣的一般形式為：[h]=[Pm0Pm-10……P10P0Ir0]=[hmhm-1……h(huán)1h0]hm=Pm0;hm-1=Pm-10……h(huán)1=P10;h0=P0Ir0;根本監(jiān)督關(guān)系為：[h][Ci]T=[0][h]矩陣為n0-k0=r0行，(m+1)×n0列矩陣；Ir0矩陣為(n0-k0)×(n0-k0)單位陣；0矩陣為(n0-k0)×(n0-k0)零矩陣；Pm矩陣為(n0-k0)×k0階矩陣；例如上面介紹的(3,2,2)系統(tǒng)卷積碼的根本監(jiān)督矩陣為：[h]=[100010111]r0=3-2=1行;(m+1)×n0=3×3=9列矩陣；P2=[10];P1=[01];P0=[11]。h2=100;h1=010;h0=111;[初始截短卷積碼的監(jiān)督矩陣]：初始截短卷積碼定義為：在編碼器初始狀態(tài)為零時，初始輸入m+1個信息碼字編碼器輸出的卷積碼。即：[C]初=[c0c1…cm]，根據(jù)根本監(jiān)督矩陣的定義，可以很方便地得到初始截短卷積碼的監(jiān)督關(guān)系為：[H]初[C]初=[0]，而監(jiān)督矩陣為：[H]初=P0Ir0=h0P10P0Ir0h1h0……Pm0Pm-10……P10P0Ir0hmhm-1……h(huán)1h0[H]初矩陣為(m+1)×r0行；(m+1)×n0列；(3,1,2)卷積碼的[H]初為：[H]初=h0=110101h1h0100110000101h2h1h0000100110100000101(3,2,2)卷積碼的[H]初為：[H]初=h0=111h1h0010111h2h1h0100010111[卷積碼的監(jiān)督矩陣]；上面介紹的是初始截短卷積碼的監(jiān)督矩陣，實際上卷積碼的監(jiān)督矩陣應(yīng)當(dāng)是一個有頭無尾的矩陣，它對應(yīng)的根本監(jiān)督關(guān)系為：[H][C]T=[0]其中：[C]=[C0,C1,C2,……Cm,Cm+1,……][H]=P0Ir0=h0P10P0Ir0h1h0…………Pm0Pm-10……P10P0Ir0hmhm-1……h(huán)1h0Pm0Pm-10……P10P0Ir0hmhm-1……h(huán)1h0Pm0Pm-10……P10P0Ir0hmhm-1……h(huán)1h0….….……例如(3,2,2)卷積碼的監(jiān)督矩陣為：[H]=h0=111h1h0010111h2h1h0100010111…h(huán)2h1h0100010111…h(huán)2h1h01000101117.1.3卷積碼的生成矩陣描述卷積碼同樣也可以用生成矩陣來描述，[卷積碼的生成矩陣]：同分組碼一樣，卷積碼的生成矩陣與監(jiān)督矩陣同樣也有相互正交的關(guān)系：因此，可以很方便的得到：截短卷積碼的根本生成矩陣的一般形式為：[g]=[g0g1……gm]=[Ik0P0T0P1T……0PmT]初始截短卷積碼的生成矩陣的一般形式為：[G]初=g0g1……gm=Ik0P0T0P1T……0PmTg0……gm-1Ik0P0T……0Pm-1T…………g0Ik0P0T卷積碼的無窮生成矩陣的一般形式為：[G]=g0g1……gm=Ik0P0T0P1T……0PmTg0g1……gmIk0P0T0P1T……0PmT…………g0g1……gmIk0P0T0P1T……0PmTg0g1……gmIk0P0T0P1T……0PmT…………例如：(3,1,2)卷積碼的這幾種矩陣分別為：[h]=000100110=[P20P10P0I2]=[h2h1h0]100000101[g]=[111010001]=[I1P0T0P1T0P2T][G]初=g0g1g2=I1P0T0P1T0P2T=111010001g0g1Ik0P0T0P1T000111010g0Ik0P0T000000111[G]=g0g1g2=111010001g0g1g2111010001…………g0g1g2111010001g0g1g2111010001…………[卷積碼生成矩陣的多項式描述]：通過前面的(3,1,2)系統(tǒng)卷積碼的例子的編碼電路可以看出：編碼器的三個輸出支路可以由三個生成多項式來確定。g(1)(x)=1g(2)(x)=1+xg(3)(x)=1+x2一個(n0,k0,m)卷積碼的支路生成多項式的一般形式為：g(1)(x)=g0(1)+g1(1)x+…+gm(1)xmg(2)(x)=g0(2)+g1(2)x+…+gm(2)xm……g(n0)(x)=g0(n0)+g1(n0)x+…+gm(n0)xm如果用向量表示支路的生成多項式為：g(i)=[g0(i)g1(i)g2(i)……gm(i)]這時，卷積碼的根本生成矩陣為：[g]=[g0g1……gm]=[g0(1)g0(2)…g0(n0)g1(1)g1(2)…g1(n0)……gm(1)gm(2)…gm(n0)]g0=[g0(1)g0(2)…g0(n0)]g1=[g1(1)g1(2)…g1(n0)]……gm=[gm(1)gm(2)…gm(n0)]由這個根本生成矩陣可以得到卷積碼的生成矩陣和初始截短卷積碼的生成矩陣等。例如：(3,1,2)系統(tǒng)卷積碼的生成矩陣為：g(1)=[g0(1)g1(1)g2(1)]=[100]g(2)=[g0(2)g1(2)g2(2)]=[110]g(3)=[g0(3)g1(3)g2(3)]=[101]g0=[111]g1=[010]g2=[001][G]=111010001111010001……111010001111010001……[非系統(tǒng)卷積碼的描述]：利用這種生成多項式表示的生成矩陣特別適合描述非系統(tǒng)卷積碼。例如，前面介紹的(2,1,2)非系統(tǒng)卷積碼的支路生成多項式為：g(1)(x)=1+x+x2g(2)(x)=1+x2g(1)=[g0(1)g1(1)g2(1)]=[111]g(2)=[g0(2)g1(2)g2(2)]=[101]其根本生成矩陣為：[g]=[111011]生成矩陣為：[G]=111011111011……111011111011……非系統(tǒng)卷積碼的監(jiān)督矩陣從電路圖中很難得到，較好的方法是先得到生成矩陣，然后再由生成矩陣求監(jiān)督矩陣，〔作練習(xí)〕。7.1.4卷積碼的編碼舉例看以下(2,1,3)非系統(tǒng)卷積碼的例子：圖7-6(2,1,3)非系統(tǒng)卷積碼編碼器原理圖其兩個支路的生成多項式分別為：g(1)(x)=1+x2+x3g(2)(x)=1+x+x2+x3g(1)=[g0(1)g1(1)g2(1)g3(1)]=[1011]g(2)=[g0(2)g1(2)g2(2)g3(2)]=[1111]當(dāng)輸入的碼字序列為[m]=[10111]時，求輸出的卷積碼？[生成矩陣方法]：由生成多項式可以得到其生成矩陣為：g0=[g0(1)g0(2)]=[11];g1=[g1(1)g1(2)]=[01];g2=[g2(1)g2(2)]=[11];g3=[g3(1)g3(2)]=[11];[G]=g0g1g2g3=11011111g0g1g2g311011111g0g1g2g311011111g0g1g2g311011111g0g1g2g311011111由[C]=[m][G]=[10111][G]=[1101000101010011]在計算矩陣乘法時，實際上假設(shè)信息序列的后續(xù)為零狀態(tài)〔三個0〕即認為：[m]=[10111000]。[時域卷積方法]：利用時域卷積的方法可以分別得到編碼器兩個支路的輸出序列，然后將兩個支路的序列交織后可以得到編碼器的輸出序列。[C(1)]=[m]*[g(1)]=[10111]*[1011]=[10000001][C(2)]=[m]*[g(2)]=[10111]*[1111]=[11011101]注：時域卷積方法：(反轉(zhuǎn)-交錯-乘積和)101110001011100010111000101110001101110111011101100(1+1)0(1+1)1011100010111000101110001011100011011101110111010001即：[10111]*[1011]=[10000001]101110001011100010111000101110001111111111111111110(1+1)1(1+1+1)1011100010111000101110001011100011111111111111111101即：[10111]*[1011]=[11011101]由此可以得到輸出序列為：[C]=[C0,C1,C2,C3,C4…]=[C0(1)C0(2),C1(1)C1(2),C2(1)C2(2),C3(1)C3(2),C4(1)C4(2),…]=[1101000101010011][多項式計算方法]：對于線性系統(tǒng)來說，時域上的卷積可以用域上多項式的乘法運算來代替。對于(2,1,3)非系統(tǒng)卷積碼：g(1)(x)=1+x2+x3g(2)(x)=1+x+x2+x3當(dāng)輸入序列為[m]=[10111]時，m(x)=1+x2+x3+x4C(1)(x)=m(x)g(1)(x)=(1+x2+x3+x4)(1+x2+x3)=1+x7C(2)(x)=m(x)g(2)(x)=(1+x2+x3+x4)(1+x+x2+x3)=1+x+x3+x4+x5+x7將兩個支路的序列交織合成為一個輸出序列為：C(x)=C(1)(x2)+xC(2)(x2)=1+x14+x(1+x2+x6+x8+x10+x14)=1+x+x3+x7+x9+x11+x14+x15對應(yīng)序列為：[C]=[1101000101010011]如果對于一個一般的(n0,k0,m)卷積碼編碼器，其支路生成多項式為：g(1)(x)=g0(1)+g1(1)x+…+gm(1)xmg(2)(x)=g0(2)+g1(2)x+…+gm(2)xm……g(n0)(x)=g0(n0)+g1(n0)x+…+gm(n0)xm支路輸出序列為：C(1)(x)=m(x)g(1)(x)C(2)(x)=m(x)g(2)(x)……C(n0)(x)=m(x)g(n0)(x)合路輸出序列為：C(x)=C(1)(xn0)+xC(2)(xn0)+x2C(3)(xn0)+……+xn0-1C(n0)(xn0)另外還有一種利用多項式計算輸出序列的方法：首先得到一個復(fù)合生成多項式，g(x)=g(1)(x2)+xg(2)(x2)=(1+x4+x6)+x(1+x2+x4+x6)=1+x+x3+x4+x5+x6+x7C(x)=m(x2)g(x)=(1+x4+x6+x8)(1+x+x3+x4+x5+x6+x7)=1+x+x3+x7+x9+x11+x14+x15如果對于一個一般的(n0,1,m)卷積碼編碼器，其復(fù)合生成多項式為：g(x)=g(1)(xn0)+xg(2)(xn0)+x2g(3)(xn0)+……+xn0-1g(n0)(xn0)下面給出幾種典型的卷積碼的編碼電路和生成多項式，通過練習(xí)掌握計算：根本生成矩陣，初始截短碼生成矩陣，復(fù)合生成多項式，及各種方法計算輸出序列等。7.2卷積碼的維特比譯碼7.2.1卷積碼的狀態(tài)圖描述卷積碼的編碼器是一個時序網(wǎng)絡(luò)，其工作過程可以用一個狀態(tài)圖來描述。編碼器的狀態(tài)由它的移位存放器的內(nèi)容確定。例如(2,1,3)非系統(tǒng)卷積碼，有k0個信息位，m位移位存放器，共有2m=23=8個不同狀態(tài)。其狀態(tài)可以表示為：Si=[D2,D1,D0]，分別為：S0=[000]，S1=[001]，S2=[010]，……S7=[111]。根據(jù)(2,1,3)卷積碼的生成多項式或生成矩陣，可以確定它的唯一的狀態(tài)圖為：圖7-7(2,1,3)非系統(tǒng)卷積碼狀態(tài)圖其中狀態(tài)轉(zhuǎn)移線上的數(shù)字表示，某一時刻編碼器輸入某一信息位后，編碼器輸出的碼元序列。例如：1/10表示編碼器輸入為1時，輸出為10。如果，編碼器輸入為m=[10111]，那么輸出為[C]=[1101000101010011]，與上一節(jié)中例子相同。M序列后面補三個0，這時編碼器狀態(tài)變化路經(jīng)為：S0—S1—S2—S5—S3—S7—S6—S4—S0。例如：(3,1,2)非系統(tǒng)卷積碼。三個支路的生成多項式分別為：g(1)(x)=1+xg(2)(x)=1+x2g(3)(x)=1+x+x2電路原理圖為：圖7-8(3,1,2)非系統(tǒng)卷積碼編碼器原理圖其編碼器的狀態(tài)為Si=[D1,D0]其狀態(tài)圖如下：當(dāng)輸入為m=[11101]時，輸出為：[C]=[111，010，001，110，100，101，011]狀態(tài)變化路徑為：S0—S1—S3—S3—S2—S1—S2—S0。圖7-9(3,1,2)非系統(tǒng)卷積碼狀態(tài)圖7.2.2卷積碼的格子圖〔籬笆圖〕卷積碼的格子圖是將編碼器的狀態(tài)圖按時間展開形式。(3,1,2)非系統(tǒng)卷積碼的格子圖例子如下，只畫出信息序列長度L=5。圖7-10(3,1,2)非系統(tǒng)卷積碼格子圖說明：對于L=5的格子圖，圖中含有L+m+1級。格子0到格子L+m，本例中L=5,m=2,L+m=7，為0-7級。除了初始狀態(tài)后面m=2個狀態(tài)假設(shè)為0狀態(tài)輸入外，格子圖的中間狀態(tài)均為兩個輸入分支和兩個輸出分支。對于每個狀態(tài)的輸出分支，上分支表示輸入信息位為mi=0，下分支表示輸入的信息位為mi=1，每個分支上的n0個序列表示輸出碼序列。長度為L+m的2L個碼字，每個碼字都對應(yīng)于格子圖上的唯一一條路徑。7.2.3譯碼量度假設(shè)：長度為L的信息碼序列m=[m0,m1,m2,m3,m4]=[m0,m1,……mL-1]；編成長度為N=n0(L+m)的卷積碼，C=[C0,C1,C2,……CL-1]；其中Ci=[ci0,ci1,…cino-1]；接收碼字序列為C’=[C’0,C’1,C’2,……C’L+m-1]；或者將發(fā)送碼字和接收碼字寫成：C=[c0,c1,c2,……cN-1]；如果m=2；L=5；n0=3；那么N=3〔5+2〕=21；C’=[c’0,c’1,c’2,……c’N-1]；譯碼的過程就是根據(jù)接收碼字C’來產(chǎn)生發(fā)送碼字C的估計值C’’。維特比譯碼實際上是一種最大似然譯碼。最大似然譯碼就是根據(jù)似然函數(shù)為最大的一種估計準那么。似然函數(shù)表示為：根據(jù)：；可得根據(jù)最大似然準那么的分析，當(dāng)信源狀態(tài)的先驗概率相等時，它是一種最小錯誤譯碼概率準那么。其中的p(ci’/ci)就是信道轉(zhuǎn)移概率?？梢钥闯?，這個對數(shù)似然函數(shù)是一個與卷積碼格子圖上的路徑有關(guān)的度量。在維特比譯碼算法中定義它為譯碼路徑量度。記為：其中：分別稱為路徑量度、分支量度和比特量度。定義：一條譯碼路徑的前j個分支的局部路徑量度為：在卷積碼的維特比譯碼過程中，就是根據(jù)接收到的碼字序列C’，在格子圖上找到具有最大量度的路徑，實際上就是找到最大似然路徑。對于信道轉(zhuǎn)移概率p<0.5的BSC信道，可以證明似然函數(shù)有：其中：d(C’,C)為C’與C之間的漢明距離，由于對于所有的C’，，并且為常數(shù)。因此，只要d(C’,C)最小，就可以使似然函數(shù)最大。因此，維特比算法對于BSC信道來說，就可以使用漢明距離作為譯碼量度，即選擇最小漢明距離的路徑作為幸存路徑。(Suiviver)7.2.4維特比算法由初始狀態(tài)經(jīng)過m個時間單位〔定時〕，從時間j=m開始，計算進入每一個狀態(tài)的每一條路徑的局部路徑量度。對于每一個狀態(tài)，比擬進入它的各條路徑的局部量度，其中量度最大〔漢明距離最小〕的路徑及其量度被保存下來，這個路徑稱為進入這個狀態(tài)的幸存路徑。進入下一個單位時間j+1，計算進入某一個狀態(tài)的分支量度，并與前一個時間的有關(guān)幸存路徑的量度相加。比擬此時的局部量度，選出最大者，作為進入此狀態(tài)的幸存路徑，存儲其路徑和量度，刪除其它路徑和量度。如果一個狀態(tài)的兩個路徑量度相等，可以都保存〔也可以刪除一個〕。如果j<L+m，那么重復(fù)〔2〕步，否那么就停止計算。對于(n0,k0,m)卷積碼，如果發(fā)送的碼字為L個，即Ln0個碼元，那么譯碼算法到L+m個時間單位后，應(yīng)當(dāng)進入到一個全零狀態(tài)，這時只有一個幸存路徑。這時譯碼算法結(jié)束。[譯碼舉例]：(3,1,2)非系統(tǒng)卷積碼的維特比譯碼。假設(shè)：發(fā)送碼字為：C=[111，010，110，011，111，101，011]接收碼字為：C’=[110，110，110，111，010，101，101]有7個碼元錯誤。維特比算法：第一步：計算j=m=2級分支以前的各個狀態(tài)的各路徑的量度。利用接收碼字序列與格子圖上的序列進行比擬。S0=(4);S1=(3);S2=(3);S3=(2)括號里面的數(shù)字就是進入該狀態(tài)的漢明距離。第二步：計算從j=2到j(luò)=3的局部路徑，與原路徑量度相加，并刪除一個漢明距離較大的路徑。如下表：S0S1=(5)S0-S0=(6)×漢明距離大，刪除S0=(6)S2-S0=(5)√漢明距離小，保存S1S3=(4)S0-S1=(5)×漢明距離大，刪除S2=(5)S2-S1=(4)√漢明距離小，保存S2S1=(4)S1-S2=(5)×漢明距離大，刪除S0=(5)S3-S2=(2)√漢明距離小，保存S3S3=(5)S1-S3=(4)√漢明距離小，保存S2=(2)S3-S3=(5)×漢明距離大，刪除第三步：計算從j=3到j(luò)=4的局部路徑，與原路徑量度相加，并刪除一個路徑。S0S1=(5)S0-S0=(8)×漢明距離大，刪除S0=(8)S2-S0=(3)√漢明距離小，保存S1S3=(6)S0-S1=(5)×漢明距離大，刪除S2=(5)S2-S1=(4)√漢明距離小，保存S2S1=(4)S1-S2=(5)√漢明距離相等，保存S0=(3)S3-S2=(5)√漢明距離相等，保存S3S3=(6)S1-S3=(6)√漢明距離相等，保存S2=(5)S3-S3=(6)√漢明距離相等，保存第四步：計算從j=4到j(luò)=5的局部路徑，與原路徑量度相加，并刪除一個路徑。S0S1=(5)S0-S0=(4)√漢明距離小，保存S0=(4)S2-S0=(6)×漢明距離大，刪除S1S3=(4)S0-S1=(5)√漢明距離小，保存S2=(7)S2-S1=(7)×漢明距離大，刪除S2S1=(7)S1-S2=(7)√漢明距離相等，保存S0=(6)S3-S2=(7)√漢明距離相等，保存S3S3=(8)S1-S3=(4)√漢明距離相等，保存S2=(7)S3-S3=(8)×漢明距離大，刪除第五步：計算從j=5到j(luò)=6的局部路徑，與原路徑量度相加，并刪除一個路徑。S0-S0=(6)√漢明距離小，保存S2-S0=(9)×漢明距離大，刪除S1-S2=(5)√漢明距離小，保存S3-S2=(6)×漢明距離大，刪除第六步：計算從j=6到j(luò)=7的局部路徑，與原路徑量度相加，并刪除一個路徑。S0-S0=(8)×漢明距離大，刪除S2-S0=(7)√漢明距離小，保存最后得到的譯碼路徑為S0—S1—S3—S2—S0—S1—S2—S0。相應(yīng)的譯碼序列為：C=[111，010，110，011，111，101，011]可見這種譯碼算法具有很強的糾錯能力。如下圖。圖7-11卷積碼的維特比譯碼舉例第八章信息率失真理論限失真信源編碼前面我們介紹了無失真信源編碼和有噪聲信道編碼的問題。概括地講，無論是有噪聲信道還是無噪聲信道，只要傳信率小于信道容量，總能找到一種編碼方法，使誤碼率任意小，同時使傳信率任意接近信道容量。另外，在實際系統(tǒng)中，人們一般并不要求完全無失真地恢復(fù)消息，而是允許一定的失真或過失。即在一定的保真度條件下的傳輸信息。例如語音信號為20Hz-8kHz的范圍，但其主要能量集中在300Hz-3400Hz范圍內(nèi)。如果是無失真信源編碼，描述信源的最少比特數(shù)為信源的熵H(S)。那么在限失真條件下，描述信源的最少比特數(shù)為多少那？.1失真度與平均失真函數(shù)我們看下列圖8-1的通信系統(tǒng)模型，由于這里我們只考慮信源編碼問題，因此我們將新到編碼和譯碼都看成信道的一局部。同時把這個信道看成沒有干擾的無噪聲信道。這時接收消息的失真是產(chǎn)生于信源編碼，而不是新到干擾。從直觀的感覺知道，允許失真越大，傳信率就越大，允許失真越小，傳信率就越小。另外，我們信源編碼產(chǎn)生的失真等價看成由信道干擾造成的，也就是用信道轉(zhuǎn)移概率描述信源編碼造成的失真。我們這種信道稱為試驗信道，如圖8-2所示。圖8-1通信系統(tǒng)的信道模型圖8-2試驗信道模型[1]失真度〔失真函數(shù)〕定義設(shè)離散無記憶信源的狀態(tài)空間為U={u1,u2,……ur}，概率空間為P(U)={p(u1),p(u2),……p(ur)}。接收的離散隨機變量為V={v1,v2,……vs}。對應(yīng)每一對(u,v)，我們定義一個非負函數(shù)；稱為編碼信源單個符號的失真度。它表示由發(fā)送符號到接收符號產(chǎn)生的失真。它的值越小表示失真越小，=0表示無失真?？梢杂靡粋€矩陣表示每個符號對產(chǎn)生的全部失真。我們稱為失真矩陣。例如：二元對稱信源，U={0，1}，V={0，1}。用所謂漢明失真定義的失真矩陣為：可以看到：失真矩陣就類似于信道轉(zhuǎn)移概率矩陣。[2]平均失真度由于U和V都是隨機變量，因此也是一個隨機變量。因此，編碼信源的平均失真度為：設(shè)離散無記憶信源的狀態(tài)空間為U={u1,u2,……ur}，概率空間為P(U)={p(u1),p(u2),……p(ur)}。接收的離散隨機變量為V={v1,v2,……vs}。那么：平均失真度描述了一個信源和信道的整體失真特性，即一個信源在一個試驗信道上傳輸?shù)氖д娲笮　3]隨機序列〔N維隨機向量〕信源的失真度〕如果不是單符號信源，而是N維隨機向量信源，；。Ui取值于{u1,u2,……ur}，Vi取值于{v1,v2,……vs}。因此，U共有rN個不同的符號序列，V共有sN個不同的符號序列。這時，單個序列的失真度為：這時的N維序列信源的平均失真度為：也可以寫成：根據(jù)這個結(jié)果可以看出，信源平均失真度〔單個信源符號的平均失真度〕為：如果N維向量的多符號信源為離散無記憶信源，信道為離散無記憶信道，那么N維序列信源的平均失真度為：而信源的平均失真度為：如果信源為離散平穩(wěn)無記憶N維信源，在無記憶信到上，那么：即N維序列的平均失真度等于單個符號平均失真度的N倍。當(dāng)信源固定，單個符號失真度固定，選擇不同的試驗信道，相當(dāng)于不同的編碼方法，得到不同的平均失真度。但凡滿足失真度準那么的這些信道稱為D失真允許試驗信道。所有D失真允許試驗信道組成一個集合，用符號BD表示，即:.2信息率失真函數(shù)對于給定的信源，又確定了失真函數(shù)后，我們總是希望在滿足失真的情況下，使傳信率盡量小。這一點與信道容量的問題相反。實際上就是滿足平均失真度條件下求平均交互信息量I(U,V)的最小值。設(shè)BD是所有滿足保真度條件的試驗信道的集合，因而可以在這個集合中找到一個信道，使量I(U,V)取最小值。平均交互信息量I(U,V)是信道轉(zhuǎn)移概率的下凸函數(shù)，所以這個最小值是存在的。由此定義信源的率失真函數(shù)為：其單位為比特/信源符號。對于N維隨機向量信源，信源的率失真函數(shù)定義為在保真度條件下，平均交互信息量的最小值，即它是在所有滿足失真度的N維試驗信道集合中，找到一個信道使平均交互信息量取最小值。對于離散無記憶平穩(wěn)信源，可以證明應(yīng)當(dāng)說明：在討論信源率失真函數(shù)時引入的信道轉(zhuǎn)移概率并沒有實際信道的意義。只是為了求交互信息量的最小值而引入的、假想的試驗信道。實際上它只是反映了不同的信源編碼方法。也就是說找到一種編碼方法使平均交互信息量到達最小值。8.1.3率失真函數(shù)與信道容量的對偶性從信道容量和信源率失真函數(shù)的定義我們可以看到：信道容量和率失真函數(shù)存在著對偶關(guān)系。信道容量是在信道一定的條件下，選擇試驗信源的先驗概率，使平均交互信息量到達最大值。信道容量反映信道的傳信能力，信道容量與信源無關(guān)，不同的信道就有不同的信道容量。解決的是信道編碼問題。信源率失真函數(shù)R(D)是在信源和失真度一定的條件下，選擇試驗信道的轉(zhuǎn)移概率〔實際上選擇信源編碼方法〕，使平均交互信息量到達最小值，R(D)是接收機在滿足一定失真條件下，恢復(fù)信源狀態(tài)所需要的最小平均信息量。率失真函數(shù)R(D)反映信源的可壓縮能力，率失真函數(shù)R(D)與信道無關(guān)，不同的信源就有不同的率失真函數(shù)。解決的是信源編碼問題。信道容量與率失真函數(shù)的對應(yīng)關(guān)系可以由下表表示。信息傳輸理論率失真理論信道固定信源固定試驗信源可變試驗信道可變平均誤碼概率為參量平均失真度為參量信道容量率失真函數(shù)信道編碼定理信源編碼定理.4最小失真度和最大失真度率失真函數(shù)R(D)是允許失真D的函數(shù)。下面給出R(D)的性質(zhì)。[1]最小平均失真度根據(jù)平均失真度的定義：它是一個非負實函數(shù)的數(shù)學(xué)期望，因此它也是一個非負實函數(shù)，所以它的下限一定為零，所以允許失真度D的下限的也一定是零，這就是不允許任何失真的情況。對于給定的信源[U,P(U)]，及給定的失真矩陣D，信源的最小平均失真度定義為：由上式可知，如果選擇適當(dāng)?shù)脑囼炐诺馈布葱诺擂D(zhuǎn)移概率〕，使對于每一個ui，其求和為最小，那么總和就是最小。當(dāng)固定一個ui值，對于不同的vj，其不同〔即在失真矩陣中D第i行的元素不同〕，其中必然有一個最小值，也可能有多個相同的最小值。我們可以選擇這樣的試驗信道，它滿足：(i=1,2,……n)那么可以使信源的最小平均失真度為：因此，允許失真度是否能到達零，取決于失真矩陣中每行元素中是否至少有一個零元素。如果至少有一個零元素，那么可以使。當(dāng)時，表示信源不允許有任何失真。在這里討論的問題，如果要求信源無失真的傳輸，就相當(dāng)于信息傳輸率〔熵速率〕就等于信源的熵，〔相當(dāng)于無噪聲信道〕相當(dāng)于這個等式的條件是失真矩陣的每一行至少有一個零，而每一列最多有一個零元素。否那么：它表示這時的信源符號集中有些符號可以壓縮，而不帶來失真。[例題]：對于一個信源U=(0,1)，信宿V={0,1,2}，失真矩陣〔失真度〕為：這時的最小失真度為：即滿足最小允許失真度的信道是一個無噪聲試驗信道，信道矩陣為：可以看出，如果我們選取允許失真度，那么在信道集合中BD就只有唯一可取的試驗信道，實際上是說明信源編碼方法只有一種就是一一對應(yīng)的無失真編碼，不允許壓縮。根據(jù)交互信息量的原理，在這個試驗信道中，因此：如果最小允許失真要求不為零，那么信道不要求為無噪聲信道，那么說明可能存在壓縮編碼方法。[2]最大平均失真度平均失真度也存在一個上界，率失真函數(shù)R(D)是一定條件下，平均交互信息量I(U,V)的最小值。I(U,V)是非負函數(shù)，R(D)也是非負函數(shù)，其下限為零。當(dāng)R(D)為零時對應(yīng)的平均失真度就是平均失真度的最大值。如下圖。圖8-3平均失真度的最大值平均失真度的最大值說明允許失真到達最大，已經(jīng)使交互信息量為0，沒有什么實際意義，理論上講，存在多種試驗信道，即多種信源壓縮方法，壓縮率很大以至于使平均交互信息量為零，即接收的符號已經(jīng)不包含信源發(fā)出的信息量。.5二元對稱信源的率失真函數(shù)信源的率失真函數(shù)的計算和信道容量的計算一樣都是復(fù)雜的問題，二元對稱信源是一種簡單情況，通過它的計算可以了解率失真函數(shù)的概念。設(shè)二元對稱信源U={0,1}，概率空間為p(u)={p(0)=ω;p(1)=1-ω}，接收變量V={0,1}。失真度矩陣為：因為最小失真度。計算可知滿足這個最小失真度要求的試驗信道是一個無噪聲信道〔無損信道〕，信道轉(zhuǎn)移矩陣為：根據(jù)率失真函數(shù)的定義，這時的最大允許失真度為：其中假設(shè)。通過計算可知，要到達這個最大允許失真度的試驗信道，信道轉(zhuǎn)移概率矩陣為：這個矩陣說明：當(dāng)信道傳送信源符號u=1時，可以正確接收，而當(dāng)信道傳送信源符號u=0時必然出現(xiàn)錯誤。信源u=0的概率為，所以信道的平均失真度為。在這個試驗信道下，可以計算最大失真度條件下的率失真函數(shù)為：而在一般情況下，時，平均失真度為：為信道平均錯誤概率。此時，如果選擇一個信道，使，得到平均交互信息量為：根據(jù)費諾不等式：當(dāng)n=2時：所以得：這是平均交互信息量的下限值。根據(jù)信息率失真函數(shù)的定義，當(dāng)時，平均交互信息量的下限值就是信息率失真函數(shù)的值。如何找到這樣的試驗信道，使其得到率失真函數(shù)的這個結(jié)果那？這是比擬麻煩的。對于二元對稱信道有一個簡單方法，“反向信道〞設(shè)計法。在原來的信道模型下假設(shè)考慮反向傳輸問題，如圖8-4所示。圖8-4二元對稱信道的反向信道這主要是一種尋找試驗信道的手段，假設(shè)一種信道正好以失真度D為轉(zhuǎn)移概率傳輸。其轉(zhuǎn)移概率矩陣P(U/V)為：根據(jù)的條件{p(u),p(u/v)}可以求出p(v)的概率分布。同時考慮：得到：因為，所以。說明這個反向信道是存在的。利用這個所謂的反向信道作為正向的試驗信道，其平均失真度為：可以看到這種利用反向信道尋找試驗信道的方法是可行的。計算得到：那么在該試驗信道上的交互信息量為：這樣我們就找到了滿足失真度D，同時率失真函數(shù)為R(D)的實驗信道。如圖8-5。圖8-5二元對稱信道的試驗信道圖8-6給出了不同情況下的率失真函數(shù)的曲線?？梢钥闯觯簩τ谝欢ǖ钠骄д娑?，信源分布越均勻，信源率失真函數(shù)就越大；信源分布越不均勻，率失真函數(shù)就越小，說明信源剩余度越大，壓縮的可能性就越大。率失真函數(shù)和實驗信道的求法還有正規(guī)的參量計算法和迭代計算法，就象信道容量的計算一樣，當(dāng)然也相對復(fù)雜一些，這里介紹的只是對于BSC的一種簡單方法。同樣還有連續(xù)信源的率失真函數(shù)的定義和計算方法，這里不在詳述。圖8-6不同信源分布下的率失真函數(shù).6限失真離散無記憶信源編碼定理率失真函數(shù)R(D)的物理意義是在一定的允許失真D條件下，每個信源符號可以被壓縮的最小信息量值，也就是最低信息傳輸速率。這里我們給出離散平穩(wěn)無記憶信源的限失真編碼定理，只介紹其物理含義。同樣可以推廣到連續(xù)信源和有記憶信源的情況。[定理]：〔山農(nóng)第三編碼定理〕設(shè)R(D)為一個離散平穩(wěn)無記憶信源的率失真函數(shù)，對于任意的以及足夠長的碼字長度n，總可以找到一種信源編碼方法C，使編碼后的碼字符號的平均失真度為：而碼字的個數(shù)為：對于二元編碼，R(D)單位為比特，那么碼字個數(shù)為：反之，平均失真度為，且的編碼方法是不存在的。[定理的含義]：①定理說明：對于任何的失真度，只要碼長足夠長，總可以找到一種編碼方法C，使編碼后每個信源符號〔碼元〕的信息速率為：即；同時。②定理說明：在允許失真D的條件下，信源最小的可以到達的信息傳輸率為R(D)。③限失真信源編碼的熵速率就是所謂率失真函數(shù)R(D)，在給定的允許失真D條件下，熵速率一般小于信源熵，即。而無失真信源編碼定理指出，其極限熵速率等于信源熵，即。④山農(nóng)第三定理也只是一個存在性定理，即定理沒有給出如何尋找最正確的編碼方法，使編碼后的熵速率到達。在實際應(yīng)用中該理論存在兩類問題：第一是實際信源的R(D)的計算相當(dāng)復(fù)雜，信源的數(shù)學(xué)描述就很困難；信源的失真度很難明確〔主觀和客觀評價難以數(shù)學(xué)描述〕；R(D)的計算太麻煩。第二是即使得到了符合實際的R(D)，還需要找到最正確的實用的信源壓縮編碼方法；這一點也很困難。例如：目前靜止圖象壓縮標準JPEG；運動圖象壓縮標準MPEG2、MPEG4；會議電視圖象壓縮標準H.261、H.263；會議電視語音壓縮標準G.711、G.722，G.723等。8.1.7限失真信源編碼舉例通過一個簡單例子說明限失真信源編碼的原理。[例題]：設(shè)一個二元無記憶信源，U={0,1}；P(U)={1/2,1/2}。該信源的熵為H(U)=1bit。根據(jù)山農(nóng)編碼第一定理，對這個信源進行無失真編碼，其平均碼長等于1，這時熵速率R=H(U)=1。如果進行限失真編碼，定義失真函數(shù)為漢明失真〔0/1失真〕為：即失真矩陣為：現(xiàn)在設(shè)計一種限失真信源壓縮編碼方法，就是把重復(fù)碼的反響用。做信源U的三次擴展信源，。這時我們把用表示，把用表示。然后再用0代表；用1代表。這樣就使原來的三個二進制信源符號壓縮成一個二進制信源符號。因此，這種編碼后的信息傳輸率為：比特/符號在接收端，當(dāng)收到0和1，就分別譯碼成和。例如，發(fā)送序列、傳輸序列、接收序列和譯碼序列表示如下表。發(fā)送序列：000101100110011111001…編碼序列：000111000111111111000…傳輸序列：0101110…接收序列：0101110…譯碼序列：000111000111111111000…可以計算：；；；；這樣的簡單壓縮編碼的平均失真度為：其中可以看到，經(jīng)過這種編碼方法壓縮后信息率為R’=