信道編碼定理錯誤概率譯碼準則信道編碼定理1噪聲信道的編碼問題在二進制數字通信系統中，編碼器的編碼過程分為兩步：信源編碼：把信源的消息數據序列編成二進制數字構成的碼序列；信道編碼：把二進制數據序列編成具有糾檢錯能力的二進制序列。由于信源編碼在構造上并未考慮抗干擾，如果把信源編碼器的輸出直接接入信道，由于信道中存在噪聲干擾，將引起誤碼，降低通信可靠性。因此提出了以提高通信可靠性為主要目的的信道編碼，它是對信源編碼器輸出的最佳碼再進行一次編碼，以提高其抗干擾能力的一種編碼形式。2信道編譯碼的理論基礎信道的特征是由信道傳遞概率p(Y|X)來描述的。由p(Y|X)可以算出信道容量C，只要在信道中實際傳送的信息率R’<C，在接收端就能夠無差錯地譯出發端所輸送的信息。信道輸入符號序列X代表M種信源符號，信源符號也可以是已經經過信源編碼的M種碼字，使從信道輸出符號序列Y能正確地譯出這M種碼字，問題就在于如何用X組成這M種碼字，才能達到無差錯地傳送，這就要編碼。這種編碼實質上是希望信源與信道特性相匹配，所以稱為信道編碼。

3信道編譯碼的基本思想信道編碼的編碼對象是信源編碼器輸出的數字序列M，又稱為信息序列。通常是由二元符號0，1構成的序列，而且符號0和1是獨立等概的。信道編碼，就是按一定的規則給數字序列M增加一些多余的碼元，使不具有規律性的信息序列M變換為具有某種規律性的數字序列C，又稱為碼序列。碼序列中信息序列的諸碼元與多余碼元之間是相關的。在接收端，信道譯碼器利用這種預知的編碼規則來譯碼，或者檢錯(檢驗接收到的數字序列R中是否有錯)，或者糾錯(糾正其中的差錯)。信道編碼的基本思想是就是根據相關性來檢測和糾正傳輸過程中產生的差錯。4通信的可靠性問題通信的可靠性問題，即消息通過信道傳輸時如何選擇編碼方案以減少差錯。首先，通信的可靠性顯然與信道的統計特性有關，因為雜噪干擾是造成錯誤的主要因素。其次，編碼方法和譯碼方法也將影響信息傳輸的可靠性。在有噪信道中傳輸信息是會發生錯誤的，錯誤概率和信道統計特性、編譯碼過程以及譯碼規則有關。5編碼信道的概念信道編碼研究的對象是編碼信道，如上圖所示，它是由信道編碼器、信道譯碼器和實際信道一起形成的一個新的信道。編碼信道是研究信道糾錯編碼和譯碼的一種模型。它可以是：無線通信中的如發射機、天線、自由空間、接收機等全體；有線通信中的如調制解調器、電纜等全體；互聯網的多個路由器、節點、電纜、低層協議等全體；計算機的存儲器如磁盤等的全體；……。接收向量

Y碼字X編碼信道信源編碼信源譯碼消息m消息m’6錯誤概率和譯碼規則考慮一個二元對稱信道，單符號錯誤傳遞概率是pb=0.9，其輸入符號為等概率分布。如果規定在信道輸出端接收到符號0時，譯碼器把它譯成0；接收到1時譯成1，那么譯碼錯誤概率為0.9。反之，如果規定在接收到符號0時譯成1；接收到1時譯成0，則譯碼錯誤概率為0.1。可見，錯誤概率既與信道統計特性有關，也與譯碼規則有關。00111-pb1-pbpbpb二元對稱信道7無記憶二進制對稱信道（BSC）假定數字通信系統的編碼信道是無記憶二進制對稱信道：二進制信道是指碼字和接收向量均由二元序列表示的信道，即c=(c0,c1,…,cn-1)ci{0,1}、

r=(r0,r1,…,rn-1)ri{0,1}。二進制信道可用轉移概率p(r/c)描述輸入輸出關系；滿足以下公式的二進制信道稱為無記憶二進制信道：

p(r/c)=p(ri

/ci

)i=0…n-1滿足以下對稱特性的無記憶二進制信道稱為無記憶二進制對稱信道，簡稱BSC：p(0/1)=

p(1/0)=pb接收向量rri{0,1}

碼字cci{0,1}二進制信道p(r/c)信源編碼信源譯碼消息m消息m’8BSC的信道模型只要噪聲是白噪聲，大多數二進制傳輸信道的模型可等效為一個BSC，其信道模型如下圖所示。+cer二進制無記憶00111-pb1-pbpbpbBSC轉移概率BSC編碼信道9可將BSC的輸入輸出關系等效為代數關系：r=c+emod2e=(e0,e1,…,en-1)差錯圖案：隨機序列(ei)隨機錯誤：ei

=1,i位突發錯誤：第i至第j位之間有很多錯誤。BSC的輸入輸出關系描述+cer10譯碼規則譯碼規則的定義11譯碼規則-例設有一離散無記憶信道，其信道矩陣為則以下A和B是兩個不同的譯碼規則：由于n=3，m=3，m個輸出符號中的每一個都可以譯成n個輸入符號中的任何一個，故按此信道矩陣總共可設計出33=27種譯碼規則。在所有的譯碼規則中，不是每一種譯碼規則都是合理的，因此要討論選擇譯碼規則的準則，這些準則總的原則是使譯碼平均錯誤概率最小。

121、譯碼平均錯誤概率若譯碼規則為，則信道輸出端接收到符號yj時，一定譯成xi。如果發送端發的就是xi，這就是正確譯碼，因此條件正確概率為反之，如果發送端發的是，則是錯誤譯碼，因此條件錯誤概率為

經過譯碼后，平均到一個符號所產生的錯誤的大小，也就是譯碼平均錯誤概率為

13譯碼平均錯誤概率的其它表達式譯碼平均錯誤概率還可以寫成若用條件概率表示，則可以寫成平均正確概率則可以寫成

14等概率分布時的譯碼平均錯誤概率若輸入為等概率分布，則上式意味著，在輸入為等概率分布的條件下，譯碼錯誤概率可用信道矩陣中元素的求和來求。這種求和是除去信道矩陣中每列中對應于的那一項后，求矩陣中其余元素之和。

152、譯碼規則選擇譯碼規則總的原則應是使譯碼平均錯誤概率pE最小。

譯碼平均錯誤概率

為非負項之和，欲使譯碼平均錯誤概率最小，那么應使每一項為最小。由于p(yj)

與譯碼規則無關，故欲使譯碼平均錯誤概率最小，即為使最小，或者使為最大，于是引出最大后驗概率準則。

16最大后驗概率譯碼準則-定義17最大后驗概率準則-例題18最大后驗概率準則-例題（續）19后驗概率與最大似然-譯碼準則從最大后驗概率譯碼規則可以很容易推出極大似然譯碼規則。20最大似然譯碼準則-定義

當信道輸入符號為等概分布時，應用極大似然譯碼準則是很方便的，即將yj譯成信道矩陣中第j列最大的那個元素。式中的條件概率即為信道矩陣中的元素。21最大似然譯碼準則-例題當輸入為等概率分布時，譯碼規則A就是依據最大似然譯碼準則而得的。22最大似然譯碼準則-例題（續）輸入為等概率分布時，兩種譯碼規則所對應的平均錯誤概率分別為

在輸入為等概率分布時，最大似然譯碼準則是最優的。23費諾不等式譯碼時發生錯誤是由信道中噪聲引起，因此平均錯誤概率與信道疑義度H(X|Y)有關，其關系由費諾不等式表示。引理6.1.1譯碼平均錯誤概率與信道疑義度H(X|Y)間滿足以下關系這個不等式稱為費諾不等式。

24費諾不等式的物理意義雖然PE與譯碼規則有關，但不管采用什么譯碼規則費諾不等式均成立。費諾不等式表示，當作了一次譯碼判決后所保留的關于信元的不確定性可以分成兩部分：H(PE)和PE

log(n-1)。第二部分是當判決是錯誤的，其錯誤概率為PE

時，到底是n-1個輸入符號中哪一個引起錯誤的最大不確定性，它是(n-1)個符號不確定性的最大值log(n-1)與PE

的乘積。

第一部分是接收到Y后，判決是否發生錯誤的不確定性H(PE)，其中H(PE

)是譯碼平均錯誤概率PE

的熵，表示產生錯誤概率PE

的不確定性。25費諾不等式的幾何含義信道疑義度是信源熵H(X)超過平均互信息I(X;Y)的部分。若以H(X|Y)為縱坐標，PE為橫坐標，則函數H(PE)+PE

log(n-1)隨PE變化的曲線如圖所示。由圖可知，當信源、信道給定時，信道疑義度H(X|Y)就給定了譯碼平均錯誤概率PE的下限。

26錯誤概率與編碼方法

前面討論了平均錯誤概率與譯碼規則的關系。選擇最佳譯碼規則只能使錯誤概率有限地減小，無法使其任意地小。要想進一步減小錯誤概率，必須優選信道編碼方法。現在討論不同的編碼方法對譯碼平均錯誤概率和信息傳輸率的影響。

27錯誤概率與編碼方法1簡單重復編碼2消息符號個數3（5,2）線性碼4漢明距離281簡單重復編碼與錯誤概率

本節舉例說明在采用簡單重復編碼時重復次數對譯碼平均錯誤概率和信息傳輸率的影響。設有二元對稱信道如圖其信道矩陣為未編碼時：選擇最佳譯碼規則為

在輸入為等概率分布時，譯碼平均錯誤概率為29簡單重復編碼舉例（續1）采用簡單重復編碼，規定信源符號為0（或1）時重復發送三個0（或1）。輸入符號和輸出符號的關系如圖：

30簡單重復編碼舉例（續2）31簡單重復編碼舉例（續3）在簡單重復編碼時，采用“擇多譯碼”的譯碼規則等效于最大似然譯碼準則。擇多譯碼是根據接收序列中“0”和“1”的個數，如果是“0”多，則譯碼器就判決為“0”，如果是“1”多，就判決為“1”。采用簡單重復編碼方法，如果增大重復次數n，則會降低譯碼平均錯誤概率，但信息傳輸率也要減小。信息傳輸率表示平均每個碼符號所攜帶的信息量，其中M為消息符號個數。32簡單重復編碼舉例（續4）重復次數對信息傳輸率和錯誤概率的影響如下能否找到一種編碼方法，使平均錯誤概率充分小，而信息傳輸率R’又可以保持在一定水平上，這就是香農第二定理所要回答的問題。

332消息符號個數M本節討論消息符號個數M對錯誤概率和信息傳輸率的影響。在一個二元信道的n次無記憶擴展信道中，輸入端共有2n個符號序列可能作為消息符號，現僅選其中M個作為消息符號傳遞。

34消息符號個數M的影響（續1）設n=3，那么可供選擇的消息符號數共有8個，發送端只選擇其中M個作為輸入消息符號傳遞，而接收端會接收到所有8個輸出符號，然后從中譯出M個消息符號。

以下假設輸入為等概率分布p(x)=1/M，信道錯誤傳遞概率p=0.01，采用簡單重復編碼和最大似然譯碼準則。當n=3，M=2時，有：

35消息符號個數M的影響（續2）當n=3，M=4時，有比特/碼符號

M=4有不同的選取方法，代表不同的編碼方法，其平均錯誤概率是不同的。

36結論：輸入信息符號個數M增大時，平均錯誤概率顯然是增大了，但信息傳輸率也增大了。反之，亦然。

輸入信息符號個數M不變時，即信息傳輸率不變時，不同的編碼方法，其平均錯誤概率是不同的。

37錯誤概率與編碼方法1簡單重復編碼2消息符號個數3（5,2）線性碼4漢明距離383（5，2）線性碼從以上討論看出：增大簡單重復編碼次數n，雖然使平均錯誤概率pE下降，但信息傳輸率R’也降低了。增大輸入消息符號個數M，盡管可使信息傳輸率R’增大，但又增大了平均錯誤概率pE。當采用好的編碼方法時，可以使平均錯誤概率pE和信息傳輸率R’兩個指標得到較好的折衷。39（5，2）線性碼的編碼設M=4，n=5則輸入符號有M=4種，由的4個不同取值決定。采用以下編碼方法將輸入符號編碼成為5位碼：40（5,2）線性碼的編碼（續）由上述編碼方法得到一種(5,2)線性碼，如圖所示:41（5,2）線性碼的譯碼效果采用最大似然譯碼準則，當p=0.01時正確譯碼概率為平均錯誤譯碼概率為信息傳輸率為前述n=3，M=4的一種簡單重復編碼平均錯誤譯碼概率為信息傳輸率為42結論與n=3，M=4的簡單重復編碼比較，（5,2）線性碼的信息傳輸率R’略有降低，但平均錯誤概率卻好得多。說明好的編碼方法可以在錯誤概率和信息傳輸率兩個性能上達到最佳折衷。43離散信道編碼定理信道編碼定理是一個理想編碼的存在性定理。信道容量是一個臨界值，信息傳輸率不超過這個值，信道就可幾乎無失真地把信息傳過去，否則就會產生失真。44糾錯碼分類

檢糾錯碼的種類繁多，其分類也有多種方式，主要依據使用的信道、糾錯類型和碼的數學結構分類。以下首先簡要介紹干擾類型和對應的信道類型、檢糾錯工作方式，再介紹檢糾錯碼的不同分類方法。45干擾類型信道中的干擾一般分為兩種形式：隨機噪聲，它主要來源于設備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統中的主要噪聲；脈沖干擾，它的特點是突發出現，主要來源于雷電、通電開關、負荷突變或設備故障等。46檢糾錯的工作方式

反饋重傳糾錯當發現有錯時，通過反饋系統向發出端發出詢問信號要求重新發送。發送端收到信號后，重發已發生錯誤的那部分信息，直至接收端認為無錯誤為止。前向糾錯當在傳輸中出現差錯，且錯誤個數在碼的糾錯能力范圍內時，系統的接收端根據編碼規則進行解碼，并自動糾正錯誤。這種糾錯方式不需要反饋，故稱其為前向糾錯。混合糾錯當錯誤在碼的糾錯能力之內時，采用自動糾錯。當超出碼的糾錯能力，且能發現錯誤，則發出詢問信號，反饋到發送端要求重發。47線性碼和非線性碼根據碼的數學結構，可以有不同的分類。按校驗元與信息元的關系，可分為線性碼和非線性碼。線性碼的校檢位是若干信息位的線性組合，而非線性碼的校檢位與信息位不滿足線性關系。線性碼的編譯碼都優于相同糾錯能力的非線性碼。48分組碼和卷積碼按對信息序列處理方式分類，可分為分組碼和卷積碼分組碼:對于某組碼字，其信息序列劃分為一組k位碼元，將其編成n（n>k）位的碼字。重點討論線性分組碼。根據分組碼的結構，又可分為循環碼和非循環碼。卷積碼:是將整個信息序列編成一個碼序列，碼與碼之間相互影響，不能分開。卷積碼又稱為樹碼或鏈碼。494漢明距離

定義：設為兩個n長的二元碼字，則碼字X和Y之間的漢明距離為其中，代表模二和運算。上式的含義是，兩個碼字之間的漢明距離就是它們在相同位上不同碼符號的數目的總和。

舉例：設X=(101111)，Y=(111100)，則D(X,Y)=350漢明距離滿足的性質1、非負性D(X,Y)≥0當且僅當X=Y式等號成立。2、對稱性D(X,Y)=D(Y,X)3、三角不等式D(X,Z)+D(Y,Z)≥D(X,Y)51最小碼距Dmin定義：在二元碼C中，任意兩個碼字的漢明距離的最小值，稱為碼C的最小碼距，即舉例：設有n=3的兩組碼對于碼C1有對于碼C2有52最小碼距對錯誤概率的影響顯然，最小碼距Dmin越大，則平均錯誤概率pE越小。碼本中最小碼距Dmin越大，受干擾后，越不容易把一個碼字錯譯成另一個碼字，因而平均錯誤概率pE小。如果碼本中最小碼距Dmin小，受干擾后很容易把一個碼字錯譯成另一個碼字，因而平均錯誤概率pE大。因此，在選擇編碼規則時，應使碼字之間的距離Dmin越大越好，這樣的準則即為最小