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

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

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

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

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

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

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

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

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

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

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

確定一個(gè)惟一的輸入符號(hào)ai

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

rs

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

，則譯為ai

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

條件下譯碼的條件錯(cuò)誤概率（后驗(yàn)概率）為：（e代表任何除ai外可能的輸入符號(hào)）：107.1譯碼規(guī)則2013秋季信息1110InfTheory&Coding-張祖平譯碼規(guī)則的定義每收到一個(gè)符號(hào)的平均正確譯碼概率，是輸出隨機(jī)變量Y的概率空間的統(tǒng)計(jì)平均值。每收到一個(gè)符號(hào)的平均錯(cuò)誤譯碼概率，是輸出隨機(jī)變量Y的概率空間的統(tǒng)計(jì)平均值。11在信道傳輸概率確定情況下，顯然，不同的譯碼規(guī)則會(huì)出現(xiàn)不同的平均錯(cuò)誤譯碼概率如何選擇譯碼規(guī)則，讓Perror簡寫成Pe更小呢？Pright簡寫成Pr更大呢??7.1譯碼規(guī)則2013秋季信息1111InfTheory&Coding-張祖平7.2譯碼規(guī)則選擇準(zhǔn)則信源和信道概率復(fù)習(xí)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-張祖平最大后驗(yàn)概率準(zhǔn)則(最小錯(cuò)誤概率準(zhǔn)則)要使平均錯(cuò)誤譯碼概率Pe最小，就要平均正確譯碼概率Pr最大。通過信源先驗(yàn)概率和信道矩陣中條件概率，計(jì)算出每個(gè)輸出符號(hào)概率，和每個(gè)輸出符號(hào)判斷輸入符號(hào)的后驗(yàn)概率。后驗(yàn)概率是我們的依據(jù)，似乎信源先驗(yàn)概率，信道矩陣中條件概率都與譯碼規(guī)則無直接關(guān)系。針對(duì)某個(gè)bj，選擇r個(gè)后驗(yàn)概率p(ai/bj)中最大的值時(shí)對(duì)應(yīng)的a*，就可以使信道錯(cuò)誤概率最小，這種譯碼規(guī)則稱“最大后驗(yàn)概率準(zhǔn)則”13即選擇譯碼函數(shù)：并滿足:7.2譯碼規(guī)則選擇準(zhǔn)則2013秋季信息1113InfTheory&Coding-張祖平平均錯(cuò)誤譯碼概率與平均正確譯碼概率的計(jì)算14因此，使用最大后驗(yàn)概率準(zhǔn)則可以讓平均錯(cuò)誤譯碼概率最小，而且只取決于給定信源空間和給定信道矩陣，也就是說，信源和信道給定時(shí)，通信的可靠性最高程度就已經(jīng)確定。表示對(duì)輸入符號(hào)集中除F（bj）=a*以外的所有元素求和。7.2譯碼規(guī)則選擇準(zhǔn)則2013秋季信息1114InfTheory&Coding-張祖平舉例：設(shè)有一離散信道，其信道矩陣為，當(dāng)信源X的概率分布為р(a1)＝2/3，р(a2)＝р(a3)＝1/6時(shí)，按最大后驗(yàn)概率準(zhǔn)則選擇譯碼函數(shù)，并計(jì)算其平均錯(cuò)誤譯碼概率Pemin．157.2譯碼規(guī)則選擇準(zhǔn)則a1a2a3b1b2b32013秋季信息1115InfTheory&Coding-張祖平最大似然概率準(zhǔn)則16當(dāng)信源等概分布時(shí)，可選擇譯碼函數(shù)：并滿足：這樣定義的譯碼規(guī)則稱為最大似然概率準(zhǔn)則最大似然譯碼準(zhǔn)則的方法是收到一個(gè)bj

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.群

2.子群

3.域

4.線性空間及子空間

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

若ai和bj

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

，有Dij

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

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

10000應(yīng)譯成10010；

01100應(yīng)譯成11100；

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

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

把標(biāo)準(zhǔn)陣列中個(gè)陪集首和由所得相對(duì)應(yīng)的伴隨式按相對(duì)應(yīng)的位置排成下表所示的“譯碼表”。

陪集首

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

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

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

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

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

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