中南大學信息論與編碼課件Inf-T-C-74N

信息論與編碼張祖平/ZhangZuping電子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,zpzhang@InformationTheory&Coding第七章抗干擾信道編碼2013秋季信息111InfTheory&Coding-張祖平本章主要內(nèi)容

(MainContent)7.1譯碼規(guī)則7.2譯碼規(guī)則的選擇準則7.3信道編碼的編碼原則7.4抗干擾信道編碼定理7.5分組碼及其檢糾能力7.6線性分組碼的代數(shù)結(jié)構(gòu)7.7簡單重復編碼7.8香農(nóng)第二定理7.9標準陣列與譯碼表7.10檢糾能力與一致校驗矩陣的關(guān)系7.11完備碼7.12漢明碼與擴展?jié)h明碼2013秋季信息112InfTheory&Coding-張祖平抗干擾信道編碼

實際的通信信道總是存在噪聲的干擾，為了兼顧有效性和可靠性，我們往往對無失真信源編碼的碼字，用有噪信道的輸入符號集作為碼符號集，再進行一次編碼，利用和挖掘信道的統(tǒng)計特性，在保持一定有效性的基礎(chǔ)上，提高其抗干擾能力。

2013秋季信息113InfTheory&Coding-張祖平7.1譯碼規(guī)則

在完整的通信過程中，譯碼規(guī)則對通信的可靠性有重大影響。設(shè)有噪離散信道的輸入符號集，輸出符號集，信道的傳遞概率。由于噪聲的隨機干擾，信道輸入某符號，輸出的一般是的某一種變型。根據(jù)一定的判決準則，設(shè)計一個單值函數(shù)是使每一種可能的輸出符號與一個唯一的輸入符號一一對應。共構(gòu)成種不同的譯碼規(guī)則。2013秋季信息114InfTheory&Coding-張祖平

在信道輸出端收到某符號后正確譯碼的概率，就應該是信道輸出端出現(xiàn)的前提下，推測信道輸入符號的后驗概率，即同理，錯誤譯碼的概率就是其中“”表示除了以外的所有其它可能的輸入符號的集合。上式也可改寫為

7.1譯碼規(guī)則2013秋季信息115InfTheory&Coding-張祖平

后驗概率在信道輸出隨機變量的概率空間中的統(tǒng)計平均值，即同樣，后驗概率在信道輸出隨機變量的概率空間中的統(tǒng)計平均值，即平均錯誤譯碼概率是衡量通信的可靠性的標準。7.1譯碼規(guī)則2013秋季信息116InfTheory&Coding-張祖平

由上式可知，平均錯誤譯碼概率就唯一地由選擇的譯碼規(guī)則所決定，不同的譯碼規(guī)則就有不同的平均錯誤概率。所以，選擇合適的譯碼規(guī)則，就成為降低平均錯誤譯碼概率，提高通信有效性的一種可控制的手段。

7.1譯碼規(guī)則2013秋季信息117InfTheory&Coding-張祖平錯誤概率錯誤原因：噪聲干擾錯誤概率與信道的統(tǒng)計特性有關(guān)，信道的統(tǒng)計特性由信道的傳遞矩陣來描述。當確定了輸入和輸出對應關(guān)系后，也就確定了信道矩陣中哪些是正確傳遞概率，哪些是錯誤傳遞概率。譯碼規(guī)則錯誤表現(xiàn)：譯碼輸出≠信源輸出通信過程一般并不是在信道輸出端就結(jié)束了，還要經(jīng)過譯碼(或判決)過程才到達消息的終端(收信者)。因此譯碼過程和譯碼規(guī)則對系統(tǒng)的錯誤概率影響很大。為了減少錯誤，提高通信的可靠性，就必須分析錯誤概率與譯碼規(guī)則，有沒有辦法控制，能控制到什么程度。87.1譯碼規(guī)則2013秋季信息118InfTheory&Coding-張祖平譯碼規(guī)則的定義設(shè)離散單符號信道：輸入符號集為輸出符號集為制定譯碼規(guī)則就是定義一個單值函數(shù)它對于每一個輸出符號bj

確定一個惟一的輸入符號ai

與其對應。97.1譯碼規(guī)則2013秋季信息119InfTheory&Coding-張祖平譯碼規(guī)則的定義由于s個輸出符號中的每一個都可以譯成r個輸入符號中的任何一個，所以共有

rs

種譯碼規(guī)則可供選擇。(見書上例子)若信道輸出端接收到的符號為bj

，則譯為ai

若發(fā)送端發(fā)送的是ai則為正確譯碼；否則為錯誤譯碼。定義收到bj條件下譯碼的條件正確概率（后驗概率）為：定義收到bj

條件下譯碼的條件錯誤概率（后驗概率）為：（e代表任何除ai外可能的輸入符號）：107.1譯碼規(guī)則2013秋季信息1110InfTheory&Coding-張祖平譯碼規(guī)則的定義每收到一個符號的平均正確譯碼概率，是輸出隨機變量Y的概率空間的統(tǒng)計平均值。每收到一個符號的平均錯誤譯碼概率，是輸出隨機變量Y的概率空間的統(tǒng)計平均值。11在信道傳輸概率確定情況下，顯然，不同的譯碼規(guī)則會出現(xiàn)不同的平均錯誤譯碼概率如何選擇譯碼規(guī)則，讓Perror簡寫成Pe更小呢？Pright簡寫成Pr更大呢??7.1譯碼規(guī)則2013秋季信息1111InfTheory&Coding-張祖平7.2譯碼規(guī)則選擇準則信源和信道概率復習12

b1b2…bsa1P(b1|a1)P(b2|a1)…P(bs|a1)a2P(b1|a2)P(b2|a2)…P(bs|a2)…….……arP(b1|ar)P(b2|ar)…P(bs|ar)2013秋季信息1112InfTheory&Coding-張祖平最大后驗概率準則(最小錯誤概率準則)要使平均錯誤譯碼概率Pe最小，就要平均正確譯碼概率Pr最大。通過信源先驗概率和信道矩陣中條件概率，計算出每個輸出符號概率，和每個輸出符號判斷輸入符號的后驗概率。后驗概率是我們的依據(jù)，似乎信源先驗概率，信道矩陣中條件概率都與譯碼規(guī)則無直接關(guān)系。針對某個bj，選擇r個后驗概率p(ai/bj)中最大的值時對應的a*，就可以使信道錯誤概率最小，這種譯碼規(guī)則稱“最大后驗概率準則”13即選擇譯碼函數(shù)：并滿足:7.2譯碼規(guī)則選擇準則2013秋季信息1113InfTheory&Coding-張祖平平均錯誤譯碼概率與平均正確譯碼概率的計算14因此，使用最大后驗概率準則可以讓平均錯誤譯碼概率最小，而且只取決于給定信源空間和給定信道矩陣，也就是說，信源和信道給定時，通信的可靠性最高程度就已經(jīng)確定。表示對輸入符號集中除F（bj）=a*以外的所有元素求和。7.2譯碼規(guī)則選擇準則2013秋季信息1114InfTheory&Coding-張祖平舉例：設(shè)有一離散信道，其信道矩陣為，當信源X的概率分布為р(a1)＝2/3，р(a2)＝р(a3)＝1/6時，按最大后驗概率準則選擇譯碼函數(shù)，并計算其平均錯誤譯碼概率Pemin．157.2譯碼規(guī)則選擇準則a1a2a3b1b2b32013秋季信息1115InfTheory&Coding-張祖平最大似然概率準則16當信源等概分布時，可選擇譯碼函數(shù)：并滿足：這樣定義的譯碼規(guī)則稱為最大似然概率準則最大似然譯碼準則的方法是收到一個bj

后，在信道矩陣的第j列，選擇最大的傳輸概率值所對應的輸入符號作為譯碼輸出。最大似然譯碼準則本身不再依賴于先驗概率P(ai)，只依賴于信道傳遞特性

。但當先驗概率為等概率分布時，它使錯誤概率PE最小。7.2譯碼規(guī)則選擇準則2013秋季信息1116InfTheory&Coding-張祖平最大似然概率準則最大后驗概率需要求解輸出概率和后驗概率，計算較為復雜。當信源個符號是等概率輸入時可以進一步簡化計算過程。已知信道的傳遞概率P(bj|ai)與輸入符號的先驗概率P(ai)。17后驗概率的比較可以轉(zhuǎn)化為先驗概率和傳輸概率乘積的比較：當輸入為等概率時，可以轉(zhuǎn)化為傳輸概率的比較：7.2譯碼規(guī)則選擇準則2013秋季信息1117InfTheory&Coding-張祖平輸入等概率情況下：平均錯誤譯碼概率的計算18上式表明在等先驗概率分布情況下，譯碼錯誤概率可用信道矩陣中的元素P(bj|ai)求和（不包括每列對應于F(bj)=a*的那一項）來表示。7.2譯碼規(guī)則選擇準則2013秋季信息1118InfTheory&Coding-張祖平舉例：輸入為a1，a2，a3，輸出為b1，b2，b3，輸入等概率1/3，使用最大似然概率準則設(shè)計譯碼規(guī)則，求其平均錯誤譯碼概率。19第一列0.5最大，所以b1對應a1第三列0.5最大，所以b3對應a2第二列值一樣，所以b2可以對應任意一個，由于b1和b3有確定對應，所以b2對應a3計算技巧：去掉信道矩陣中每列最大的值，然后余下的元素相加，并乘上1/r7.2譯碼規(guī)則選擇準則2013秋季信息1119InfTheory&Coding-張祖平練習接前面例題，還是輸入等概率分布，如果譯碼規(guī)則如下，求平均錯誤譯碼概率。20計算技巧：去掉信道矩陣中每列被譯碼的值，然后余下的元素相加，并乘上1/r7.2譯碼規(guī)則選擇準則2013秋季信息1120InfTheory&Coding-張祖平練習接前面例題，輸入概率分布如下，如果譯碼規(guī)則按照最大似然概率規(guī)則得到如下，求平均錯誤譯碼概率。21計算技巧：去掉信道矩陣中每行被譯碼的值，每行乘以p(ai)，各行結(jié)果相加7.2譯碼規(guī)則選擇準則2013秋季信息1121InfTheory&Coding-張祖平練習接前面例題，輸入概率分布如下，如果譯碼規(guī)則按照最大后驗概率規(guī)則，求譯碼規(guī)則，求平均錯誤譯碼概率。227.2譯碼規(guī)則選擇準則2013秋季信息1122InfTheory&Coding-張祖平練習23所以，輸入不是等概分布時最大似然譯碼準則的平均錯誤概率不是最小。7.2譯碼規(guī)則選擇準則2013秋季信息1123InfTheory&Coding-張祖平7.3信道編碼的編碼原則

對于給定的信源來說，要使其最小平均錯誤譯碼概率繼續(xù)下降，就必須進行信道編碼，以改變信道的統(tǒng)計特性，挖掘和利用信道統(tǒng)計特性對提高通信可靠性的潛力。在消息數(shù)和碼字長度保持不變的條件下，引入“漢明距離”的概念，并以此來挑選碼字。2013秋季信息1124InfTheory&Coding-張祖平若有則選擇譯碼函數(shù)這就是用漢明距離來表述的最大似然譯碼準則。同理可得或7.3信道編碼的編碼原則2013秋季信息1125InfTheory&Coding-張祖平經(jīng)過分析可得：1.要盡量縮短與之間的漢明距離；2.要盡量擴大與之間的漢明距離。7.3信道編碼的編碼原則2013秋季信息1126InfTheory&Coding-張祖平7.4抗干擾信道編碼定理

設(shè)某信道有個輸入符號，個輸出符號，信道容量為。當信道的信息傳輸率時，只要碼長足夠長，總可以在輸入集合中（含有個長度為的碼符號序列），找到（，為任意小的正數(shù)）個碼字，分別代表個等可能性的消息，組成一個信道編碼，選擇相應的譯碼規(guī)則，使信道輸出端的譯碼過程的最小平均錯誤譯碼概率達到任意小。這就是抗干擾信道編碼定理，又稱之為香農(nóng)第二定理。2013秋季信息1127InfTheory&Coding-張祖平

抗干擾信道編碼定理的逆定理，從相反的角度進一步揭示了抗干擾信道編碼定理的內(nèi)涵。在敘述和證明抗干擾編碼定理的逆定理之前，有必要從一般的角度闡明平均錯誤譯碼概率與信道疑義度的內(nèi)在聯(lián)系。著名的費諾（Fano）不等式

7.4抗干擾信道編碼定理2013秋季信息1128InfTheory&Coding-張祖平

抗干擾信道編碼定理的逆定理表明，若某信道有個輸入符號、個輸出符號、信道容量為。如選用碼字個數(shù)(消息數(shù))，即時，則無論碼長有多長，也不可能找到一種編碼，使其平均錯誤譯碼概率任意小。實際上，當選用碼字數(shù)（消息數(shù)），即有時，信道的信息傳輸率（碼率）這表明，信道信息傳輸率已超過了信道容量，這是不可能的。逆定理告訴我們，要使信道的信息傳輸率超過信息容量，而有又要求無錯誤地傳輸消息，這是不可能的。同時也給我們指明，信道容量是在信道中可靠地傳輸信息的最大信息傳輸率。7.4抗干擾信道編碼定理2013秋季信息1129InfTheory&Coding-張祖平7.5分組碼及其檢糾能力一、分組碼的基本概念

由個長度為的符號序列組成的集合，構(gòu)成一個分組碼，代表個長度為的信息序列（信息）。分組碼的編碼問題，實質(zhì)上就是如何從總數(shù)為個長度為的序列中挑選個長度為的序列作為碼字的問題。

2013秋季信息1130InfTheory&Coding-張祖平二、分組碼的檢錯、糾錯能力由碼符號集組成的碼字間漢明距離具有的一般特性（1）具有自主性（2）具有對稱性（3）滿足三角不等式

7.5分組碼及其檢糾能力2013秋季信息1131InfTheory&Coding-張祖平

運用以上三大特性剖析由組成的分組碼的檢糾能力與碼字間漢明距離之間的內(nèi)在聯(lián)系：1.分組碼能發(fā)現(xiàn)個錯誤的充分必要條件是分組碼的個碼字中任意兩個碼字個之間的漢明距離2.分組碼能自動糾正個錯誤的充分必要條件是分組碼中任意兩個碼字和之間的漢明距離

7.5分組碼及其檢糾能力2013秋季信息1132InfTheory&Coding-張祖平3.分組碼能自動糾正個錯誤，同時又能發(fā)現(xiàn)個錯誤的充分必要條件是分組碼中任意兩個碼字和之間的漢明距離把由組成的分組碼的個長度為的碼字間的個漢明距離的最小值稱之為這個分組碼的最小漢明距離。

7.5分組碼及其檢糾能力2013秋季信息1133InfTheory&Coding-張祖平由以上討論，可得一下結(jié)論：1.若，則分組碼具有發(fā)現(xiàn)個錯誤的檢錯能力；2.若，則分組碼具有自動糾正個錯誤的糾錯能力；3.若，則分組碼具有自動糾正個錯誤，同時發(fā)現(xiàn)個錯誤的檢、糾錯誤能力。

7.5分組碼及其檢糾能力2013秋季信息1134InfTheory&Coding-張祖平7.6線性分組碼的代數(shù)結(jié)構(gòu)

1.群

2.子群

3.域

4.線性空間及子空間

2013秋季信息1135InfTheory&Coding-張祖平7.7簡單重復編碼一般信道傳輸時都會產(chǎn)生錯誤，而錯誤概率與譯碼規(guī)則有關(guān)。但當信道給定即信道矩陣給定，不論選擇什么譯碼規(guī)PE總不會趨于零從而消除錯誤，那么如何減少錯誤概率呢？下邊討論通過編碼方法來降低錯誤概率，以最簡單的簡單重復編碼（隨機編碼）為例，針對最簡單等概率二元對稱信道。36例：對于二元對稱信道譯碼規(guī)則：平均錯誤概率(假設(shè)輸入等概時)：01010.990.990.010.012013秋季信息1136InfTheory&Coding-張祖平最簡單的思路：冗余，重復待發(fā)送的內(nèi)容，出錯了重發(fā)37沒有使用的碼字001010011100101110用作消息的碼字000111輸出端接收序列000001010011100101110111二元對稱信道的三次擴展信道01011-P=0.990.990.01P=0.017.7簡單重復編碼2013秋季信息1137InfTheory&Coding-張祖平這時信道矩陣為：假設(shè)輸入等概率，根據(jù)最大似然譯碼準則，可得譯碼函數(shù)為：F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=11138平均錯誤概率，大大減小，降低了兩個數(shù)量級7.7簡單重復編碼2013秋季信息1138InfTheory&Coding-張祖平利用重復發(fā)送信源消息進行信道編碼，從而降低譯碼錯誤概率，這種信道編碼方式稱為“簡單重復編碼”也叫“隨機編碼”進一步分析信道隨機編碼如果我們不選擇000和111呢？，假設(shè)我們選擇000代表0，001代表1譯碼規(guī)則通過最大似然譯碼準則可以得到：F(000)=000F(010)=000F(100)=000F(110)=000F(001)=000F(011)=001F(101)=001F(111)=001為什么第二種譯碼規(guī)則的錯誤率會提升呢？這表明擴展后8個符號中選擇2個也是有技巧的。000和111任何一位變化，都非常明顯，而第二次選擇的000和001太“像”了。再思考一下，如果我們選001和110作為輸入，平均錯誤譯碼概率會如何？為什么呢？397.7簡單重復編碼2013秋季信息1139InfTheory&Coding-張祖平漢明Hamming距離。長度為n的兩個符號序列(碼字)ai和bj之間的距離是指ai和bj之間對應位置上不同碼元的個數(shù)，用符號D(ai，bj)表示。這種碼字距離通常稱為漢明距離。在某一碼書C中，任意兩個碼字Ci和Cj的漢明距離的最小值稱為該碼的最小漢明距離。在任一碼書中，碼的最小距離dmin與該碼的譯碼錯誤概率有關(guān)。407.7簡單重復編碼2013秋季信息1140InfTheory&Coding-張祖平41碼A碼B碼C碼D碼字00011100001110111000000101010000000011011011111010消息數(shù)M2444最小漢明距dmin3213錯誤概率(最大似然譯碼規(guī)則)dmin越大，Pe越小，在M相同的情況下，dmin越大，Pe也越小。碼書中最小距離大，受到干擾后不容易把一個碼字錯為另一個碼字，因而錯誤概率小。所以在選擇編碼規(guī)則時，要盡量使碼字之間距離越大越好。7.7簡單重復編碼2013秋季信息1141InfTheory&Coding-張祖平最小漢明距離譯碼準則從碼書中選擇輸入時用dmin最大為準則，那么得到輸出時呢？

若ai和bj

之間的距離為D(ai,bj)記為Dij，它表示傳輸過程中ai傳輸?shù)絙j

，有Dij

個位置發(fā)生了錯誤，(n-Dij)個位置沒有錯誤。通常（p＜1/2時），Dij越大，P(bj/ai)越小，Dij越小P(bj/ai)越大將最大似然譯碼準則與漢明距離連系起來了42當信源等概分布時，可選擇譯碼函數(shù)：并滿足：這樣定義的譯碼規(guī)則稱為最大似然概率準則7.7簡單重復編碼2013秋季信息1142InfTheory&Coding-張祖平最小漢明距離譯碼準則最大似然譯碼準則可用漢明距離表示為選擇譯碼函數(shù)使之滿足即滿足它稱為最小距離譯碼準則。在二元對稱信道中它等價與最大似然譯碼準則，也就是收到一個碼字后，把它譯成與它最近的輸入碼字，這樣可以使平均錯誤概率最小。437.7簡單重復編碼2013秋季信息1143InfTheory&Coding-張祖平練習設(shè)某二元碼為C={11100,01001,10010,00111}，計算此碼的最小距離

dmin；采用最小距離譯碼準則，試問接收序列10000，01100和00100應譯成什么碼字？44（1）此碼字的最小距離dmin=3；（2）采用最小距離譯碼，

10000應譯成10010；

01100應譯成11100；

00100譯成11100、00111均可；7.7簡單重復編碼2013秋季信息1144InfTheory&Coding-張祖平7.8香農(nóng)第二定理信息傳速率很顯然有效性和可靠性是一對矛盾。以簡單重復編碼為例，重復次數(shù)多，N變大，錯誤譯碼概率就會變小，可是R也會變小。以簡單重復編碼為例，M的大小也會影響R。M大，R會變大，但是錯誤譯碼概率也會變大。如何選擇合適的M和N，也就是信道編碼和譯碼方法，讓R保持在一定水平，同時由能讓Pe盡量?。繌睦碚撋线@是可能的，這就是香農(nóng)第二基本定理。452013秋季信息1145InfTheory&Coding-張祖平香農(nóng)第二定理（抗干擾信道編碼定理）當信道的信息傳輸率R小于信道容量C時，只要信道編碼的碼長N足夠長，總可以在輸入集合RN個碼字中找到M個碼字，組成一個信道編碼，選擇相應的譯碼規(guī)則，使????達到任意小。也就是說：總可以找到一種抗干擾信道編碼，只要碼長N夠長，他的最小平均錯誤譯碼概率????可以達到任意小，信道的信息傳輸率R可以無限接近于C。香農(nóng)第二定理（抗干擾信道編碼定理）逆定理當信息傳輸率R>C信道容量時，則無論碼長N多長，總找不到一種編碼使信道輸出端的平均錯誤譯碼概率達到任意小。467.8香農(nóng)第二定理2013秋季信息1146InfTheory&Coding-張祖平香農(nóng)第二定理（抗干擾信道編碼定理）這個定理是一個存在定理，它沒有給出一個具體可構(gòu)造的編碼方法，它有助于指導各種通信系統(tǒng)的設(shè)計有助于評價各種系統(tǒng)及編碼的效率。在它的指導下，人們設(shè)計出了很多有效又可靠的信道編碼方法。常用的信道編碼有線性分組碼漢明碼循環(huán)碼卷積碼477.8香農(nóng)第二定理2013秋季信息1147InfTheory&Coding-張祖平7.9標準陣列與譯碼表

上表構(gòu)成的陣列，稱為線性分組碼的“標準陣列”。2013秋季信息1148InfTheory&Coding-張祖平

把標準陣列中個陪集首和由所得相對應的伴隨式按相對應的位置排成下表所示的“譯碼表”。

陪集首

伴隨式7.9標準陣列與譯碼表2013秋季信息1149InfTheory&Coding-張祖平“譯碼表”譯碼的方法只須存儲個陪集首和相應的個伴隨式。而“標準陣列”譯碼方法必須存儲個重矢量，特別當足夠大時，這種譯碼方法就會顯得很繁瑣，所需譯碼設(shè)備就可能十分龐大。顯然，“譯碼表”譯碼方法比“標準陣列”譯碼方法簡單得多，而且易于具體操作。7.9標準陣列與譯碼表2013秋季信息1150InfTheory&Coding-張祖平

一般以“譯碼表”中各陪集首的總重量作為衡量一個線性分組碼的可靠性高低的標準。總重量越小，最小平均錯誤譯碼概率越小；總重量越大，最小平均錯誤譯碼概率就越大。我們把結(jié)構(gòu)相同的各種線性分組碼中陪集首總重量最小的線性分組碼，稱為這種結(jié)構(gòu)的線性分組碼中的“最優(yōu)碼”。7.9標準陣列與譯碼表2013秋季信息1151InfTheory&Coding-張祖平7.10檢糾能力與一致校驗矩陣的關(guān)系

以為一致校驗矩陣的線性分組碼能糾正個錯誤的充分必要條件是，中任意列線性獨立。結(jié)論表明，線性分組碼的一致檢驗矩陣的結(jié)構(gòu)，與線性分組碼的最小漢明重量存在內(nèi)在的聯(lián)系。由一致校驗矩陣的結(jié)構(gòu)特點，可直接判斷相應的線性分組碼具有的檢糾能力。

2013秋季信息1152InfTheory&Coding-張祖平7.11完備碼

由于線性分組碼用“譯碼表”譯碼時，能糾正的錯誤就是各種陪集首，所以，如果小于或等于個錯誤的全部錯誤圖樣數(shù)正好等于陪集首的總數(shù)，即那么，陪集首就是小于或等于個錯誤的全部錯誤圖樣。我們把滿足上式的線性分組碼稱為“完備碼”。

2013秋季信息1153InfTheory&Coding-張祖平