第6信道編碼定理課件

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

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

…

…。接收向量

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

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

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

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

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

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

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

經(jīng)過譯碼后，平均到一個符號所產(chǎn)生的錯誤的大小，也就是譯碼平均錯誤概率為

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

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

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

由于譯碼平均錯誤概率

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

與譯碼規(guī)則無關(guān)，故欲使譯碼平均錯誤概率最小，即為使最小，或者使為最大，于是引出最大后驗(yàn)概率準(zhǔn)則。

16最大后驗(yàn)概率譯碼準(zhǔn)則-定義17最大后驗(yàn)概率準(zhǔn)則-例題18最大后驗(yàn)概率準(zhǔn)則-例題（續(xù)）19后驗(yàn)概率與最大似然-譯碼準(zhǔn)則從最大后驗(yàn)概率譯碼規(guī)則可以很容易推出極大似然譯碼規(guī)則。20最大似然譯碼準(zhǔn)則-定義

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

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

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

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

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

的乘積。

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

)是譯碼平均錯誤概率PE

的熵，表示產(chǎn)生錯誤概率PE

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

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

26小結(jié)本節(jié)圍繞信道編碼的主要性能參數(shù)－譯碼平均錯誤概率進(jìn)行討論：給出了譯碼平均錯誤概率的定義與公式。依據(jù)錯誤概率最小化的原則，給出了兩種譯碼準(zhǔn)則：最大后驗(yàn)概率譯碼準(zhǔn)則是最佳準(zhǔn)則，總能使錯誤概率最小化。最大似然譯碼準(zhǔn)則是次最佳準(zhǔn)則，在輸入等概率分布時與最大后驗(yàn)概率準(zhǔn)則等效。應(yīng)用最大似然譯碼準(zhǔn)則時，只需根據(jù)信道矩陣進(jìn)行判斷，應(yīng)用很方便，因而成為最常用的準(zhǔn)則。給出了錯誤概率與信道疑義度的關(guān)系－費(fèi)諾不等式。27錯誤概率與編碼方法

前面討論了平均錯誤概率與譯碼規(guī)則的關(guān)系。選擇最佳譯碼規(guī)則只能使錯誤概率有限地減小，無法使其任意地小。要想進(jìn)一步減小錯誤概率，必須優(yōu)選信道編碼方法?，F(xiàn)在討論不同的編碼方法對譯碼平均錯誤概率和信息傳輸率的影響。

28錯誤概率與編碼方法1簡單重復(fù)編碼2消息符號個數(shù)3（5,2）線性碼4漢明距離291簡單重復(fù)編碼與錯誤概率

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

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

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

34錯誤概率與編碼方法1簡單重復(fù)編碼2消息符號個數(shù)3（5,2）線性碼4漢明距離352消息符號個數(shù)M本節(jié)討論消息符號個數(shù)M對錯誤概率和信息傳輸率的影響。在一個二元信道的n次無記憶擴(kuò)展信道中，輸入端共有2n個符號序列可能作為消息符號，現(xiàn)僅選其中M個作為消息符號傳遞，見圖。

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

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

37消息符號個數(shù)M的影響（續(xù)2）當(dāng)n=3，M=4時，有比特/碼符號

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

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

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

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

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

舉例：設(shè)X=(101111)，Y=(111100)，則D(X,Y)=348漢明距離滿足的性質(zhì)1、非負(fù)性D(X,Y)≥0當(dāng)且僅當(dāng)X=Y式等號成立。2、對稱性D(X,Y)=D(Y,X)3、三角不等式D(X,Z)+D(Y,Z)≥D(X,Y)49最小碼距Dmin定義：在二元碼C中，任意兩個碼字的漢明距離的最小值，稱為碼C的最小碼距，即舉例：設(shè)有n=3的兩組碼對于碼C1有對于碼C2有5