第5章有噪信道編碼

第5章有噪信道編碼

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

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

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

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

=F(y)。

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

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

下面為重復編碼傳輸示意圖，計算錯誤概率pe。書上例題5.1信源輸出序列為：

信道輸入序列為：

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

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

信道錯誤概率：假設信道離散無記憶，即

錯誤概率為：

重復編碼的結果使錯誤概率下降。

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

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

p

1011-p

p

計算差錯概率pe：分二步進行：（1）先設p=0，計算這種編碼方法帶來的固有錯誤p1信道輸入符號集X={000,001,010,011,100,101,110,111}判決輸出符號集Y={000,111}譯碼規(guī)則因為后驗概率則出錯概率

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

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

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

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

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

但是一般信道總會存在噪聲和干擾,那么在有噪信道中進行無錯傳輸可以達到的最大信息傳輸率是多少呢？這就是本章所要討論的問題。

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

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

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

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

如果采用這樣一種譯碼函數(shù)，它對于每一個輸出符號均譯成具有最大后驗概率的那個輸入符號，則信道錯誤概率就能最??；即收到符號bj以后譯成具有最大后驗概率的輸入符號a*.該譯碼準則稱為“最大后驗概率譯碼準則(MAP，MaximumaPosteriori)

”或“最小錯誤概率譯碼準則”.也叫最大聯(lián)合概率譯碼準則。對每個輸出符號均譯成具有最大后驗概率的那個輸入符號，則信道錯誤概率就能最小。

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

前面介紹的最大后驗概率譯碼準則等同于最小傳輸錯誤概率準則，從錯誤概率最小角度，該譯碼準則是最好的。

在實際應用中，通常用同一信道去傳輸各種不同的信源，只知道信道的轉移概率，而不知道信源的分布，故無法計算全概率，故無法采用最大后驗概率譯碼準則進行譯碼。

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

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

如果采用這樣一種譯碼函數(shù)，它對于每一個輸出符號均譯成具有最大后驗概率的那個輸入符號，則信道錯誤概率就能最?。患词盏椒朾j以后譯成具有最大后驗概率的輸入符號a*.該譯碼準則稱為“最大后驗概率譯碼準則(MAP，MaximumaPosteriori)

”或“最小錯誤概率譯碼準則”.也叫最大聯(lián)合概率譯碼準則。對每個輸出符號均譯成具有最大后驗概率的那個輸入符號，則信道錯誤概率就能最小。

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

前面介紹的最大后驗概率譯碼準則等同于最小傳輸錯誤概率準則，從錯誤概率最小角度，該譯碼準則是最好的。

在實際應用中，通常用同一信道去傳輸各種不同的信源，只知道信道的轉移概率，而不知道信源的分布，故無法計算全概率，故無法采用最大后驗概率譯碼準則進行譯碼。

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

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

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

2）對于每一列（相當于y固定）找一個最大的概率對應的X作為譯碼結果；

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

信道轉移概率矩陣

，信道輸出符號Y={y1，y2，y3}。（1）計算按最大后驗概率準則譯碼的平均錯誤概率；（2）若信源等概分布，對其按極大似然譯碼準則譯碼，并求平均錯誤概率。

【解】（1）最大后驗概率準則譯碼

前面同一例子求平均錯誤概率平均錯誤概率：

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

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

平均錯誤概率：

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

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

物理意義進行一次判決后，關于X的疑義度可分成兩項：(1)是否判對，疑義度為H

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

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

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

如何提高信道傳輸?shù)恼_率呢？可嘗試下面的方法沒有使用的碼字001010011100101110用作消息的碼字000111輸出端接收序列000001010011100101110111二元對稱信道的三次擴展信道重復編碼(n=3次)：信道看成是3次擴展，輸出端由于各個干擾，各個碼元都可能發(fā)生錯誤，則有8個可能的輸出序列。根據(jù)最大似然譯碼準則(假設輸入時等概率的),可得簡單重復編碼的譯碼規(guī)則為F(β1)=F(β2)=F(β3)=F(β5)=α1F(β4)=F(β6)=F(β7)=F(β8)=α8信道矩陣簡單重復編碼根據(jù)這個規(guī)則計算得譯碼后的錯誤概率為簡單重復編碼簡單重復編碼也可以采用“擇多譯碼”,即根據(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ī)則,同樣可得到可見,擇多譯碼準則與最大似然譯碼準則是一致的.

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

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

1．隨機編碼方法信道輸入符號集A={a1,a2,…,ak},選用長為n的定長碼，共可構成kn個矢量，設有M個消息待傳（M<kn），每次隨機地從kn個矢量中抽出M個矢量構成一個碼集C（允許重復?。〤

={x1,…,xm,…,x

M}共可構成knM個這樣的碼集。由隨機編碼的構造方法，得到任何一個碼字的概率相同，且相互獨立。

上述定理也稱有噪信道編碼定理，即Shannon第二定理。

2．Gallager上界因為上述按隨機編碼方法構成的碼集是等概分布的，按照最大似然譯碼準則譯碼，在發(fā)送碼矢xk時，要得到正確譯碼須滿足

，即

（5-5）

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

（5-6）

書上錯的根據(jù)式(5-5)，當0

,

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

（5-7）

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

,

1，因為,

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

（5-8）

Gallager上界3．隨機編碼錯誤概率上界

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

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

(5-9)

后面一項，因為0

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

(5-11)

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

（5－12）

平均錯誤概率的一個上界4．離散無記憶信道DMC的錯誤概率上界

對于n維離散無記憶信道DMC，有，對于隨機編碼，將這兩個關系式代入式(5-12)，有（5－13）

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

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

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

（5－15）

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

記則式(5-16)可寫成

pe

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

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

(R)}稱E

(R)為可靠性函數(shù),也稱隨機編碼指數(shù)，它與信道轉移概率p(y︱x)有關。

在0

R

C的范圍內，E

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

(R)有界，這樣，當時，有exp{-nE

(R)}→0，從而pe

<exp{-n

E

(R)}→0。

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

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

信道容量是一個明確的分界點,當取分界點以下的信息傳輸率時,PE以指數(shù)趨進于0;

當取分