《信息論與編碼》課件1第5章

第5章有噪信道編碼

5.1最簡單的編碼方法5.2聯(lián)合ε典型序列5.3有噪信道編碼與Shannon第二編碼定理5.4Shannon理論對信道編碼的指導意義5.5線性分組碼5.6卷積碼5.7Turbo碼習題55.1最簡單的編碼方法本節(jié)從最簡單的編碼方法入手，了解噪聲通信中傳輸?shù)幕驹砗头椒?。由于噪聲的存在，當發(fā)送方發(fā)送信息比特0時，接收方收到的不一定是0。一個最簡單的想法是，當發(fā)送比特mi時，重復發(fā)送n遍，接收方根據(jù)接收序列中0和1的個數(shù)多少來判定發(fā)送方發(fā)送的比特，這種編碼方式稱做重復碼。

【例5.1】重復碼是信息長度k=1的(n,1)碼，其中,n是重復發(fā)送的長度，稱為碼長。經(jīng)過編碼后，碼字集合中只有兩個長度為n的碼字（000…0）和（111…1）。設它們通過二進制對稱信道傳輸，信道的轉(zhuǎn)移概率為P=10－1，碼長n可能取不同的值，進一步簡化情況，只考慮n=3、5、7、…，下面分別討論。

(1)n=3，（3，1）重復碼，兩個碼字是（000）和（111），可能接收到的向量為{000，001，010，011，100，101，110，111}。當發(fā)送000時：沒有出現(xiàn)錯誤，接收到000，判定為0：出現(xiàn)1比特錯誤，即可能接收到001、010、100時，仍可以判定為0，可以糾正1比特錯誤：出現(xiàn)2比特錯誤，即接收到110、101、011時，判定為1，此時就判錯了：出現(xiàn)3比特錯誤，即接收到111時，只能判定為1，此時也判錯了：那么就譯錯了。此時譯碼錯誤概率為Pe=1－P(0)－P(1)=1－(1－p)3－3p(1－p)2=2.8×10－2

(2)n=5，（5，1）重復碼，兩個碼字是（00000）和（11111），可以糾正2個錯，譯碼錯誤概率為

(3)n=7，（7，1）重復碼，兩個碼字是（0000000）和（1111111），可以糾正3個錯，譯碼錯誤概率為

對于信源［X,P］，每個符號的平均信息量為H(X)，則每個碼符號的平均信息量為(5.1)其單位為信息單位/碼符號。例如，當信息單位為比特時，每個碼符號的平均信息量的單位為比特/碼符號。由例5.1可知，每個信源符號所需要的碼元越多，傳輸效率越低。我們把編碼后的信息傳輸率定義為

其中,M為使用的碼字的個數(shù)，信源符號的個數(shù)不會超過M。由于在信源輸出和信道之間增加了信道編碼器，導致信源符號和信道輸入符號集不一致，因此碼元符號集和信道輸入符號集必須保持一致，以保證碼元符號在信道中能順利傳輸。(5.2)比特/碼符號在例5.1中，取n=3的重復碼，相當于在集合{000，001，010，011，100，101，110，111}中取出了兩個串000和111作為與信源符號0和1對應的碼字，故M=2。一般地，信道輸入符號集有r個符號，編碼長度為n時，可以組成的可用碼字個數(shù)為rn個。從中選取M(M<rn)個作為與信源符號對應的碼字，則選擇種類為

。同樣的個數(shù)M，選擇不同的碼字集合，對應的最小錯誤概率可能就不一樣。若信源符號集的符號個數(shù)為m，則應有m≤M。例5.1中，m=2，信源符號集為{0,1}。若取該信源符號集的離散無記憶二次擴展信源：X2={00,01,10,11}m=4,仍在{000，001，010，011，100，101，110，111}中選取M=m=4個碼字，則可以有種選擇方法。例如{000，001，010，100}、{000，011，100，110}和{000，010，100，110}，每一種選擇均可計算出相應的最小錯誤概率。在信道輸入符號集分布未知的情況下，我們假設等概率分布是合理的。對應碼字集合{000，001，010，100}的最小錯誤概率約為2.28×10－2，對應碼字集合{000，011，100，110}的最小錯誤概率約為2×10－2。若傳輸每個碼元的平均時間為t秒，則編碼后每秒鐘傳輸?shù)男畔⒘繛?/p>

在簡單重復編碼方法中，有以下結(jié)論（設t=1）：

n=1:R=1比特/碼符號Rt=1比特/秒(5.3)比特/秒n=3:比特/碼符號比特/秒n=5:比特/碼符號比特/秒

n=7:

比特/碼符號比特/秒可見，對于重復擴展編碼方法而言，Pe下降時，編碼信息傳輸率R也隨之下降。在實際的通信系統(tǒng)中，我們并不希望R下降太多，而是希望在保證R為一定值的前提下，使錯誤概率下降。顯然，重復編碼并不是最好的編碼方法。

【例5.2】信源符號集為{0，1}，離散無記憶二次擴展信源為{00，01，10，11}，信道為前述的二進制離散無記憶對稱信道，P(0|1)=P(1|0)=p<1/2。取碼長為5，且與輸入符號集有以下對應關系。輸入信源符號：ab

a,b∈{0,1}對應碼字：Abcdec=a

bd=ae=a

b故使用碼字{00000，01101，10111，11010}分別與{00，01，10，11}對應。信道輸出端可以有32種可能輸出結(jié)果，譯碼規(guī)則為

00000，00001，00010，00100，01000，10000，10001，00011譯碼成00000

01101，01100，01111，01001，00101，11101，11100，01110譯碼成01101

10111，10110，10101，10011，11111，00111，00110，10100譯碼成10111

11010，11011，11000，11110，10010，01010，01011，11001譯碼成11010此譯碼規(guī)則具有很強的規(guī)律性和對稱性（實際上，這個表稱之為陪集譯碼表）：1個全正確的碼字，5個錯一個碼元的碼字，1個第一和第五碼元錯誤的碼字，1個第四和第五碼元錯誤的碼字。信道看成是離散無記憶的5次擴展信道，故正確譯碼概率為PD=(1－p)5+5p(1－p)4+2p2(1－p)3錯誤概率為Pe=1－PD=1－{(1－p)5+5p(1－p)4+2p2(1－p)3}當p=0.01時，Pe≈7.8×10－4，比特/碼符號。此碼的編碼信息傳輸率與M=4,n=3的編碼相差不大，錯誤概率卻低得多：與M=2,n=3的編碼相比，錯誤概率相當，但編碼信息傳輸率要高。從前面的論述中可以看出，在有噪信道中消息傳輸?shù)腻e誤概率與所采用的編譯碼方法有關，那么在有噪信道中，有沒有存在一種最佳的編碼方法使得錯誤概率盡可能小呢？在使平均錯誤概率盡可能小的情況下，可達的最大的信息傳輸速率是多少呢？Shannon在1948年的論文中首先給出了肯定的回答，并指出這個可達的最大的信息傳輸速率是有噪信道的信道容量，這就是著名的Shannon第二編碼定理，也稱為有噪信道編碼定理。5.2聯(lián)合ε典型序列

Shannon在有噪信道編碼定理的證明中，采用的是基于聯(lián)合ε典型序列的思想。到目前為止，它是一種較為簡潔的證明。我們分析的信道是n次無記憶擴展信道，如圖5-1所示。圖5-1離散信道的n次無記憶擴展圖中：x=(x1,x2,…,xN)xi∈X

y=(y1,y2,…,yN)yi∈Y

P(xi)、P(yi)是單符號離散信道輸入和輸出的概率分布，其信道轉(zhuǎn)移概率為P(yi|xi)，而x和y都是n次無記憶擴展信道的輸入和輸出的長為n的隨機序列，已知其滿足

它們對應的信息熵和聯(lián)合熵為H(X)、H(Y)、H(XY)。

定義5.1

令H(X)是信源［X,P(x)］的熵，ε是正數(shù)，集合

稱為信源［X,P(x)］輸出的長為n的典型序列集。(5.4)其中：

Xn為X的n次離散無記憶擴展信源。上述定義又稱ε弱典型序列集。其實質(zhì)是由長為n、平均信息熵和H（X）相差不超過ε的所有矢量組成的集合。(5.5)

定義5.2

令x是信源［X,P(x)］發(fā)出的長為n的序列，ε是正數(shù)，集合：

稱為信源［X,P(x)］輸出的長為n的ε典型序列集。式（5.5）中,nk是在長為n的輸出序列中符號ak出現(xiàn)的次數(shù)。上述定義又稱做強ε典型序列集。其實質(zhì)是由長為n、每個符號的出現(xiàn)頻率和概率相差不超過ε的所有矢量組成的集合。

定義5.3

TX(n,ε)的補集稱為非典型序列集。

定理5.1（信源劃分定理）給定信源［X,P(x)］，ε是正數(shù)，當n→∞時，P{TX(n,ε)}→1,即對ε>0,n0使得當n>n0時，有P{x∈TX(n,ε)}≥1－ε

(5.6)

推論1（特定典型序列出現(xiàn)的概率）若x∈TX(n,ε)，則2－n［H(x)+ε］≤P(x)≤2－n［H(x)－ε］

(5.7)證明：由定義式(5.4)有：

不等式各項取指數(shù)即可得證。該推論說明，所有典型序列出現(xiàn)的概率都在同一范圍內(nèi)，當ε足夠小時，概率幾乎為一常量，且當n增大時，該概率隨nH(X)指數(shù)減少。(5.8)

推論2（典型序列的數(shù)目）當n足夠大時，對于給定的信源和ε>0，典型序列的數(shù)目滿足：(1－ε)2n［H(X)－ε］≤‖TX(n,ε)‖≤2n［H(X)+ε］

(5.9)

證明：

故‖TX(n,ε)‖≤2n［H(X)+ε］

據(jù)式(5.5)和式(5.6)有：

故‖TX(n,ε)‖≥(1－ε)2n［H(X)－ε］

證畢。由式(5.9)可知：

‖TX(n,ε)‖≈2nH(X)

(5.10)

信源劃分定理及其推論說明,一個離散無記憶信源的輸出符號序列可分成TX(n,ε)和兩組，有

。TX(n,ε)中各序列出現(xiàn)的概率幾乎相等，且每個序列中一個信源符號的平均信息量接近于信源的熵H(X)，所有典型序列的概率和趨向于1。因此，典型序列集又可稱為高概率集，非典型序列集稱為低概率集，信源的這種劃分性質(zhì)漸近等同于分割性。典型序列又稱做漸近等概序列。由于典型序列集在整個信源輸出序列中占絕對優(yōu)勢，所以在信息論的研究中可以忽略非典型序列集而只考察典型序列集。盡管TX（n,ε）中元素個數(shù)不少，約為2nH(X)個，但與‖Xn‖相比，仍是非常少的一部分。事實上，若‖X‖=r，則Xn中的元素個數(shù)為rn=2nlogr個，有：若－n［logr－H(X)－ε］>0，即信源非等概分布，則有n→∞時α→0。若信源等概,H(X)=logr，則由式(5.10)得：‖TX(n,ε)‖≈2nH(X)，即信源等概分布時幾乎所有序列都是典型序列。

定義5.4

令X、Y是兩個概率空間，x=(x1,x2,…,xN)∈Xn，y=(y1,y2,…,yn)∈Yn。若序列對x和y滿足：

(1)x是ε典型序列，即對任意小的正數(shù)ε，存在n，使得：

(5.11)

(2)y是ε典型序列，即對任意小的正數(shù)ε，存在n，使得：

(5.12)

(3)(x，y)是ε典型序列，即對任意小的正數(shù)ε，存在n，使得：

(5.13)

則稱序列對(x，y)是聯(lián)合ε典型序列，表示為TXY(n,ε)。給定y，稱集合：TX|Y(n,ε)={x：xy∈TXY(n,ε)}

(5.14)為條件y下X的ε典型序列。

定理5.2

當n足夠大時,有：‖TX|Y(n,ε)‖≤2n［H(X|Y)+2ε］(5.15)證明：|TX|Y(n,ε)|=0，引理顯然成立。，有：同理可證:

‖TY|X(n,ε)‖≤2n［H(Y|X)+2ε］

(5.16)證畢。

定理5.3

若對于x∈Xn,y∈Yn,x、y統(tǒng)計獨立，(x，y)是聯(lián)合ε典型序列，則當n足夠大時，有：(5.17)

證明：由于x、y均為典型序列，故有：(5.18)(5.19)(5.20)將上述三個不等式相應項相乘，考慮到：－I(X;Y)=H(XY)－H(X)－H(Y)

(5.21)證畢。如前所述，聯(lián)合ε典型序列要求(x，y)必須是ε典型序列，令：Lε=‖TX(n,ε)‖·‖TY(n,ε)‖

(5.22)由信源劃分定理推論2可得出Lε的上、下限為(1－ε)22n［H(X)+H(Y)-2ε］≤Lε≤2n［H(X)+H(Y)+2ε］

(5.23)

由式(5.20)和式(5.23)可得：

(5.24)由于ε為任意小的正數(shù)，因此(1－ε)－2≈1，從而TXY(n,ε)/Lε和式(5.17)中的量的上、下限保持一致。TXY(n,ε)/Lε為聯(lián)合ε典型序列的由ε典型序列x、y構成的空間中的平均密度。5.3有噪信道編碼與Shannon第二編碼定在前面的討論中已經(jīng)提到,在通信系統(tǒng)中，信道是非常重要的組成部分，且由于信道中隨機噪聲的存在，信道在傳輸符號時會產(chǎn)生畸變，從而使接收到的符號序列與發(fā)送端的符號序列不一致。為此，需要尋找編碼方法，在信道噪聲存在的情況下能夠檢測進而糾正發(fā)生錯誤的符號，以提高通信系統(tǒng)的可靠性。從概率的角度研究噪聲通信的問題就是要研究是否存在一種編碼方法使得編碼信息傳輸率保持較大，這就是著名的Shannon第二編碼定理，也稱為有噪信道編碼定理。任意給定希望達到的編碼信息速率R和錯誤概率限度ε，只要R小于信道容量，就可以找到一種編碼方法，使得碼長足夠大時，錯誤概率達到小于ε的要求。

定義5.5

對給定離散無記憶信道和任意ε>0，若有一種編碼信息速率為R的碼，在碼長n足夠大時，能使Pe<ε，則稱R是可達的。

定理5.4（Shannon第二編碼定理，有噪信道編碼定理）給定信道容量為C的離散無記憶信道［P(y|x)］，若編碼信息傳輸率R<C，則R是可達的。等價描述：給定信道容量為C的離散無記憶信道［P(y|x)］，若編碼信息傳輸率R<C，則只要碼長n足夠長，總可以在輸入集合中找到M個碼字對應M種可能的信源消息符號，組成一個碼集合，M≤2n(C－ε)，ε為任意小的正數(shù)，在一定的譯碼規(guī)則下，可使信道輸出的錯誤概率任意小。

解釋：設信道容量為C的離散無記憶信道有r個輸入符號（從而碼符號也有r個）、s個輸出符號，則碼長為N時，可將信道看成是離散無記憶的n次擴展信道，擴展信道的輸出符號集有sn種選擇，輸入符號集有rn種選擇，從rn種選擇中選出M種作為碼字，對應M種可能的消息符號。為了正確譯碼，應有M≤sn。下面我們來證明Shannon第二編碼定理。設信道輸入序列為x，x∈Xn，x=(x1,x2,…,xn)，輸出為y∈Yn,y=(y1,y2,…,yn)，轉(zhuǎn)移概率為

若發(fā)送消息為xm，接收序列為y，則在發(fā)送消息xm的條件下的譯碼錯誤概率為Pem=P(xk≠xm|y)消息獨立、等概時的平均錯誤率（針對每個XN）為

(5.25)其中,M為消息數(shù)目。從Xn中獨立隨機地選擇M=2nR個序列作為碼字，這相當于每個碼字出現(xiàn)的概率為

其中,R是要求的編碼信息傳輸率;x∈Xn，x=(x1,x2,…,xn)，并設X中的所有元素獨立、等概地出現(xiàn)。這種編碼方法稱為隨機編碼。取譯碼規(guī)則：對給定的接收序列y，若存在唯一的k∈［1,2nR］，使(xk,y)∈TXY(n,ε)則將y譯為xk，即F(y)=xk若實際發(fā)送的為xm，則當k≠m或兩個以上(含兩個)的k與y構成聯(lián)合ε典型序列時就認為出現(xiàn)譯碼錯誤。由于隨機碼具有對稱性，因此譯碼錯誤概率與送出消息的標號無關，即隨機碼集合的平均錯誤概率就是任一特定消息被錯誤譯碼的概率。不失一般性，設發(fā)送的是第一個消息，令事件：Em={(xm,y)∈TXY(n,ε)}

m∈［1,2nR］則發(fā)送消息x1時，譯碼錯誤概率為而又與j無關，故

由定理5.2得:

P(Ek)≤2－n［I(X;Y)－3ε］

(5.26)所以為了使R大，故使I(X;Y)極大化，即取I(X;Y)=C。若R<C－3ε，則n→∞時，上式趨向于０。由于錯誤概率非負，因此錯誤概率趨向于０。由于當R<C－3ε時，隨機碼集合的平均譯碼錯誤概率趨向于０，所以必然存在一種碼，當n足夠大時，其譯碼錯誤概率任意小。證畢。碼的個數(shù)為2nR，由于ε為任意小的正數(shù)，因此η=3ε仍為任意小的正數(shù)，故碼字數(shù)目滿足M=2nR≤2n(C－η)，η為任意小的正數(shù)，從而等價描述成立。借助于典型序列的概念，我們證明了離散無記憶信道編碼定理，指出只要R<C，必然存在編碼方法使譯碼錯誤概率任意小，卻未給出具體的編碼方法。那么當R>C時情況如何呢？信道編碼逆定理給出了答案。

定理5.5（信道編碼逆定理）設離散無記憶信道的信道容量為C，當信息傳輸速率R>C(選用碼字個數(shù)M=2n(C+ε))時，無論n多大也不能找到一種編碼，使譯碼錯誤概率任意小。證明：假設選用M=2n(C+ε)碼字組成的一個碼，每個碼字的概率是1/M，則離散無記憶信道的n次擴展信道的平均互信息為H（Xn）－H(Xn|Yn)≤nC

(5.27)則log2n(C+ε)－H(Xn|Yn)≤nC

(5.28)即nε≤H(Xn|Yn)由Fano不等式有：nε≤H(Xn|Yn)≤H(Pe)+Pelog(M－1)≤1+Pelog(M－1)所以nε≤1+Pelog(M－1)<1+PelogM=1+Pe(nC+nε)求得：

當n→∞時，，從而Pe為非零值。證畢。以上只是在離散無記憶信道的情況下對定理做了證明，事實上，Shannon第二編碼定理和逆定理對連續(xù)信道、有記憶信道同樣成立?，F(xiàn)已證明離散無記憶信道中譯碼錯誤概率Pe趨于零的速度與n（碼長）成指數(shù)關系，即當R→C時，譯碼錯誤概率為(5.29)式中,Er(R)為隨機編碼指數(shù)，又稱做可靠性函數(shù)，其表達式為其中,ρ為人為定義的修正系數(shù)，0≤ρ≤1。可見，可靠性函數(shù)又與輸入概率分布有關。一般Er(R)與R的關系曲線如圖5-2所示，是一條下凸函數(shù)。從圖5-2中可以看出，R<C時，Er(R)>0，所以式(5.29)表明Pe隨著n的增大以指數(shù)趨于零。

Shannon第二編碼定理只是一個存在性定理，它說明錯誤概率趨于零的好碼是存在的，但是并沒有給出怎么構造，盡管如此，它對信道編碼的發(fā)展仍具有重大的指導意義。(5.30)圖5-2Er(R)與R的關系曲線5.4Shannon理論對信道編碼的指導意義信息傳輸?shù)目煽啃允撬型ㄐ畔到y(tǒng)努力追求的首要目標。要實現(xiàn)高可靠性的傳輸，可采取諸如增大發(fā)射功率、增加信道帶寬、提高天線增益等傳統(tǒng)方法，但這些方法往往難度比較大，有些場合甚至無法實現(xiàn)。Shannon信息論指出：對信息序列進行適當?shù)木幋a后同樣可以提高信道的傳輸可靠性，這種編碼即為信道編碼。信道編碼是在著名的信道編碼定理的指導下發(fā)展起來的，幾十年來已取得了豐碩的成果。5.4.1二進制離散無記憶信道下的極限二進制對稱信道的信道容量為C=1+plogp+(1－p)log(1－p)比特/碼元(5.31)采用相干PSK信號發(fā)送和接收碼字比特，有(5.32)令式(5.31)中的C=Rc，求出滿足式(5.32)的Eb/N0值。假如采用碼率Rc=1/2的編碼方式，則為了獲得硬判決譯碼時該碼的容量，要求每比特最小信噪比約為1.6dB。當碼率漸近于零時，我們關心的是最小信噪比極限。在Rc較小時，概率p近似為

(5.33)把p的表達式代入式(5.31)，并利用式:

可把信道容量公式簡化為(5.34)再令C=Rc，在Rc趨近于零的極限情況下，可得:

（0.37dB）

(5.35)也就是說，在二進制離散信道下，只要傳輸每比特信息的信噪比不低于0.37dB，就可能實現(xiàn)完全無差錯的傳輸。

5.4.2AWGN信道下的理論極限由信息論中對波形信道的分析可知，當信道中的噪聲為加性高斯白噪聲時，其信道容量為

(5.36)其中,Ps是信號的平均功率，W為信道帶寬。令Ps=Rt·Eb，Rt為信息傳輸速率（比特/秒），Eb為傳輸每一比特信息所需的平均功率，則式(5.36)可化為

(5.37)式中,Eb/N0可理解為每赫茲帶寬傳輸每比特信息所需的信噪功率比。式(5.37)表明了通信系統(tǒng)中帶寬W、信道容量Ct、信噪比Eb/N0之間的定量關系。顯然，增加帶寬和提高信噪比都能使信道容量得到增加，從而使一定的信息傳輸率Rt下的錯誤概率減小。在信道帶寬不受限的情況下，信道容量僅取決于信噪比，進而此時傳輸可靠性主要由信噪比決定。由式(5.37)可得：

(5.38)令式(5.38)中W→∞，且Rt→C，則可得到可靠傳輸時所需的最小信噪比為(5.39)式(5.39)表示在帶寬不受限的高斯白噪聲信道中，只要傳輸每比特信息的信噪比不低于－1.6dB，就可能實現(xiàn)完全無差錯的傳輸。這是高斯信道中傳送信息的極限能力，這一信噪比的極限值稱為Shannon限。通過前面的分析可以知道，在二進制對稱信道下，達到信道容量所需要的信噪比為0.37dB，所以在實際的譯碼過程中建議采用波形信道模型，可獲得大約2dB的增益。當信道帶寬有限，且信道輸入為二元輸入時，需將式(5.37)中的Ct和Rt按通帶歸一化，令即得:

(5.40)或

(5.41)令R→Cn，則可得帶限信道中二元信息可靠傳輸時所需的信噪比為

(5.42)令碼率，則得：

(5.43)這是帶限高斯信道以1/2的碼率可靠傳輸每比特二元信息所需的最小信噪比，是Shannon限的另一種表述。實際上不采取任何編碼措施的傳輸系統(tǒng)是不可能以這么低的信噪比實現(xiàn)可靠傳輸?shù)?。采取信道編碼后，在某一誤碼率指標下，經(jīng)過仿真計算，所需信噪比可比不編碼時有明顯減少。編碼的分析設計有兩條基本途徑。一是不涉及具體的編碼，運用概率統(tǒng)計的方法，在特定信道條件下對編碼信號的性能作出統(tǒng)計分析，求出差錯概率的上下邊界，這就是本章前半部分的內(nèi)容。這種方法不能得知最優(yōu)碼是如何編出來的，卻能得出最優(yōu)碼可以好到什么程度，對指導編碼技術具有特別重要的理論價值。另一條途徑是數(shù)學解析途徑，將代數(shù)、集合、數(shù)論等理論運用到編譯碼中來設計某種碼，比如分組碼、卷積碼、Turbo碼等。本章后面幾節(jié)將簡單介紹這幾種編碼方式，主要目的是了解Shannon定理對編碼的指導意義。信道編碼更深、更系統(tǒng)的知識請參照相關的專業(yè)書籍。5.5線性分組碼本節(jié)討論糾錯碼中最基本的一類碼，即線性分組碼。這類碼有明顯的數(shù)學結(jié)構，它雖然簡單，但卻是各類碼的基礎，且許多已知的好碼都屬于線性分組碼。5.5.1線性分組碼的編碼為了引入線性分組碼的概念，首先看下面的例子。

【例5.3】任給一個由k=3位信息組成的信息組m=(m2,m1,m0)，由它生成的(6，3)線性分組碼的碼字v=(v5,v4,v3,v2,v1,v0)由下列關系式確定：由于每個信息組共有k=3位信息碼元，信息組集合共由23=8個不同的信息組構成，因此上述關系生成的(6，3)線性分組碼共有8個碼字。對于任意信息組m=(m2,m1,m0)，生成的碼字:v=(m2,m1,m0,m2+m1,m2+m0,m1+m0)

(5.44)若用向量與矩陣的乘積表示式(5.44)，則可寫成：v=(m2,m1,m0)G

其中:

稱為該(6，3)碼的生成矩陣。有了生成矩陣G，不難將23=8個信息組變換成表5-1所示的(6，3)碼的8個碼字。從生成的碼字可以看出，前k=3位是原信息組，而后n－k=3位是由式(5.44)確定的監(jiān)督元，因此我們稱(6，3)碼為系統(tǒng)碼。表5-1(6，3)碼的碼字

定義5.6

信息組以不變的形式，在碼字的任意k位中出現(xiàn)的碼稱為系統(tǒng)碼，否則，稱為非系統(tǒng)碼。一般地，我們把信息組排在碼的前k位，分析(n，k)系統(tǒng)碼的生成矩陣可以看出，它的左邊必然是一個k×k階單位矩陣，因此矩陣G的秩為k。若分別用Ik和P表示G的兩個矩陣塊，則生成矩陣G可表示成G=［Ik

P］(5.45)通常把上式表示的生成矩陣G稱為標準型生成矩陣，G的k行是線性無關的。事實上，G的每一行都是碼集合中的一個碼字，展開來寫就是：因此可歸納出一般(n,k)系統(tǒng)線性分組碼的結(jié)構形式如下：一般地，如果碼元vn－1,vn－2,…,vn－k也是mk－1,mk－2,…,m0的線性組合，則可得到非系統(tǒng)線性分組碼，即其中:

是一個秩為k的k×n階矩陣。當G是式(5.45)表示的標準型生成矩陣時，它才生成系統(tǒng)碼，這時它生成的碼字前k位是原信息組，后r=n－k位是監(jiān)督元。對于一般情況，如果不給出信息組和碼字的對應碼表，而只給出一個碼集合，如000000，001011，010101，011110，100110，101101，110011，111000此時我們無法知道該碼字對應哪個信息組。實際上，k個線性無關的碼向量的一切線性組合共有2k個可能，它恰好是V的2k個碼字，因此任意兩個碼字的和仍是碼字，而全零n維向量0=(00…0)是由信息組m=(00…0)生成的碼字，對于任意l∈F2，v∈V，則lV仍是V中的碼字，即(n,k)線性分組碼V是n維線性空間Vn(2n)的一個k維子空間。既然(n,k)分組碼的2k個碼字組成了一個k維子空間，那么這2k個碼字完全可由k個獨立向量所組成的基底而生成。設基底為若把這組基底寫成矩陣形式，則有(n,k)碼的任何碼字都可由這組基底的線性組合而生成，即若已知信息組m，通過上式可求得相應的碼字，稱上式中的G為(n,k)碼的生成矩陣。例如表5-1中的(6,3)碼，可從它的8個碼字中任意挑選出k=3個線性無關的碼字，作為碼的生成矩陣的行，則也可以是

下面介紹一下描述分組碼的幾個參數(shù)。

定義5.7

碼率R=k/n表示(n，k)分組碼中，信息位在碼字中所占的比重。

定義5.8

漢明距離d(a,b)表示向量a與b不相等的對應分量的個數(shù)，簡稱距離。

定義5.9

n重向量v中非零碼元的個數(shù)稱為漢明重量，用W(v)來表示。

(n，k)分組碼中，任兩個碼字之間距離的最小值稱為該分組碼的最小漢明距離dmin，簡稱最小距離，即dmin=min{d(vi,vj)|vi,vj∈v,i≠j}

R和dmin是(n，k)分組碼的兩個重要的參數(shù)。糾錯編碼的基本任務之一就是構造出R一定、dmin盡可能大的碼字，或dmin一定、R盡可能高的碼字。5.5.2最小距離譯碼譯碼器接收到一個二進制序列，而譯碼器輸出的是信息序列m的估值序列。譯碼器的基本任務就是根據(jù)某種譯碼規(guī)則，由接收序列R給出與發(fā)送的信息序列m最接近（最好是相同）的估值序列。由于m與碼字v之間存在一一對應的關系，所以這等價于譯碼器根據(jù)R產(chǎn)生一個v的估值序列。顯然，當且僅當=v時，=m，這時譯碼器正確譯碼。當給定接收序列R時，譯碼器的條件譯碼錯誤概率定義為(5.46)所以，譯碼器的錯誤譯碼概率:

(5.47)

P(R)是接收R的概率，與譯碼方法無關，所以譯碼錯誤概率最小的最佳譯碼規(guī)則是使(5.48)因此，如果譯碼器對輸入的R，能在2k個碼字中選擇一個使最大的碼字vi作為v的估值序列，則這種譯碼規(guī)則一定使譯碼器輸出錯誤概率最小，稱這種譯碼規(guī)則為最大后驗概率譯碼。由貝葉斯公式得到:若發(fā)端V中每個碼字等概率發(fā)送，即假設先驗概率P(v)相等，則P(v）=1/2k，且由于P(R)與譯碼方法無關，所以后驗概率P(v|R)最大等價于條件概率P(R|v)最大，P(R|v)稱為似然函數(shù)，這種譯碼準則稱為最大似然譯碼，記為MLD。顯然，最大似然譯碼等價于最大后驗概率譯碼。當r與vj的距離最小時，認為發(fā)方發(fā)送vj、收到r的概率最大，可以據(jù)此譯碼。其依據(jù)是下面的定理。

定理5.6

如果BSC信道的轉(zhuǎn)移概率p是一個很小的數(shù)，則當接收到的r與V中的碼字vj的距離最小，即d(r,vj)<d(r,vi)i=1,2,…,qk;i≠j時，發(fā)端發(fā)送vj、收到r的條件概率最大，即P(r|vj)>P(r|vi)i=1,2,…,qk;i≠j證明：設d(r,vj)=d，對于V中任意一個碼字vi≠vj，令d(r,vi)=d′，由定理條件知d<d′，于是發(fā)送vj、收到r的條件概率為P(r|vj)=pd(1－p)n－d≈pd發(fā)送vi、收到r的條件概率為P(r|vi)=pd′(1－p)n－d′≈pd′

由于d<d′，且p是一個很小的數(shù)，因此有pd>pd′，P(r|vj)>P(r|vi)由此可見，對于硬判決譯碼，在先驗等概的情況下，最大似然譯碼等價于最小距離譯碼。

【例5.4】一個數(shù)字通信系統(tǒng)的誤碼率為P=10－4，因而收到一個7位碼元的碼字有一位碼元有錯的概率為

同理，有2~7位碼元有錯的概率分別為如果不發(fā)生錯誤的概率為P(0)，則P(0)=(1－p)7≈0.9993由以上結(jié)果可以看出：P(0)>>P(1)>>…>>P(7)即發(fā)生t個錯誤的概率遠遠大于發(fā)生t+1個錯誤的概率。因此，當我們收到一個r時，若它不屬于碼集V，則可將r與V中所有碼字作比較。當r與vj的距離最小時，發(fā)送vj、收到r的條件概率最大，因而可將r判決為vj。實現(xiàn)最小距離譯碼有一種直觀的方法，即計算接收到的碼字與所有可能發(fā)送的碼字之間的距離，取距離最小的碼字為譯碼結(jié)果，也就是將收到的碼字與碼集合當中所有可能的碼字進行比較，與哪個碼字的距離最小，就判決輸出。這種方法固然實現(xiàn)了最小距離譯碼的思想，但事實上，當碼長較長時，計算量相當大，無法實現(xiàn)。下面介紹一種最簡單的譯碼方法，稱為陪集譯碼。構造譯碼表的方法如下：（1）表的第一行為2k個碼字，全0碼字放在最左邊。（2）將所有可能的n維向量中重量最小的，且在前面行中沒有出現(xiàn)過的向量放在此行的第一列中，將此向量與碼向量相加，放到此行相應的列上。

(3)重復第(2)步，直到2n個向量完全分到表中。例如，例5.3中的（6，3）碼的陪集譯碼表如表5-2所示。表5-2例5.3中的（6，3）碼的陪集譯碼表表5-2中第一列稱為陪集首。通過譯碼表的構造過程可以知道，每個碼字所在列上其他向量都是距離正確碼字距離最小的向量（陪集首的重量最?。?。如果接收到向量出現(xiàn)了錯誤，則將它譯成所在列的碼字（即第一行上的向量）。若接收到向量011101，則譯成010101。5.5.3伴隨式譯碼下面首先引入校驗矩陣的概念。從例5.3中很容易得到：

(5.49)若V=(v5,v4,…,v0)是該(6，3)碼的一個碼字，則V的6個碼元一定滿足式(5.49)的三個方程。反之，若有一個r=(r5,r4,…,r0)不完全滿足式(5.49)中的三個方程，則它一定不是該(6，3)碼的碼字，因此式(5.49)中的三個方程對碼字起監(jiān)督作用，我們稱這三個方程為監(jiān)督方程。若用矩陣表示，則有若令

則H稱為碼的一致監(jiān)督矩陣，簡稱監(jiān)督矩陣。該碼的任一個碼字v都應滿足HvT=0。事實上，監(jiān)督方程也可以用更一般的形式表示，即監(jiān)督方程可以寫成如下形式：若用矩陣表示，即得:或者HvT=0，這里

仍舊稱為該碼的監(jiān)督矩陣，它的r行是線性無關的。從監(jiān)督矩陣的推導過程知道，它的每一行表示求一個監(jiān)督元的監(jiān)督方程，因為每個碼字共有r=n－k個監(jiān)督元，所以任何一個(n,k)線性分組碼的監(jiān)督矩陣H至少有r=n－k行，且有r行是線性無關的。我們知道，線性分組碼的糾錯能力與它的最小距離dmin有著密切的關系，dmin越大,它的糾錯能力越強，因此討論H與dmin的關系就是討論H與碼的糾錯能力的關系。

定理5.7

一個(n，k)線性分組碼的最小距離為dmin

的充分必要條件是它的監(jiān)督矩陣H的任意dmin－1列線性無關，而有dmin列線性相關。證明：先證必要性。如果(n，k)碼的最小距離為dmin，則由分組碼的性質(zhì)可知，最小碼重Wmin=dmin，于是存在一個碼字v=(vn－1,vn－2,…,v0)，它的重量為dmin，即v有d=dmin個碼元不為0，不妨設不為0，其余碼元為0，設碼的監(jiān)督矩陣為H=［αn－1

αn－2

…α0］其中αn－i表示H矩陣的第i個列向量，于是由HvT=0得到

即H中有d=dmin列線性相關。如果H中有dmin－1=d列也線性相關，不妨設

于是存在一個碼字v，它的碼元不為0，其余碼元為0，使即存在一個碼字v，W(v)=d=dmin－1，這與Wmin=dmin矛盾，因此H中任意dmin－1列都線性無關。下面證明充分性。設H中有dmin列線性相關，不妨設不0，使

(5.50)我們令v=(vn－1,vn－2,…,v0)，它的碼元、、…、不為0，其余碼元為0。由式(5.50)知HvT=0，即該(n，k)碼有一個碼字v，重量W(v)=dmin。最后證明碼中沒有重量小于等于dmin－1的碼字。為此設有一個碼字v，它的重量為W(v)=d=dmin－1，不妨設不為0，其余碼元為0，于是

這與H中任意dmin－1列線性無關矛盾。

推論3

當(n，k)碼的最小距離dmin≥2t+1時，它的H矩陣任意t列的線性組合與其他任意t列的線性組合均不相同。設V是(n，k)線性分組碼，v是V中任一個碼字，當發(fā)端發(fā)送v時，收端收到一個r，錯誤圖樣為e=r－v=(en－1,en－2,…,e0)于是定義

(5.51)

從式(5.51)可以看出，sT僅與錯誤圖樣e有關，而與發(fā)送的碼字無關。我們稱s為r或e的伴隨式。s完全由e確定，它在一定程度上反映了信道的干擾情況。譯碼器的主要任務就是如何從s求得錯誤圖樣，從而譯出發(fā)送的碼字v。設一個最小距離dmin=3、糾錯能力t=1的(n，k)碼的監(jiān)督矩陣為當收到的r無錯，即r=v時，e=0，一定有sT=HrT=HeT=0。當接收的r有1位錯時，設錯誤圖樣為e=(00…0ei0…00)，則伴隨式為可見,伴隨式正好是H矩陣的第i列，它是r維列向量。又因為碼的最小距離dmin=3，H矩陣任何兩列都不相同，所以伴隨式與單個錯誤的錯誤圖樣一一對應。如果發(fā)生了兩個錯誤，設錯誤圖樣為e=(00…0ei0…0ej0…0)，則伴隨式為H矩陣的第i列和第j列之和。但是，此時的伴隨式也可能是另外兩列之和（請考慮H矩陣列相關性和最小距離之間的關系），所以此時只能發(fā)現(xiàn)錯誤，但是不能糾正錯誤。糾正單個錯的伴隨式譯碼方法如下：

(1)如果sT=0，則判r無錯，此時v=r：

(2)如果sT≠0，且sT與H矩陣的第i列相同，則判第i位有錯：

(3)如果sT≠0，但不是H的列，則只判r有錯，而不糾錯。糾正多個錯誤的伴隨式譯碼的原理跟單個錯誤情況相同，這里不再贅述。5.5.4分組碼最小距離的邊界在離散二進制對稱信道上，人們在研究分組碼的誤碼率邊界時得出了以下結(jié)論：

(5.52)(5.53)因此,dmin的上、下邊界在評價碼的性能時十分重要。由5.5.3節(jié)可知，分組碼的校驗矩陣H中有dmin列線性相關，而dmin－1列是線性無關的，由于H的秩最多為n－k，則必有n－k≥dmin－1，所以dmin的上界是:dmin≤n－k+1

(5.54)式(5.54)是Singleton給出的最簡單的上邊界，稱為Singleton限。用分組長度n可將此式歸一化，即

式中，Rc是碼率。當n很大時，因子1/n可以忽略。如果某一編碼具有最大的可能距離，即dmin=n－k+1，則這種碼叫做極大最小距離可分碼。除了普通重復型碼外，不存在二進制的極大最小距離可分碼。事實上，式(5.54)規(guī)定的上邊界對二進制碼來說是非常松散的。另一方面，具有dmin=n－k+1的非二進制碼卻是存在的。例如里德-索羅門（ReedSolomon）碼就是極大最小距離可分碼，它屬于BCH碼的子類。除了上述上邊界之外，還有幾個線性分組碼的最小距離較緊的邊界。下面我們將簡述4種重要的邊界，其中三個是上邊界，一個是下邊界。這些邊界的推導冗長，這里不進行詳述，有興趣的讀者請參閱彼得森和韋爾登（1972年）著作的第4章。第一個最小距離的上邊界為

(5.55)由于碼的糾錯能力（用t度量）與最小距離有關，所以上述關系式是最小距離的上邊界，叫做Hamming上邊界或Hamming限。令n→∞，可得到式(5.55)的漸近形式。對于任意n，令t0是使式(5.55)成立的t的最大整數(shù)，可以證明，當n→∞時，任何(n,k)分組碼t/n決不會超過t0/n。這里,t0/n滿足等式:

式中，H(x)是的二進制熵函數(shù)H(x)=－plogp－(1－p)log(1－p)，其中p為0的概率。(5.56)將Hamming界推廣到非二進制碼，即

(5.57)另一個最小距離的上邊界是普洛特金（Plotkin）1960年推出的，后人稱之為Plotkin限。說明如下：在一個(n,k)線性分組碼中，為了達到最小距離dmin，所需的校驗位數(shù)目必須滿足不等式：

(5.58)其中,q是字符集大小。對二進制編碼來說，式(5.58)可表示為

在dmin/n≤1/2而n→∞的極限情況下，式(5.58)簡化為

(5.59)最后一個緊的最小距離上邊界是埃利斯（Elias，1968年）發(fā)現(xiàn)的，以漸近線形式表示為

(5.60)式中,參數(shù)A與碼率有關，兩者之間的關系式為

(5.61)

(n,k)分組碼最小距離的下邊界同樣存在，特別是具有歸一化最小距離的二進制分組碼，它們漸近地滿足不等式:(5.62)式中，α通過下列等式與碼率建立聯(lián)系:

(5.63)這個下邊界是吉爾伯特（Gilbert，1952年）和烏沙莫夫（Varsharmov，1957年）提出的下邊界的一個特例，適用于非二進制和二進制分組碼，簡稱V-G限。上述三個性能限中，前兩個是必要條件，即想讓dmin達到某值，n－k必須大于某值，或者說對于一定冗余度n－k，dmin最大能達到多少，所以Hamming限和Plotkin限給出的是上邊界。V-G限是充分條件，它說明只要滿足這個條件，就一定存在最小距離為dmin的碼，所以V-G限給出的是下邊界。然而，V-G限指出的“存在”并不一定能被找到。如圖5-3所示，斜線區(qū)是可能實現(xiàn)的區(qū)域，雙重斜線區(qū)是必能實現(xiàn)的區(qū)域。圖5-3幾種碼限的比較5.6卷積碼卷積碼convolutionalcode）是1955年由P.Elias提出的一種記憶碼，在二十世紀六七十年代開始廣泛使用。它與分組碼不一樣，不僅是輸入k0位信息碼元的函數(shù)，還是前面m個k0位信息碼元的函數(shù)。卷積碼由n0、k0、m描述，n0為每組輸出碼元數(shù)，k0為每組輸入碼元數(shù)，k0/n0表示卷積碼的編碼效率，m稱為編碼約束度，表示k0組移位寄存器中最大的級數(shù)。由于卷積碼各組之間相互有關，因此在卷積碼的分析過程中，未找到像分組碼那樣有效的數(shù)學工具，性能分析比較困難，從分析上得到的成果不像分組碼那樣多，往往要借助計算機的搜索來尋找好碼。

【例5.5】一個簡單的卷積碼如圖5-4所示。初始狀態(tài)為00。設輸入m=101100…，則輸出與輸入的關系為輸入：1

0

11000狀態(tài)：00

10

01

10

11

01

00輸出：11

01

00

10

10

11

00

圖5-4卷積碼生成器卷積碼的特點如下：（1）當前碼分組輸出不僅與當前信息分組輸入有關，還與前面m個信息分組有關。（2）尚沒有完善的數(shù)學工具有效地分析其結(jié)構和性能，必須借助計算機搜索來尋找好碼。（3）研究表明：卷積碼是漸近好碼，相同碼率、相同譯碼復雜性條件下，卷積碼的性能要好于分組碼。（4）卷積碼仍是線性碼，滿足線性疊加關系。例5.5中的編碼器一共有4個狀態(tài)：00、10、01、11，分別記為：S0、S1、S2、S3，該編碼器的狀態(tài)轉(zhuǎn)移圖如圖5-5所示。卷積碼的狀態(tài)圖只表示編碼狀態(tài)之間的轉(zhuǎn)移關系，無法表示狀態(tài)轉(zhuǎn)移與時間節(jié)拍的關系。為了表示狀態(tài)轉(zhuǎn)移與時間節(jié)拍的關系，引入卷積碼的格圖(TrellisDiagram)表示。卷積碼的格圖也稱為籬笆圖。圖5-5狀態(tài)轉(zhuǎn)移圖從初始狀態(tài)出發(fā)，格圖上的每一條路徑都對應著一個輸入信息序列所對應的編碼序列。給定信息序列，可在格圖上找到一條路徑，進而得到所對應的編碼序列。反過來，給定編碼序列，也可在格圖上找到一條路徑，進而得到所對應的信息序列。例5.5中，(2，1，2)卷積碼將狀態(tài)轉(zhuǎn)移圖按時間節(jié)拍展開，如圖5-6所示。圖5-6(2,1,2)卷積碼的網(wǎng)格圖

Shannon在證明Shannon第二編碼定理時引用了如下3個基本條件：（1）采用隨機性編譯碼。（2）編碼長度趨于無窮，即分組的碼組長度無限。（3）譯碼過程采用最佳的最大似然譯碼（ML）方案。在信道編碼的研究與發(fā)展過程中，基本上以后兩個條件為主要方向，如卷積碼使得碼長變得很長，并采用次最優(yōu)的最大似然譯碼(viterbi算法)。對于條件（1），雖然隨機選擇編碼碼字可以使獲得好碼的概率增大，但是最大似然譯碼器的復雜度隨碼字數(shù)目的增大而加大，當編碼長度很大時，譯碼幾乎不可能實現(xiàn)?？傮w而言，目前各種單一的構造性很強的編譯碼方法其性能都很有限，與信道容量之間的差距是很大的，這也就是為什么信息論發(fā)展半個多世紀以來人們關心的容量仍不是信息論意義上的容量。因此，多年來隨機編碼理論一直作為分析和證明編碼定理的主要方法，而如何在構造碼上發(fā)揮作用卻并未引起人們的足夠重視。直到1993年，Turbo碼的發(fā)現(xiàn)才較好地解決