第5章有噪信道編碼

第5章有噪信道編碼

前一章已經(jīng)從理論上討論了在無(wú)噪無(wú)損信道上，只要對(duì)信源進(jìn)行適當(dāng)?shù)木幋a,總能以最大信息傳輸率C（信道容量）無(wú)差錯(cuò)的傳輸信息。但是一般信道總存在噪聲或干擾,信息傳輸會(huì)造成損失，那么在有噪信道中怎么能使消息通過(guò)傳輸后發(fā)生的錯(cuò)誤最少？在有噪信道中無(wú)錯(cuò)誤傳輸?shù)目蛇_(dá)的最大信息傳輸率是多少？這就是本章所要研究的問(wèn)題，即研究通信的可靠性問(wèn)題。第5章有噪信道編碼

內(nèi)容提要本章介紹了信道編碼和譯碼的基本概念，介紹了兩種常用的譯碼準(zhǔn)則：最大后驗(yàn)概率譯碼準(zhǔn)則和極大似然譯碼準(zhǔn)則,還介紹了在這兩種譯碼準(zhǔn)則下錯(cuò)誤概率的計(jì)算方法。本章還介紹了信道編碼定理以及信息論中的一個(gè)重要不等式Fano不等式。5．1信道編碼的基本概念

將信道用圖5-1所示的模型表示。信道編碼器信道信道譯碼器uxy圖5-1信道模型

信源輸出序列u，經(jīng)信道編碼器編成碼字x=f(u)并輸入信道，由于干擾，信道輸出y，信道譯碼器對(duì)y估值得

=F(y)。

信源編碼以提高傳輸效率作為主要考慮因素，信道編碼以提高傳輸可靠性作為主要考慮因素。這一章討論信道編碼的一些基本概念及信道編碼定理?！纠拷o定二元對(duì)稱(chēng)信道，信道固有錯(cuò)誤概率為p（p<0.5）編碼規(guī)則：為提高可靠性，每個(gè)信道符號(hào)重復(fù)三次發(fā)送。

譯碼規(guī)則：擇多譯碼，即信宿方收到的三個(gè)符號(hào)中有兩個(gè)或三個(gè)為1，就將此次接收符號(hào)判決為1；若三個(gè)符號(hào)中有兩個(gè)或三個(gè)為0，就將此次接收符號(hào)判決為0。

下面為重復(fù)編碼傳輸示意圖，計(jì)算錯(cuò)誤概率pe。書(shū)上例題5.1信源輸出序列為：

信道輸入序列為：

由于p的存在，使得傳輸出錯(cuò)，故信道輸出為：

根據(jù)譯碼規(guī)則，信道估值輸出：

信道錯(cuò)誤概率：假設(shè)信道離散無(wú)記憶，即

錯(cuò)誤概率為：

重復(fù)編碼的結(jié)果使錯(cuò)誤概率下降。

書(shū)5-1式有問(wèn)題書(shū)上例題5.2【例5.3】逆重復(fù)碼離散無(wú)記憶二進(jìn)制對(duì)稱(chēng)信道，固有誤碼率為p(p<0.5)，信源輸出序列為三位二進(jìn)制數(shù)字。編碼規(guī)則：為提高傳輸效率，僅向信道發(fā)送一位，預(yù)先將信源輸出序列進(jìn)行擇多編碼:圖5-3逆重復(fù)編碼傳輸示意圖

譯碼規(guī)則：將接收的一位符號(hào)重復(fù)三次譯出，即若接收到1就譯碼為111，即若接收到0就譯碼為000。信源輸出的三位符號(hào)中有兩位或3位是1，信源序列編碼為1，若三位符號(hào)中有兩位或3位是0，就將此信源序列編碼為0。1-p0

p

1011-p

p

計(jì)算差錯(cuò)概率pe：分二步進(jìn)行：（1）先設(shè)p=0，計(jì)算這種編碼方法帶來(lái)的固有錯(cuò)誤p1信道輸入符號(hào)集X={000,001,010,011,100,101,110,111}判決輸出符號(hào)集Y={000,111}譯碼規(guī)則因?yàn)楹篁?yàn)概率則出錯(cuò)概率

假設(shè)8組輸入序列是等概發(fā)送的，由于信道的對(duì)稱(chēng)性，兩個(gè)估值序列也是等概分布的，則每個(gè)序列的平均錯(cuò)誤概率為，誤比特率。（2）再設(shè)p≠0，計(jì)算由于信道噪聲引起的錯(cuò)誤概率p2因?yàn)槊總€(gè)序列有三位二進(jìn)制數(shù)字，但只發(fā)送一位，這一位的出錯(cuò)概率為p，故序列差錯(cuò)概率為p，誤比特率。（3）總差錯(cuò)概率（誤比特率）：

【例5.4】奇偶校驗(yàn)碼在信息序列后面加上一位校驗(yàn)位，使之模2和等于1，這樣的編碼稱(chēng)為奇校驗(yàn)碼；若使模2和等于0，這樣的編碼就稱(chēng)為偶校驗(yàn)碼，即每個(gè)碼矢中1的個(gè)數(shù)固定為奇數(shù)或偶數(shù)。關(guān)于奇偶校驗(yàn)

奇偶校驗(yàn)原理：通過(guò)計(jì)算數(shù)據(jù)中“1”的個(gè)數(shù)是奇數(shù)還是偶數(shù)來(lái)判斷數(shù)據(jù)的正確性。在被校驗(yàn)的數(shù)據(jù)后加一位校驗(yàn)位或校驗(yàn)字符用作校驗(yàn)碼實(shí)現(xiàn)校驗(yàn)。校驗(yàn)位的生成方法奇校驗(yàn)：確保整個(gè)被傳輸?shù)臄?shù)據(jù)中“1”的個(gè)數(shù)是奇數(shù)個(gè)，即載荷數(shù)據(jù)中“1”的個(gè)數(shù)是奇數(shù)個(gè)時(shí)校驗(yàn)位填“0”，否則填“1”；偶校驗(yàn)：確保整個(gè)被傳輸?shù)臄?shù)據(jù)中“1”的個(gè)數(shù)是偶數(shù)個(gè)，即載荷數(shù)據(jù)中“1”的個(gè)數(shù)是奇數(shù)個(gè)時(shí)校驗(yàn)位填“1”，否則填“0”。

使用奇偶校驗(yàn)碼校驗(yàn)的特點(diǎn)：奇偶校驗(yàn)?zāi)軌驒z測(cè)出信息傳輸過(guò)程中的部分誤碼（1位誤碼能檢出，2位及2位以上誤碼不能檢出），同時(shí)，它不能糾錯(cuò)。在發(fā)現(xiàn)錯(cuò)誤后，只能要求重發(fā)。但由于其實(shí)現(xiàn)簡(jiǎn)單，仍得到了廣泛使用。校驗(yàn)處理過(guò)程簡(jiǎn)單，但如果數(shù)據(jù)中發(fā)生多位數(shù)據(jù)錯(cuò)誤就可能檢測(cè)不出來(lái)，更檢測(cè)不到錯(cuò)誤發(fā)生在哪一位；主要應(yīng)用于低速數(shù)字通信系統(tǒng)中，一般異步傳輸模式選用偶校驗(yàn)，同步傳輸模式選用奇校驗(yàn)。信道編碼的目的：提高傳輸可靠性。有噪信道編碼定理，即香農(nóng)第二定理，是信道編碼的理論基礎(chǔ)。本章重點(diǎn)介紹通過(guò)信道編碼通信系統(tǒng)所能達(dá)到的極限性能，不涉及編碼技術(shù)的具體實(shí)現(xiàn)，以及兩種常用的譯碼準(zhǔn)則。信道編碼就是按一定的規(guī)則給信源輸出序列增加某些冗余符號(hào)，使其變成滿(mǎn)足一定數(shù)學(xué)規(guī)律的碼序列（或碼字），再經(jīng)信道進(jìn)行傳輸。（具有糾錯(cuò)能力）信道譯碼就是按與編碼器同樣的數(shù)學(xué)規(guī)律去掉接收序列中的冗余符號(hào)，恢復(fù)信源消息序列。傳輸信道插入冗余信息抽出冗余信息編碼譯碼還原序列發(fā)送序列編碼譯碼發(fā)送序列還原序列傳輸信道插入冗余信息抽出冗余信息編碼譯碼第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則第5.2節(jié)錯(cuò)誤概率與編碼方法第5.3節(jié)有噪信道編碼定理主要內(nèi)容

前一章已經(jīng)從理論上討論了,對(duì)于無(wú)噪無(wú)損信道只要對(duì)信源進(jìn)行適當(dāng)?shù)木幋a,總能以信道容量無(wú)差錯(cuò)的傳遞信息。

但是一般信道總會(huì)存在噪聲和干擾,那么在有噪信道中進(jìn)行無(wú)錯(cuò)傳輸可以達(dá)到的最大信息傳輸率是多少呢？這就是本章所要討論的問(wèn)題。

本章的核心是香農(nóng)第二定理。第五章有噪信道編碼第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則

有噪信道傳輸消息是會(huì)發(fā)生錯(cuò)誤的.為了減少錯(cuò)誤,提高通信可靠性,就必須1)分析錯(cuò)誤概率與哪些因素有關(guān);2)有沒(méi)有辦法控制,如何控制;3)能控制到什么程度等問(wèn)題.

前邊已經(jīng)討論過(guò),錯(cuò)誤概率與信道的統(tǒng)計(jì)特性有關(guān),但并不是唯一相關(guān)的因素,譯碼方法的選擇也會(huì)影響錯(cuò)誤率。信道統(tǒng)計(jì)特性信道統(tǒng)計(jì)特性用信道傳遞矩陣來(lái)描述,該矩陣確定了哪些是正確傳遞概率,哪些是錯(cuò)誤傳遞概率.

譯碼規(guī)則通信過(guò)程并非到信道輸出端就結(jié)束,還要經(jīng)過(guò)譯碼過(guò)程(或判決過(guò)程)才到達(dá)消息的終端(收信者).第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則例:有一個(gè)BSC信道,如右圖01011/31/32/32/3若收到“0”譯作“0”,收到“1”譯作“1”,則平均錯(cuò)誤概率為:反之,若收到“0”譯作“1”,收到“1”譯作“0”,則平均錯(cuò)誤概率為1/3.可見(jiàn),錯(cuò)誤概率與譯碼準(zhǔn)則有關(guān).第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則極端的例子---書(shū)P103，圖5.4-強(qiáng)噪信道譯碼規(guī)則定義譯碼規(guī)則:輸入符號(hào)集:A={ai},i=1,2,…,r;輸出符號(hào)集:B={bj},j=1,2,…,s;譯碼規(guī)則:設(shè)計(jì)函數(shù)F(bj),它對(duì)于每個(gè)輸出符號(hào)bj確定一個(gè)唯一的輸入符號(hào)ai與其對(duì)應(yīng)(單值函數(shù)).即F(bj)=ai譯碼規(guī)則的選擇依據(jù)由于任何輸出符號(hào)bj都可以譯成任何輸入符號(hào)ai,即s個(gè)輸出符號(hào)中的每一個(gè)都可以譯成r個(gè)輸入符號(hào)中的任一個(gè)，所以有rs種譯碼規(guī)則.譯碼規(guī)則的選擇應(yīng)該根據(jù)什么準(zhǔn)則？譯碼規(guī)則的選擇依據(jù):使平均錯(cuò)誤概率最小.譯碼準(zhǔn)則可以為:A:和B:例5.1:有一離散單符號(hào)信道，信道矩陣為平均錯(cuò)誤概率有了譯碼規(guī)則F(bj)=ai以后,條件正確概率:收到bj譯碼為ai的概率p[F(bj)|bj]=p(ai|bj)條件錯(cuò)誤概率:收bj后推測(cè)發(fā)出除ai之外符號(hào)的概率p(e|bj)=1-p(ai|bj)=1-p[F(bj)|bj]平均錯(cuò)誤譯碼概率:最小錯(cuò)誤概率譯碼準(zhǔn)則問(wèn)題:如何選擇p(ai|bj)?使p(e|bj)最小,就應(yīng)選擇p[F(bj)|bj]為最大,即選擇譯碼函數(shù)F(bj)=a*，并使之滿(mǎn)足條件:p(a*|bj)≥p(ai|bj)ai≠a*

如果采用這樣一種譯碼函數(shù)，它對(duì)于每一個(gè)輸出符號(hào)均譯成具有最大后驗(yàn)概率的那個(gè)輸入符號(hào)，則信道錯(cuò)誤概率就能最??；即收到符號(hào)bj以后譯成具有最大后驗(yàn)概率的輸入符號(hào)a*.該譯碼準(zhǔn)則稱(chēng)為“最大后驗(yàn)概率譯碼準(zhǔn)則(MAP，MaximumaPosteriori)

”或“最小錯(cuò)誤概率譯碼準(zhǔn)則”.也叫最大聯(lián)合概率譯碼準(zhǔn)則。對(duì)每個(gè)輸出符號(hào)均譯成具有最大后驗(yàn)概率的那個(gè)輸入符號(hào)，則信道錯(cuò)誤概率就能最小。

（1）聯(lián)合概率其中稱(chēng)為前向概率，描述信道的噪聲特性有時(shí)也把稱(chēng)為先驗(yàn)概率，把稱(chēng)為后驗(yàn)概率（2）輸出符號(hào)的概率（3）后驗(yàn)概率表明輸出端收到任一符號(hào)，必定是輸入端某一符號(hào)輸入所致我們一般已知信道傳遞概率p(bj|ai)與輸入符號(hào)先驗(yàn)概率p(ai),所以根據(jù)貝葉斯定律,上式也可以寫(xiě)成一般p(bj)≠0.這樣最大后驗(yàn)概率準(zhǔn)則就表示為:選擇譯碼函數(shù)F(bj)=a*, 使?jié)M足p(bj|a*)p(a*)≥p(bj|ai)p(ai),也即p(a*bj)≥p(aibj).—最大聯(lián)合概率譯碼準(zhǔn)則p(a*|bj)≥p(ai|bj)等效于最大聯(lián)合概率譯碼準(zhǔn)則最大似然譯碼準(zhǔn)則(maximumlikelihoodML準(zhǔn)則)

前面介紹的最大后驗(yàn)概率譯碼準(zhǔn)則等同于最小傳輸錯(cuò)誤概率準(zhǔn)則，從錯(cuò)誤概率最小角度，該譯碼準(zhǔn)則是最好的。

在實(shí)際應(yīng)用中，通常用同一信道去傳輸各種不同的信源，只知道信道的轉(zhuǎn)移概率，而不知道信源的分布，故無(wú)法計(jì)算全概率，故無(wú)法采用最大后驗(yàn)概率譯碼準(zhǔn)則進(jìn)行譯碼。

如果輸入符號(hào)等概發(fā)生,則選擇譯碼函數(shù)F(bj)=a*,并滿(mǎn)足p(bj|a*)≥p(bj|ai) 該譯碼規(guī)則稱(chēng)為:最大似然譯碼準(zhǔn)則.該準(zhǔn)則表示收到bj后,在信道矩陣的第j列,選擇最大的值對(duì)應(yīng)輸入符號(hào)a*作為譯碼輸出.平均錯(cuò)誤概率

根據(jù)譯碼規(guī)則,可進(jìn)一步寫(xiě)出平均錯(cuò)誤概率PE,即而平均正確概率為平均錯(cuò)誤概率也可寫(xiě)成:如果先驗(yàn)概率p(ai)相等,則:平均錯(cuò)誤概率先對(duì)行求和，除去譯碼規(guī)則中所對(duì)應(yīng)的概率，然后是各行之和幾點(diǎn)說(shuō)明1）當(dāng)輸入符號(hào)等概時(shí)，最大似然準(zhǔn)則等價(jià)于最大后驗(yàn)概率準(zhǔn)則。2）該準(zhǔn)則可直接從信道傳遞矩陣中選定譯碼函數(shù)，即收到bj后，譯成信道矩陣p中第j列中最大那個(gè)元素所對(duì)應(yīng)的信源符號(hào)。3）該準(zhǔn)則本身不再依賴(lài)于先驗(yàn)概率p(ai)，但當(dāng)輸入符號(hào)等概時(shí)，它使平均錯(cuò)誤概率PE最小。4）當(dāng)輸入符號(hào)等概或先驗(yàn)概率未知時(shí)，采用此準(zhǔn)則。復(fù)習(xí)和捋順關(guān)系信道編碼就是按一定的規(guī)則給信源輸出序列增加某些冗余符號(hào)，使其變成滿(mǎn)足一定數(shù)學(xué)規(guī)律的碼序列（或碼字），再經(jīng)信道進(jìn)行傳輸。（具有糾錯(cuò)能力）信道譯碼就是按與編碼器同樣的數(shù)學(xué)規(guī)律去掉接收序列中的冗余符號(hào)，恢復(fù)信源消息序列。平均錯(cuò)誤概率與兩個(gè)因素有關(guān)1、信道的統(tǒng)計(jì)特性（傳遞矩陣）2、譯碼規(guī)則主要內(nèi)容和捋順關(guān)系：一、譯碼規(guī)則；二、如何選擇譯碼規(guī)則；三、兩種譯碼準(zhǔn)則-最大后驗(yàn)概率譯碼準(zhǔn)則四、兩種譯碼準(zhǔn)則-最大似然譯碼準(zhǔn)則一、譯碼規(guī)則；定義譯碼規(guī)則:輸入符號(hào)集:A={ai},i=1,2,…,r;輸出符號(hào)集:B={bj},j=1,2,…,s;譯碼規(guī)則:設(shè)計(jì)函數(shù)F(bj),它對(duì)于每個(gè)輸出符號(hào)bj確定一個(gè)唯一的輸入符號(hào)ai與其對(duì)應(yīng)(單值函數(shù)).即F(bj)=ai由于任何輸出符號(hào)bj都可以譯成任何輸入符號(hào)ai,即s個(gè)輸出符號(hào)中的每一個(gè)都可以譯成r個(gè)輸入符號(hào)中的任一個(gè)，所以有rs種譯碼規(guī)則.譯碼準(zhǔn)則可以為:A:和B:例5.1:有一離散單符號(hào)信道，信道矩陣為二、如何選擇譯碼規(guī)則；譯碼規(guī)則的選擇應(yīng)該根據(jù)什么準(zhǔn)則？譯碼規(guī)則的選擇依據(jù):使平均錯(cuò)誤概率最小.平均錯(cuò)誤概率如何計(jì)算？平均錯(cuò)誤概率有了譯碼規(guī)則F(bj)=ai以后,條件正確概率:收到bj譯碼為ai的概率p[F(bj)|bj]=p(ai|bj)條件錯(cuò)誤概率:收bj后推測(cè)發(fā)出除ai之外符號(hào)的概率p(e|bj)=1-p(ai|bj)=1-p[F(bj)|bj]平均錯(cuò)誤譯碼概率:三、兩種譯碼準(zhǔn)則-最大后驗(yàn)概率譯碼準(zhǔn)則最小錯(cuò)誤概率譯碼準(zhǔn)則問(wèn)題:如何選擇p(ai|bj)?使p(e|bj)最小,就應(yīng)選擇p[F(bj)|bj]為最大,即選擇譯碼函數(shù)F(bj)=a*，并使之滿(mǎn)足條件:p(a*|bj)≥p(ai|bj)ai≠a*

如果采用這樣一種譯碼函數(shù)，它對(duì)于每一個(gè)輸出符號(hào)均譯成具有最大后驗(yàn)概率的那個(gè)輸入符號(hào)，則信道錯(cuò)誤概率就能最?。患词盏椒?hào)bj以后譯成具有最大后驗(yàn)概率的輸入符號(hào)a*.該譯碼準(zhǔn)則稱(chēng)為“最大后驗(yàn)概率譯碼準(zhǔn)則(MAP，MaximumaPosteriori)

”或“最小錯(cuò)誤概率譯碼準(zhǔn)則”.也叫最大聯(lián)合概率譯碼準(zhǔn)則。對(duì)每個(gè)輸出符號(hào)均譯成具有最大后驗(yàn)概率的那個(gè)輸入符號(hào)，則信道錯(cuò)誤概率就能最小。

我們一般已知信道傳遞概率p(bj|ai)與輸入符號(hào)先驗(yàn)概率p(ai),所以根據(jù)貝葉斯定律,上式也可以寫(xiě)成一般p(bj)≠0.這樣最大后驗(yàn)概率準(zhǔn)則就表示為:選擇譯碼函數(shù)F(bj)=a*, 使?jié)M足p(bj|a*)p(a*)≥p(bj|ai)p(ai),也即p(a*bj)≥p(aibj).—最大聯(lián)合概率譯碼準(zhǔn)則p(a*|bj)≥p(ai|bj)四、兩種譯碼準(zhǔn)則-最大似然譯碼準(zhǔn)則最大似然譯碼準(zhǔn)則(maximumlikelihoodML準(zhǔn)則)

前面介紹的最大后驗(yàn)概率譯碼準(zhǔn)則等同于最小傳輸錯(cuò)誤概率準(zhǔn)則，從錯(cuò)誤概率最小角度，該譯碼準(zhǔn)則是最好的。

在實(shí)際應(yīng)用中，通常用同一信道去傳輸各種不同的信源，只知道信道的轉(zhuǎn)移概率，而不知道信源的分布，故無(wú)法計(jì)算全概率，故無(wú)法采用最大后驗(yàn)概率譯碼準(zhǔn)則進(jìn)行譯碼。

如果輸入符號(hào)等概發(fā)生,則選擇譯碼函數(shù)F(bj)=a*,并滿(mǎn)足p(bj|a*)≥p(bj|ai) 該譯碼規(guī)則稱(chēng)為:最大似然譯碼準(zhǔn)則.該準(zhǔn)則表示收到bj后,在信道矩陣的第j列,選擇最大的值對(duì)應(yīng)輸入符號(hào)a*作為譯碼輸出.平均錯(cuò)誤概率

根據(jù)譯碼規(guī)則,可進(jìn)一步寫(xiě)出平均錯(cuò)誤概率PE,即而平均正確概率為平均錯(cuò)誤概率也可寫(xiě)成:如果先驗(yàn)概率p(ai)相等,則:平均錯(cuò)誤概率先對(duì)行求和，除去譯碼規(guī)則中所對(duì)應(yīng)的概率，然后是各行之和幾點(diǎn)說(shuō)明1）當(dāng)輸入符號(hào)等概時(shí)，最大似然準(zhǔn)則等價(jià)于最大后驗(yàn)概率準(zhǔn)則。2）該準(zhǔn)則可直接從信道傳遞矩陣中選定譯碼函數(shù)，即收到bj后，譯成信道矩陣p中第j列中最大那個(gè)元素所對(duì)應(yīng)的信源符號(hào)。3）該準(zhǔn)則本身不再依賴(lài)于先驗(yàn)概率p(ai)，但當(dāng)輸入符號(hào)等概時(shí)，它使平均錯(cuò)誤概率PE最小。4）當(dāng)輸入符號(hào)等概或先驗(yàn)概率未知時(shí)，采用此準(zhǔn)則。兩種準(zhǔn)則使用要點(diǎn)MAP準(zhǔn)則-最大后驗(yàn)概率準(zhǔn)則

1）由轉(zhuǎn)移概率矩陣的每行分別乘p(x)，得到聯(lián)合概率矩陣；

2）對(duì)于每一列（相當(dāng)于y固定）找一個(gè)最大的概率對(duì)應(yīng)的X作為譯碼結(jié)果；

3）所有譯碼結(jié)果所對(duì)應(yīng)的聯(lián)合概率的和為正確概率，其他矩陣元素的和為錯(cuò)誤概率。ML準(zhǔn)則--最大似然譯碼準(zhǔn)則1）對(duì)轉(zhuǎn)移概率矩陣中每列選擇最大的一個(gè)元素對(duì)應(yīng)的x作為譯碼結(jié)果；2）所有譯碼結(jié)果所對(duì)應(yīng)的轉(zhuǎn)移概率的和再乘以1/r（或pi）為正確概率,其他矩陣元素的和再乘以1/r（或pi）為錯(cuò)誤概率。當(dāng)輸入分布等概時(shí)，最大似然譯碼準(zhǔn)則和最大后驗(yàn)概率準(zhǔn)則是等價(jià)的。根據(jù)最大似然譯碼準(zhǔn)則，我們可以直接從信道矩陣的傳遞概率中去選定譯碼函數(shù)：就是說(shuō)，收到后，譯成信道矩陣的第j列中最大的那個(gè)元素所對(duì)應(yīng)的信源符號(hào)。最大似然譯碼準(zhǔn)則本身不再依賴(lài)于先驗(yàn)概率。但是當(dāng)先驗(yàn)概率為等概時(shí)，它使錯(cuò)誤概率PE最小。如果先驗(yàn)概率不相等或不知道時(shí)，仍可以采用這個(gè)準(zhǔn)則，但不一定能使PE最小。如果知道先驗(yàn)概率，應(yīng)該使用最大后驗(yàn)概率準(zhǔn)則;如果不知道先驗(yàn)概率，則只能用最大似然準(zhǔn)則.例題5.2.2已知信道的轉(zhuǎn)移概率矩陣為現(xiàn)有兩種譯碼規(guī)則：規(guī)則A：規(guī)則B：設(shè)輸入等概，求兩種譯碼規(guī)則的錯(cuò)誤概率。解：設(shè)判決函數(shù)為，根據(jù)平均錯(cuò)誤概率公式得Thefourteenthclass--2014書(shū)上P104可見(jiàn)這兩種方法得到同一結(jié)果，因?yàn)橐玫胶篁?yàn)概率，計(jì)算步驟更多，所以可直接應(yīng)用最大聯(lián)合概率譯碼準(zhǔn)則譯碼?！纠啃旁捶植?/p>

信道轉(zhuǎn)移概率矩陣

，信道輸出符號(hào)Y={y1，y2，y3}。（1）計(jì)算按最大后驗(yàn)概率準(zhǔn)則譯碼的平均錯(cuò)誤概率；（2）若信源等概分布，對(duì)其按極大似然譯碼準(zhǔn)則譯碼，并求平均錯(cuò)誤概率。

【解】（1）最大后驗(yàn)概率準(zhǔn)則譯碼

前面同一例子求平均錯(cuò)誤概率平均錯(cuò)誤概率：

（2）當(dāng)信源等概分布，按極大似然函數(shù)譯碼準(zhǔn)則譯碼，已給出信道轉(zhuǎn)移概率矩陣為

在矩陣的每列中選一最大值(矩陣中帶下劃線(xiàn)的值)，譯碼為

平均錯(cuò)誤概率：

第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則例5.3:

根據(jù)最大似然準(zhǔn)則可選擇譯碼函數(shù)為B:若采用前述譯碼函數(shù)A,則平均錯(cuò)誤率為:可見(jiàn)第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則若輸入不等概,仍可采用最大似然譯碼準(zhǔn)則,其概率分布為:第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則輸入不是等概分布時(shí)，比較最大似然譯碼準(zhǔn)則和最小錯(cuò)誤概率譯碼準(zhǔn)則若采用最小錯(cuò)誤概率譯碼準(zhǔn)則,其聯(lián)合矩陣{p(aibj)}為:所得譯碼函數(shù)為:C:第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則平均錯(cuò)誤率為:可見(jiàn),.所以輸入非等概分布時(shí)最大似然譯碼準(zhǔn)則獲得的平均錯(cuò)誤概率不是最小的.第5.1節(jié)錯(cuò)誤概率與譯碼規(guī)則§5.3費(fèi)諾(Fano)不等式1.信道疑義度（損失熵）2.費(fèi)諾(Fano)不等式平均錯(cuò)誤概率Pe與譯碼規(guī)則(譯碼函數(shù))有關(guān)，而譯碼規(guī)則又由信道特性來(lái)決定。由于信道中存在噪聲，導(dǎo)致輸出端發(fā)生錯(cuò)誤，并使接收端輸出符號(hào)后，對(duì)發(fā)送的是什么符號(hào)還存在不確定性?？梢?，Pe與信道疑義度具有一定的關(guān)系，就是下面要講的費(fèi)諾不等式5.3.1信道疑義度（回憶）設(shè)信道的輸入與輸出分別為X、Y，定義條件熵H(X/Y)為信道疑義度。信道疑義度的含義：信道疑義度表示接收到Y(jié)條件下X的平均不確定性；根據(jù)I(X;Y)=H(X)-H(X/Y)，信道疑義度又表示X經(jīng)信道傳輸信息量的損失；8－2Fano不等式證明：倒數(shù)？(2)如果判決出錯(cuò)（概率為）,錯(cuò)在r-1個(gè)符號(hào)中的哪一個(gè)，其疑義度不會(huì)超log(r-1)。

物理意義進(jìn)行一次判決后，關(guān)于X的疑義度可分成兩項(xiàng)：(1)是否判對(duì)，疑義度為H

()費(fèi)諾不等式示意圖信道疑義度是信源熵H(X)超過(guò)平均互信息I(X;Y)的部分。若以H(X|Y)為縱坐標(biāo)，PE為橫坐標(biāo)，則函數(shù)H(PE)+PElog(n-1)隨PE變化的曲線(xiàn)如圖所示。由圖可知，當(dāng)信源、信道給定時(shí)，信道疑義度H(X|Y)就給定了譯碼平均錯(cuò)誤概率PE的下限。

注釋第5.2節(jié)錯(cuò)誤概率與編碼方法

一般信道傳輸時(shí)都會(huì)產(chǎn)生錯(cuò)誤,而選擇譯碼準(zhǔn)則并不會(huì)消除錯(cuò)誤,那么如何減少錯(cuò)誤概率呢?下邊討論通過(guò)編碼方法來(lái)降低錯(cuò)誤概率.第5.2節(jié)錯(cuò)誤概率與編碼方法a1=0a2=1b1=0b2=10.990.990.010.01例:對(duì)于如下二元對(duì)稱(chēng)信道若選擇最佳譯碼規(guī)則F(b1)=a1F(b2)=a2對(duì)于一般傳輸系統(tǒng)(如數(shù)字通信),這個(gè)概率已經(jīng)相當(dāng)大了.一般要求系統(tǒng)的錯(cuò)誤概率在10-6~10-9范圍內(nèi),甚至更低.簡(jiǎn)單重復(fù)編碼如何提高信道傳輸?shù)恼_率呢？可嘗試下面的方法實(shí)際經(jīng)驗(yàn)告訴我們：只要在發(fā)送端把消息重復(fù)發(fā)幾遍，也就是增加消息的傳輸時(shí)間，就可使接收端接收消息時(shí)錯(cuò)誤減小，從而提高了通信的可靠性。如在二元對(duì)稱(chēng)信道中，當(dāng)發(fā)送消息（符號(hào)）0時(shí)，不是只發(fā)一個(gè)0而是連續(xù)發(fā)三個(gè)0，同樣發(fā)送消息（符號(hào)）1時(shí)也連續(xù)發(fā)送三個(gè)1，這是一種最簡(jiǎn)單的編碼方法，他它將長(zhǎng)度n=1的兩個(gè)二元序列變換為兩個(gè)長(zhǎng)度n=3的二元序列，我們稱(chēng)這兩個(gè)長(zhǎng)度為3的二元序列為碼字，于是信道輸入端有兩個(gè)碼字000和111，但在輸出端，由于信道干擾的作用，碼字中各個(gè)碼元（碼符號(hào)）都可能發(fā)生錯(cuò)誤，則有8個(gè)可能的輸出序列，如下面簡(jiǎn)單重復(fù)編碼

如何提高信道傳輸?shù)恼_率呢？可嘗試下面的方法沒(méi)有使用的碼字001010011100101110用作消息的碼字000111輸出端接收序列000001010011100101110111二元對(duì)稱(chēng)信道的三次擴(kuò)展信道重復(fù)編碼(n=3次)：信道看成是3次擴(kuò)展，輸出端由于各個(gè)干擾，各個(gè)碼元都可能發(fā)生錯(cuò)誤，則有8個(gè)可能的輸出序列。根據(jù)最大似然譯碼準(zhǔn)則(假設(shè)輸入時(shí)等概率的),可得簡(jiǎn)單重復(fù)編碼的譯碼規(guī)則為F(β1)=F(β2)=F(β3)=F(β5)=α1F(β4)=F(β6)=F(β7)=F(β8)=α8信道矩陣簡(jiǎn)單重復(fù)編碼根據(jù)這個(gè)規(guī)則計(jì)算得譯碼后的錯(cuò)誤概率為簡(jiǎn)單重復(fù)編碼簡(jiǎn)單重復(fù)編碼也可以采用“擇多譯碼”,即根據(jù)接收序列中0多還是1多,0多就判作0,1多就判作1.可得譯碼函數(shù)為：F(000)=000,F(001)=000,F(010)=000,F(011)=111F(100)=000,F(101)=111,F(110)=111,F(111)=111根據(jù)擇多譯碼規(guī)則,同樣可得到可見(jiàn),擇多譯碼準(zhǔn)則與最大似然譯碼準(zhǔn)則是一致的.

簡(jiǎn)單重復(fù)編碼與原來(lái)PE=10-2比較,這種簡(jiǎn)單重復(fù)的編碼方法已把譯碼錯(cuò)誤概率降低了近兩個(gè)數(shù)量級(jí).結(jié)論：重復(fù)編碼使PE減小原因:這種編碼可以糾正碼字中的一位碼元出錯(cuò),譯錯(cuò)的可能性變小了,因此錯(cuò)誤概率降低.簡(jiǎn)單重復(fù)編碼若重復(fù)更多次可進(jìn)一步降低錯(cuò)誤率.可算得可見(jiàn),當(dāng)n很大時(shí),使PE很小是可能的.但這又帶來(lái)了一個(gè)新問(wèn)題,n很大時(shí),信息傳輸率會(huì)降低很多.簡(jiǎn)單重復(fù)編碼編碼后信息傳輸率為在上例中：M=2當(dāng)n=1時(shí)R=1當(dāng)n=3時(shí)R=1/3當(dāng)n=5時(shí)R=1/5............由此得PE和R的關(guān)系,如右圖.它表明:盡管PE降低很多,但也使信息傳輸率降得很低.M為輸入信息（許用碼字）的個(gè)數(shù)。logM表示消息集在等概率條件下每個(gè)消息（碼字）攜帶的平均信息量（比特）。n是編碼后碼字的長(zhǎng)度（碼元的個(gè)數(shù)）Thefifteenthclass--2014復(fù)習(xí)上一次課主要內(nèi)容一、費(fèi)諾(Fano)不等式二、降低錯(cuò)誤概率的方法§5.3費(fèi)諾(Fano)不等式1.信道疑義度2.費(fèi)諾(Fano)不等式平均錯(cuò)誤概率Pe與譯碼規(guī)則(譯碼函數(shù))有關(guān)，而譯碼規(guī)則又由信道特性來(lái)決定。由于信道中存在噪聲，導(dǎo)致輸出端發(fā)生錯(cuò)誤，并使接收端輸出符號(hào)后，對(duì)發(fā)送的是什么符號(hào)還存在不確定性。可以，Pe與信道疑義度具有一定的關(guān)系，就是下面要講的費(fèi)諾不等式香農(nóng)第二定理這顯然是一個(gè)矛盾,有沒(méi)有解決的辦法,能不能找到一種更好的編碼方法,使PE相當(dāng)?shù)?而R卻保持在一定水平呢？這就是香農(nóng)第二定理,即有噪信道編碼定理.在上圖中,也給出了香農(nóng)第二定理的PE和R的關(guān)系值,其中ε為任意小的數(shù).設(shè)離散無(wú)記憶信道[X,p(y|x),Y]，其信道容量為C。當(dāng)信息傳輸率R<C時(shí)，只要碼長(zhǎng)n足夠長(zhǎng)，總可以在輸入符號(hào)集中找到個(gè)碼字組成的一組碼和相應(yīng)的譯碼規(guī)則，使譯碼的錯(cuò)誤概率任意小。與信源編碼定理的證明類(lèi)似，構(gòu)造編碼方法。第三節(jié)有噪信道編碼定理(香農(nóng)第二定理)基本思路—證明有噪信道編碼定理香農(nóng)對(duì)有噪信道編碼定理證明方法的基本思路是：連續(xù)使用信道多次，即在n次無(wú)記憶擴(kuò)展信道中討論，以便使大數(shù)定律有效；隨機(jī)地選取碼書(shū)，也就是在Xn的符號(hào)序列集中隨機(jī)地選取經(jīng)常出現(xiàn)的高概率序列作為碼字；采用最大似然譯碼準(zhǔn)則，也就是將接收序列譯成與其距離最近的那個(gè)碼字；在隨機(jī)編碼的基礎(chǔ)上，對(duì)所有的碼書(shū)計(jì)算其平均錯(cuò)誤概率。當(dāng)n足夠大時(shí)，此平均錯(cuò)誤概率趨于零，由此證明得至少有一種好碼存在。證明：離散無(wú)記憶信道[X,p(y|x),Y]，輸入序列為輸出序列：轉(zhuǎn)移概率：編碼速率為R，則消息的標(biāo)號(hào)集為編碼函數(shù)可看作下述映射：譯碼函數(shù)為：發(fā)送m的條件下譯碼錯(cuò)誤概率為：譯碼的平均誤組率為（消息等概）具體的證明過(guò)程----了解從中獨(dú)立隨機(jī)地選取個(gè)序列作為碼字，這相當(dāng)于每個(gè)碼字出現(xiàn)的概率為消息序列出現(xiàn)的概率:X中任一元素獨(dú)立等概地出現(xiàn)，這種編碼方法稱(chēng)作隨機(jī)編碼。譯碼規(guī)則：（典型序列準(zhǔn)則—譯為聯(lián)合典型序列的x）對(duì)給定的接受序列y，若存在唯一的使就將y譯為m'，即D(y)=m'。當(dāng)或者有兩個(gè)以上m’和y構(gòu)成聯(lián)合典型序列時(shí)，就認(rèn)為譯碼出錯(cuò)。就是任意特定消息被錯(cuò)誤譯碼的概率。所以不失一般性可假設(shè)發(fā)送的是第一個(gè)消息。譯碼錯(cuò)誤概率為因?yàn)殡S機(jī)碼具有對(duì)稱(chēng)性，所以譯碼錯(cuò)誤概率與送出的消息編號(hào)無(wú)關(guān)，也就是隨機(jī)碼集合的平均錯(cuò)誤概率再具體一些說(shuō)，就是：為了使R大，可使I(X:Y)極大化，即以C代替。若R<C-3，隨著n趨于無(wú)窮大，上面的錯(cuò)誤概率趨于0。因?yàn)镽<C-3，上面的錯(cuò)誤概率趨于0，所以必定存在一種碼，當(dāng)n足夠大時(shí)，其譯碼錯(cuò)誤概率為0。

Shannon第二定理另一種形式！有噪信道編碼定理，即Shannon第二定理。--書(shū)上的證明方法！P1065．3信道編碼定理定理5.1對(duì)于任何離散無(wú)記憶信道DMC，存在信息傳輸率為R，長(zhǎng)為n的碼，當(dāng)n→∞時(shí)，平均差錯(cuò)概率pe<exp{-nE(R)}→0，式中E(R)為可靠性函數(shù)，E(R)在0<R<C的范圍內(nèi)為正。

1．隨機(jī)編碼方法信道輸入符號(hào)集A={a1,a2,…,ak},選用長(zhǎng)為n的定長(zhǎng)碼，共可構(gòu)成kn個(gè)矢量，設(shè)有M個(gè)消息待傳（M<kn），每次隨機(jī)地從kn個(gè)矢量中抽出M個(gè)矢量構(gòu)成一個(gè)碼集C（允許重復(fù)?。〤

={x1,…,xm,…,x

M}共可構(gòu)成knM個(gè)這樣的碼集。由隨機(jī)編碼的構(gòu)造方法，得到任何一個(gè)碼字的概率相同，且相互獨(dú)立。

上述定理也稱(chēng)有噪信道編碼定理，即Shannon第二定理。

2．Gallager上界因?yàn)樯鲜霭措S機(jī)編碼方法構(gòu)成的碼集是等概分布的，按照最大似然譯碼準(zhǔn)則譯碼，在發(fā)送碼矢xk時(shí)，要得到正確譯碼須滿(mǎn)足

，即

（5-5）

定義示性函數(shù)則發(fā)送碼矢xk判錯(cuò)的概率為

（5-6）

書(shū)上錯(cuò)的根據(jù)式(5-5)，當(dāng)0

,

1時(shí)，下式成立用示性函數(shù)Ik(y)表示上式，即

（5-7）

將式(5-7)代入式(5-6)，得式中0

,

1，因?yàn)?

都是任意數(shù)，可取，則有

（5-8）

Gallager上界3．隨機(jī)編碼錯(cuò)誤概率上界

Gallager限僅給出發(fā)送碼矢xk時(shí)的錯(cuò)誤概率上界，還要對(duì)全部碼矢求平均，下面對(duì)上述的隨機(jī)編碼集合求平均。

對(duì)于隨機(jī)編碼，各碼字等概且獨(dú)立，有，對(duì)式(5-8)求統(tǒng)計(jì)平均值，得平均錯(cuò)誤概率上界

(5-9)

后面一項(xiàng)，因?yàn)?

1，而x是x的∩型凸函數(shù)，由∩型凸函數(shù)的定義知：函數(shù)均值均值函數(shù)，即有(5-10)因?yàn)閤m(m=1,2,…,M)都通過(guò)同一信道傳輸，故p(y︱xm)值相同，記為p(y︱x)，代入式（5－10）得

(5-11)

將式(5-11)代回式(5-9)，得

（5－12）

平均錯(cuò)誤概率的一個(gè)上界4．離散無(wú)記憶信道DMC的錯(cuò)誤概率上界

對(duì)于n維離散無(wú)記憶信道DMC，有，對(duì)于隨機(jī)編碼，將這兩個(gè)關(guān)系式代入式(5-12)，有（5－13）

序列x=x1,…,xi,,…,xn中的

xi,取自同一符號(hào)A={a1,a2,…,ak}，故分布q(xi)相同,（5－14）

將式（5－14）代入式（5－13），得

（5－15）

5．可靠性函數(shù)E(R)信息傳輸率，則式(5－15)可寫(xiě)為： (5-16)

記則式(5-16)可寫(xiě)成

pe

<exp{-n[-R+E0(,q)]}(5-17)

對(duì)式(5-17)右邊求極小值，即對(duì)指數(shù)-R+E0(,q)求極大值,記這個(gè)極大值為則式(5-17)可寫(xiě)為pe<exp{-nE

(R)}稱(chēng)E

(R)為可靠性函數(shù),也稱(chēng)隨機(jī)編碼指數(shù)，它與信道轉(zhuǎn)移概率p(y︱x)有關(guān)。

在0

R

C的范圍內(nèi)，E

(R)是下降的、下凹的正值函數(shù)，說(shuō)明E

(R)有界，這樣，當(dāng)時(shí)，有exp{-nE

(R)}→0，從而pe

<exp{-n

E

(R)}→0。

2、有噪信道編碼逆定理如一離散無(wú)記憶信道,其容量為C.當(dāng)信息傳輸率R>C時(shí),則無(wú)論碼長(zhǎng)n多長(zhǎng),總找不到一種編碼(2nR,n)使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小.第三節(jié)有噪信道編碼定理

這個(gè)定理是信道編碼的理論依據(jù),可以看出:

信道容量是一個(gè)明確的分界點(diǎn),當(dāng)取分界點(diǎn)以下的信息傳輸率時(shí),PE以指數(shù)趨進(jìn)于0;

當(dāng)取分