7.1信道編碼的基本概念7.1.1基本概念7.1.2平均錯(cuò)誤概率7.1.3費(fèi)諾不等式7.2譯碼準(zhǔn)則7.2.1最大后驗(yàn)概率譯碼準(zhǔn)則7.2.2最大似然譯碼準(zhǔn)則7.3編碼原則7.3.1編碼的功能7.3.2最小漢明距離譯碼準(zhǔn)則7.3.3編碼原則7.4抗干擾信道編碼定理7.4.1抗干擾信道編碼定理7.4.2抗干擾信道編碼定理的逆定理第7章糾錯(cuò)編碼原理7.1信道編碼的基本概念第7章糾錯(cuò)編碼原理17.1信道編碼基本概念7.1.1基本概念無失真信源編碼是在無噪信道的背景下，用無噪信道的輸入符號(hào)集當(dāng)作碼符號(hào)集，對(duì)信源符號(hào)或符號(hào)序列編出的惟一可譯碼，使信源符號(hào)適合信道的傳輸，以保證在無噪信道中無失真地傳輸信源發(fā)生的消息。同時(shí)還要求編碼是有效的，使每一信源符號(hào)所需的平均碼符號(hào)數(shù)盡量的小。無噪信道問題，實(shí)質(zhì)上是信源本身的問題。無失真信源編碼，實(shí)際上只是用無噪信道的輸入符號(hào)集作為碼符號(hào)集，對(duì)信源符號(hào)的形式作一一對(duì)應(yīng)的變換，并且充分而合理地利用和挖掘信源本身的統(tǒng)計(jì)特性，以期得到盡可能短的平均碼長。無失真信源編碼實(shí)質(zhì)上是信源領(lǐng)域自身的問題。信道編碼的任務(wù)就是構(gòu)造出以最小多余度代價(jià)換取最大抗干擾性能的“好碼”。7.1信道編碼基本概念7.1.1基本概念2一個(gè)好的錯(cuò)誤控制編碼方案的目標(biāo)是:(1)用可以糾正的錯(cuò)誤個(gè)數(shù)來衡量的糾錯(cuò)能力;(2)快速有效地對(duì)消息進(jìn)行編碼;(3)快速有效地對(duì)接收到的消息進(jìn)行譯碼;(4)單位時(shí)間內(nèi)所能傳輸?shù)男畔⒈忍財(cái)?shù)盡量大(即有少的冗余度)。一個(gè)好的錯(cuò)誤控制編碼方案的目標(biāo)是:37.1.2平均錯(cuò)誤概率為了達(dá)到信息傳輸?shù)哪康?，人們總是根?jù)一定的判決準(zhǔn)則，設(shè)計(jì)一個(gè)單值函數(shù)使每一種可能的輸出符號(hào)與一個(gè)唯一的輸入符號(hào)一一對(duì)應(yīng)，則函數(shù)就被稱為譯碼函數(shù)或譯碼規(guī)則。若信道對(duì)輸入符號(hào)集、輸出符號(hào)集分別為

一共可構(gòu)成種不同的譯碼規(guī)則。例如二進(jìn)制對(duì)稱信道，輸入符號(hào)集及輸出符號(hào)集均為則可構(gòu)成種譯碼規(guī)則。即譯碼規(guī)則(1)：F(0)=0,F(1)=0;譯碼規(guī)則(2)：F(0)=0,F(1)=1;譯碼規(guī)則(3)：F(0)=1,F(1)=0；譯碼規(guī)則(4)：F(0)=1,F(1)=1。7.1.2平均錯(cuò)誤概率4如二進(jìn)制對(duì)稱信道傳遞矩陣

采取譯碼規(guī)則(2)：則信道輸出端出現(xiàn)“0”和“1”的正確譯碼概率分別是在這種譯碼規(guī)則下，從統(tǒng)計(jì)的觀點(diǎn)看，信道輸出端出現(xiàn)四個(gè)符號(hào)“0”(或“1”)，只能有一個(gè)“0”(或“l(fā)”)能得到正確譯碼。 采用譯碼規(guī)則(3)。信道輸出端出現(xiàn)“0”和“1”的正確譯碼概率分別是

在這種譯碼規(guī)則下，從統(tǒng)計(jì)的觀點(diǎn)看，信道輸出端出現(xiàn)四個(gè)符號(hào)“0”(或“l(fā)”)，就有三個(gè)能得到正確譯碼?？梢姴煌淖g碼規(guī)則確實(shí)會(huì)引起不同的可靠程度。在一個(gè)完整的信息傳輸過程中，譯碼規(guī)則對(duì)信息傳輸?shù)目煽啃杂兄卮笥绊?。因此，有必要深入討論譯碼規(guī)則與信息傳輸可靠性之間的關(guān)系。如二進(jìn)制對(duì)稱信道傳遞矩陣5

在譯碼過程中，若確定了譯碼規(guī)則，那么當(dāng)信道輸出端出現(xiàn)某輸出符號(hào)，則一定按規(guī)定好的譯碼規(guī)則譯成相應(yīng)的輸入符號(hào),顯然，這就是正確譯碼；否則為錯(cuò)誤譯碼。信道輸出端收到某符號(hào)后錯(cuò)誤譯碼的概率

對(duì)于信息傳輸系統(tǒng)來說，人們的興趣不僅僅停留在個(gè)別的輸出符號(hào)的正確或錯(cuò)誤譯碼概率的表述上，更重要的是要描述在信道的輸出端，每收到一個(gè)符號(hào)的平均正確譯碼或平均錯(cuò)誤譯碼的概率。也就是從平均的意義上來說，在信道輸出端每收到一個(gè)符號(hào)，發(fā)生正確譯碼或錯(cuò)誤譯碼的可能性的大小。同樣，由(7-4)式可知，在信道輸出端，每收到輸出Y中一個(gè)符號(hào)的平均錯(cuò)誤譯碼概率應(yīng)該是(7-4)式所示后驗(yàn)概率在信道輸出隨機(jī)變量Y的概率空間中的統(tǒng)計(jì)平均值，即在譯碼過程中，若確定了譯碼規(guī)則，那么當(dāng)信道輸出端出現(xiàn)6說明:(7-5)式所示的平均錯(cuò)誤譯碼概率，表示在信道輸出端，平均每收到一個(gè)符號(hào)，產(chǎn)生錯(cuò)誤譯碼可能性的大小。平均錯(cuò)誤譯碼概率越大，表示在信道輸出端平均每收到一個(gè)符號(hào)產(chǎn)生錯(cuò)誤譯碼的可能性越大；平均錯(cuò)誤譯碼概率越小，表示在信道輸出端平均每收到一個(gè)符號(hào)產(chǎn)生錯(cuò)誤譯碼的可能性越小。顯然，產(chǎn)生錯(cuò)誤譯碼的可能性越大，意味著信息傳輸?shù)目煽啃栽讲睿划a(chǎn)生錯(cuò)誤譯碼的可能性越小，意味著信息傳輸?shù)目煽啃暂^好。所以，可把平均錯(cuò)誤譯碼概率當(dāng)作衡量信息傳輸?shù)目煽啃缘臉?biāo)準(zhǔn)。(7-5)式進(jìn)一步指明了，平均錯(cuò)誤譯碼概率，取決于信道輸出隨機(jī)變量Y的概率空間、信道的后驗(yàn)概率分布以及人們規(guī)定好的譯碼規(guī)則。那么，對(duì)于傳遞概率固定的給定信道來說，當(dāng)信道的輸入符號(hào)，即信源的輸出符號(hào)的概率分布確定后，不同的譯碼規(guī)則就有不同的平均錯(cuò)誤譯碼概率。譯碼規(guī)則是人們根據(jù)一定的準(zhǔn)則予以選擇的，所以選擇合適的譯碼規(guī)則，就可成為降低平均錯(cuò)誤譯碼概率，提高信息傳輸有效性的一種可控制的手段。說明:77.1.3費(fèi)諾不等式著名的費(fèi)諾(Fano)不等式正確地描述了平均錯(cuò)誤譯碼概率與信道疑義度H(X︱Y)的內(nèi)在聯(lián)系，即

費(fèi)諾不等式并沒有指定在什么樣的準(zhǔn)則下選擇譯碼規(guī)則,所以，雖然平均錯(cuò)誤譯碼概率與選擇的譯碼規(guī)則有關(guān)，但不論采用什么準(zhǔn)則選擇譯碼規(guī)則，費(fèi)諾不等式(7-6)都是普遍成立的。費(fèi)諾不等式(7-6)表明，收到信道輸出隨機(jī)變量后，對(duì)輸入隨機(jī)變量仍然存在的平均不確定性H(X︱Y)由二部分組成：第一部分是收到輸出隨機(jī)變量后，按選則的譯碼規(guī)則譯碼時(shí)，是否產(chǎn)生錯(cuò)誤譯碼的平均不確定性H()；第二部分是當(dāng)平均錯(cuò)誤譯碼概率為時(shí)，到底是哪一個(gè)信源符號(hào)被錯(cuò)誤譯碼的最大平均不確定性1oga(r-1)。7.1.3費(fèi)諾不等式87.2譯碼準(zhǔn)則7.2.1最大后驗(yàn)概率譯碼準(zhǔn)則按什么準(zhǔn)則來選擇合適的譯碼規(guī)則，使其平均錯(cuò)誤譯碼概率達(dá)到最小，是提高由給定信源、給定信道組成的信息傳輸系統(tǒng)的可靠性的關(guān)鍵問題。設(shè)基本離散信道傳遞矩陣為由可得個(gè)確定的后驗(yàn)概率,同樣把這確定的后驗(yàn)概率排列成一個(gè)后驗(yàn)概率矩陣7.2譯碼準(zhǔn)則7.2.1最大后驗(yàn)概率譯碼準(zhǔn)則9后驗(yàn)概率矩陣由給定的信源X的概率分布和信道的傳遞概率，可求得信道輸出隨機(jī)變量Y的s個(gè)概率分量

再把注意力回到(7-5)式所示的平均錯(cuò)誤譯碼概率上來，(7-5)式指明了，平均錯(cuò)誤譯碼概率，取決于信道輸出隨機(jī)變量Y的概率空間、信道的后驗(yàn)概率分布以及人們規(guī)定好的譯碼規(guī)則。(7-8)和(7-10)表明，對(duì)于給定信源和給定信道來說，后驗(yàn)概率和信道輸出隨機(jī)變量Y的概率分布也都是固定不變的。顯然，要使平均錯(cuò)誤譯碼概率最小，勢必要使達(dá)到最大。勢必要使達(dá)到最大。后驗(yàn)概率矩陣10若把這個(gè)最大者所對(duì)應(yīng)的信源符號(hào)記為，即有因此必須選擇譯碼規(guī)則

這就是最大后驗(yàn)概率譯碼準(zhǔn)則。由最大后驗(yàn)概率譯碼函數(shù)構(gòu)成的譯碼規(guī)則，一定能使平均錯(cuò)誤譯碼概率達(dá)到最小值由此可見，采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則，一定能使平均錯(cuò)誤譯碼概率達(dá)到最小值。而最小平均錯(cuò)誤譯碼概率取決于給定信源和給定信道的統(tǒng)計(jì)特性。這就是說，當(dāng)信源和信道給定后，信息傳輸?shù)目煽啃宰罡叱潭纫簿痛_定了。而這個(gè)最高的可靠程度，必須用最大后驗(yàn)概率準(zhǔn)則來選則譯碼規(guī)則，才能得以實(shí)現(xiàn)。編碼理論第7章課件11[例7-1]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為試選擇譯碼規(guī)則，使其平均錯(cuò)誤譯碼概率達(dá)到最小值,并計(jì)算其值?解:因信道輸入符號(hào)非先驗(yàn)等概，故只能采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則。由(7-8)式和(7-9)式計(jì)算出后驗(yàn)概率矩陣考慮信道輸出符號(hào)與信道輸入符號(hào)一一對(duì)應(yīng)，選擇譯碼譯碼規(guī)則采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則的最小平均錯(cuò)誤譯碼概率[例7-1]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為127.2.2最大似然譯碼準(zhǔn)則若要用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則,則首先要根據(jù)給定的信源統(tǒng)計(jì)特性和給定的信道統(tǒng)計(jì)特性，由(7-8)式算出與有關(guān)的r個(gè)后驗(yàn)概率。顯然，這會(huì)給具體操作帶來一些困難和不方便。在某些特定條件下，信源等概時(shí),最大后驗(yàn)概率準(zhǔn)則能得到一定程度的簡化，因?yàn)閯t可有選擇譯碼規(guī)則這種選擇譯碼規(guī)則的準(zhǔn)則，稱之為最大似然譯碼準(zhǔn)則。顯然，最大似然準(zhǔn)則是在信道輸入符號(hào)(信源輸出符號(hào))先驗(yàn)等概特定條件下的最大后驗(yàn)概率準(zhǔn)則，其平均錯(cuò)誤譯碼概率同樣達(dá)到最小值，由(7-16)和(7-17)式，得7.2.2最大似然譯碼準(zhǔn)則13[例7-2]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為試選擇譯碼規(guī)則，使其平均錯(cuò)誤譯碼概率達(dá)到最小值,并計(jì)算其值?解:因信道輸入符號(hào)先驗(yàn)等概，故采用最大似然準(zhǔn)則選擇譯碼規(guī)則。按最大似然準(zhǔn)則得到譯碼規(guī)則,并考慮信道輸出符號(hào)與信道輸入符號(hào)一一對(duì)應(yīng)，選擇譯碼函數(shù)所以，在采用最大似然準(zhǔn)則選擇譯碼規(guī)則時(shí)，就不必像一般的最大后驗(yàn)概率準(zhǔn)則那樣，由給定信道矩陣中的信道傳遞概率(前向概率)換算成后驗(yàn)概率(后向概率)，再比較后驗(yàn)概率的大小來選擇譯碼規(guī)則了。這就是最大似然準(zhǔn)則比最大后驗(yàn)概率準(zhǔn)則的方便之處。采用最大似然準(zhǔn)則選擇譯碼規(guī)則的最小平均錯(cuò)誤譯碼概率的具體計(jì)算值[例7-2]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為147.3編碼原則7.3.1編碼的功能下面以二元對(duì)稱信道為例說明編碼的作用。[例7-2]二元對(duì)稱離散無記憶信道的信道矩陣

設(shè)p=0.01,,輸入符號(hào)“0”和“1”先驗(yàn)等慨，分析其直接傳輸及編碼傳輸?shù)男Ч?。解：因?yàn)樾旁聪闰?yàn)等慨，則采用最大似然準(zhǔn)則選擇譯碼規(guī)則平均錯(cuò)誤譯碼概率必定達(dá)到最小值0.01；

7.3編碼原則7.3.1編碼的功能15對(duì)信道輸入符號(hào)“0”和“1”進(jìn)行重復(fù)編碼，把“0”變成“000”，把“1”變成“111”。這時(shí)，采用最大似然準(zhǔn)則選擇譯碼規(guī)則，最小平均錯(cuò)誤譯碼概率

若選“000”代表信源符號(hào)“0”；選“001”代表信源符號(hào)“1”，這種譯碼規(guī)則的最小平均錯(cuò)誤譯碼概率0.01。在隨機(jī)編碼中碼字的不同選擇，會(huì)導(dǎo)致不同的最小平均錯(cuò)誤譯碼概率，那么應(yīng)遵循什么原則挑選碼字，才能得到盡可能小的最小平均錯(cuò)誤譯碼概率呢?下面討論這個(gè)問題。對(duì)信道輸入符號(hào)“0”和“1”進(jìn)行重復(fù)編碼，把167.3.2最小漢明距離譯碼準(zhǔn)則簡單重復(fù)編碼減少平均錯(cuò)誤譯碼概率是以降低信息傳輸率R作為代價(jià)的。即“犧牲有效性，換取可靠性”。現(xiàn)在要討論的問題是,在隨機(jī)編碼中，當(dāng)消息數(shù)M和碼字長度N保持不變的條件下，即信道信息傳輸率(碼率)保持不變條件下，應(yīng)遵循什么原則挑選碼字，才能得到盡可能小的最小平均錯(cuò)誤譯碼概率?信道的輸入端有M個(gè)長度為N的由“0”和“1”組成的碼符號(hào)序列(碼字),信道的輸出端有個(gè)長度為N的碼符號(hào)序列。離散無記憶信道的N次擴(kuò)展信道有個(gè)傳遞概率，它們是7.3.2最小漢明距離譯碼準(zhǔn)則17(7-23)式可由漢明距離表示為在M個(gè)消息先驗(yàn)等概的條件下，采用最大似然準(zhǔn)則選擇譯碼規(guī)則。對(duì)來說，若有即編碼理論第7章課件18考慮到在一般情況下都有，且，所以(7-26)式又可改寫為

則選擇譯碼規(guī)則(7-27)和(7-28)式就是用漢明距離“語言”表述的最大似然準(zhǔn)則。它表明，在信道M個(gè)輸入消息先驗(yàn)等概的條件下，離散無記憶信道的N次擴(kuò)展信道的某一輸出序列，翻譯成與的漢明距離中的最小者所對(duì)應(yīng)的輸入消息,則其平均錯(cuò)誤譯碼概率達(dá)到最小值。(7-27)和式(7-28)意味著把翻譯成與之最相似的輸入消息。這就是為什么把這個(gè)準(zhǔn)則稱之為“最大似然”準(zhǔn)則的由來。編碼理論第7章課件19(7-21)式所示的采用最大似然準(zhǔn)則選擇譯碼規(guī)則所得的最小平均錯(cuò)誤譯碼概率，也可用漢明距離表示為

由(7-16)式可知，采用最大似然準(zhǔn)則選擇譯碼規(guī)則所得的最小平均錯(cuò)誤譯碼概率還可表示為另一種形式(7-21)式所示的采用最大似然準(zhǔn)則選擇譯碼規(guī)則20(7-29)和(7-30)式表明，采用最大似然準(zhǔn)則選譯碼規(guī)則所得的最小平均錯(cuò)誤譯碼概率取決于：(1)先驗(yàn)等概的消息數(shù)M；(2)隨機(jī)編碼的碼字長度N；(3)離散無記憶信道N次擴(kuò)展信道的輸出序列與譯碼函數(shù)規(guī)定的翻譯碼字之間的漢明距離;(4)離散無記憶信道N次擴(kuò)展信道的輸出序列與除了翻譯碼字以外的其它碼字之間的漢明距離。那么，在保持一定的信道的信息率，即碼率R的前提下(即保持先驗(yàn)等概的消息數(shù)M和碼字長度N不變的前提下)，最小平均錯(cuò)誤譯碼概率就取決于漢明距離。信道編碼的任務(wù)就是保持碼率R在一定水平(保持M和N不變)的前提下，采用正確的方法選擇M個(gè)碼字，使最小平均錯(cuò)誤譯碼概率盡量小。(7-29)和(7-30)式就指出了正確選擇M個(gè)碼字，使平均錯(cuò)誤譯碼概率達(dá)到最小所必須遵循的原則。那么應(yīng)該道循什么樣的原則，才能恰當(dāng)選擇M個(gè)碼字呢?下面介紹這個(gè)問題。(7-29)和(7-30)式表明，采用最大似然217.3.3編碼原則假定二進(jìn)制對(duì)稱信道(BSC)的正確傳遞概率遠(yuǎn)大于錯(cuò)誤傳遞概率。在這樣的假定下，由(7-29)式可知，N次擴(kuò)展離散無記億信道的輸出序列與除了譯碼函數(shù)規(guī)定的相應(yīng)碼字以外的(M一1)個(gè)碼字的漢明距離越大，其最小平均錯(cuò)誤譯碼概率就越小。即與這(M－1)個(gè)其它不對(duì)應(yīng)的碼字之間越不相似，其最小平均錯(cuò)誤譯碼概率就可越小。另一方面，由(7-30)式可知，N次擴(kuò)展離散無記憶信道的輸出序列與譯碼函數(shù)規(guī)定的相應(yīng)碼字之間的漢明距離越小，其最小平均錯(cuò)誤譯碼概率就越小。即與譯碼函數(shù)規(guī)定的碼字之間越相似，其最小平均錯(cuò)誤譯碼概率就越小。7.3.3編碼原則22結(jié)論：如消息數(shù)M和碼字長度N保持不變，信道信息傳輸率(碼率)保持不變，同時(shí)又要使最小平均錯(cuò)誤譯碼概率盡量小。一方面要盡量縮短N(yùn)次擴(kuò)展信道的輸出序列與譯碼函數(shù)規(guī)定的翻譯碼字之間的漢明距離;另一方面又要盡量擴(kuò)大N次擴(kuò)展信道的輸出序列與除了翻譯碼字以外的其它碼字之間的漢明距離。那么，為了要同時(shí)滿足這兩方面的要求，在從個(gè)長度為N的碼符號(hào)序列中選擇M個(gè)作為代表消息的碼字的選擇過程中，必須遵循這樣的原則：M個(gè)碼字中，任何兩個(gè)不同的碼字間的漢明距離要盡量大。換句話說，挑選出來的M個(gè)碼字之間，越不相似越好。這就是隨機(jī)編碼必須遵循的原則。結(jié)論：如消息數(shù)M和碼字長度N保持不變，信道信息傳輸率(碼率)23編碼理論第7章課件247.1信道編碼的基本概念7.1.1基本概念7.1.2平均錯(cuò)誤概率7.1.3費(fèi)諾不等式7.2譯碼準(zhǔn)則7.2.1最大后驗(yàn)概率譯碼準(zhǔn)則7.2.2最大似然譯碼準(zhǔn)則7.3編碼原則7.3.1編碼的功能7.3.2最小漢明距離譯碼準(zhǔn)則7.3.3編碼原則7.4抗干擾信道編碼定理7.4.1抗干擾信道編碼定理7.4.2抗干擾信道編碼定理的逆定理第7章糾錯(cuò)編碼原理7.1信道編碼的基本概念第7章糾錯(cuò)編碼原理257.1信道編碼基本概念7.1.1基本概念無失真信源編碼是在無噪信道的背景下，用無噪信道的輸入符號(hào)集當(dāng)作碼符號(hào)集，對(duì)信源符號(hào)或符號(hào)序列編出的惟一可譯碼，使信源符號(hào)適合信道的傳輸，以保證在無噪信道中無失真地傳輸信源發(fā)生的消息。同時(shí)還要求編碼是有效的，使每一信源符號(hào)所需的平均碼符號(hào)數(shù)盡量的小。無噪信道問題，實(shí)質(zhì)上是信源本身的問題。無失真信源編碼，實(shí)際上只是用無噪信道的輸入符號(hào)集作為碼符號(hào)集，對(duì)信源符號(hào)的形式作一一對(duì)應(yīng)的變換，并且充分而合理地利用和挖掘信源本身的統(tǒng)計(jì)特性，以期得到盡可能短的平均碼長。無失真信源編碼實(shí)質(zhì)上是信源領(lǐng)域自身的問題。信道編碼的任務(wù)就是構(gòu)造出以最小多余度代價(jià)換取最大抗干擾性能的“好碼”。7.1信道編碼基本概念7.1.1基本概念26一個(gè)好的錯(cuò)誤控制編碼方案的目標(biāo)是:(1)用可以糾正的錯(cuò)誤個(gè)數(shù)來衡量的糾錯(cuò)能力;(2)快速有效地對(duì)消息進(jìn)行編碼;(3)快速有效地對(duì)接收到的消息進(jìn)行譯碼;(4)單位時(shí)間內(nèi)所能傳輸?shù)男畔⒈忍財(cái)?shù)盡量大(即有少的冗余度)。一個(gè)好的錯(cuò)誤控制編碼方案的目標(biāo)是:277.1.2平均錯(cuò)誤概率為了達(dá)到信息傳輸?shù)哪康?，人們總是根?jù)一定的判決準(zhǔn)則，設(shè)計(jì)一個(gè)單值函數(shù)使每一種可能的輸出符號(hào)與一個(gè)唯一的輸入符號(hào)一一對(duì)應(yīng)，則函數(shù)就被稱為譯碼函數(shù)或譯碼規(guī)則。若信道對(duì)輸入符號(hào)集、輸出符號(hào)集分別為

一共可構(gòu)成種不同的譯碼規(guī)則。例如二進(jìn)制對(duì)稱信道，輸入符號(hào)集及輸出符號(hào)集均為則可構(gòu)成種譯碼規(guī)則。即譯碼規(guī)則(1)：F(0)=0,F(1)=0;譯碼規(guī)則(2)：F(0)=0,F(1)=1;譯碼規(guī)則(3)：F(0)=1,F(1)=0；譯碼規(guī)則(4)：F(0)=1,F(1)=1。7.1.2平均錯(cuò)誤概率28如二進(jìn)制對(duì)稱信道傳遞矩陣

采取譯碼規(guī)則(2)：則信道輸出端出現(xiàn)“0”和“1”的正確譯碼概率分別是在這種譯碼規(guī)則下，從統(tǒng)計(jì)的觀點(diǎn)看，信道輸出端出現(xiàn)四個(gè)符號(hào)“0”(或“1”)，只能有一個(gè)“0”(或“l(fā)”)能得到正確譯碼。 采用譯碼規(guī)則(3)。信道輸出端出現(xiàn)“0”和“1”的正確譯碼概率分別是

在這種譯碼規(guī)則下，從統(tǒng)計(jì)的觀點(diǎn)看，信道輸出端出現(xiàn)四個(gè)符號(hào)“0”(或“l(fā)”)，就有三個(gè)能得到正確譯碼?？梢姴煌淖g碼規(guī)則確實(shí)會(huì)引起不同的可靠程度。在一個(gè)完整的信息傳輸過程中，譯碼規(guī)則對(duì)信息傳輸?shù)目煽啃杂兄卮笥绊?。因此，有必要深入討論譯碼規(guī)則與信息傳輸可靠性之間的關(guān)系。如二進(jìn)制對(duì)稱信道傳遞矩陣29

在譯碼過程中，若確定了譯碼規(guī)則，那么當(dāng)信道輸出端出現(xiàn)某輸出符號(hào)，則一定按規(guī)定好的譯碼規(guī)則譯成相應(yīng)的輸入符號(hào),顯然，這就是正確譯碼；否則為錯(cuò)誤譯碼。信道輸出端收到某符號(hào)后錯(cuò)誤譯碼的概率

對(duì)于信息傳輸系統(tǒng)來說，人們的興趣不僅僅停留在個(gè)別的輸出符號(hào)的正確或錯(cuò)誤譯碼概率的表述上，更重要的是要描述在信道的輸出端，每收到一個(gè)符號(hào)的平均正確譯碼或平均錯(cuò)誤譯碼的概率。也就是從平均的意義上來說，在信道輸出端每收到一個(gè)符號(hào)，發(fā)生正確譯碼或錯(cuò)誤譯碼的可能性的大小。同樣，由(7-4)式可知，在信道輸出端，每收到輸出Y中一個(gè)符號(hào)的平均錯(cuò)誤譯碼概率應(yīng)該是(7-4)式所示后驗(yàn)概率在信道輸出隨機(jī)變量Y的概率空間中的統(tǒng)計(jì)平均值，即在譯碼過程中，若確定了譯碼規(guī)則，那么當(dāng)信道輸出端出現(xiàn)30說明:(7-5)式所示的平均錯(cuò)誤譯碼概率，表示在信道輸出端，平均每收到一個(gè)符號(hào)，產(chǎn)生錯(cuò)誤譯碼可能性的大小。平均錯(cuò)誤譯碼概率越大，表示在信道輸出端平均每收到一個(gè)符號(hào)產(chǎn)生錯(cuò)誤譯碼的可能性越大；平均錯(cuò)誤譯碼概率越小，表示在信道輸出端平均每收到一個(gè)符號(hào)產(chǎn)生錯(cuò)誤譯碼的可能性越小。顯然，產(chǎn)生錯(cuò)誤譯碼的可能性越大，意味著信息傳輸?shù)目煽啃栽讲?；產(chǎn)生錯(cuò)誤譯碼的可能性越小，意味著信息傳輸?shù)目煽啃暂^好。所以，可把平均錯(cuò)誤譯碼概率當(dāng)作衡量信息傳輸?shù)目煽啃缘臉?biāo)準(zhǔn)。(7-5)式進(jìn)一步指明了，平均錯(cuò)誤譯碼概率，取決于信道輸出隨機(jī)變量Y的概率空間、信道的后驗(yàn)概率分布以及人們規(guī)定好的譯碼規(guī)則。那么，對(duì)于傳遞概率固定的給定信道來說，當(dāng)信道的輸入符號(hào)，即信源的輸出符號(hào)的概率分布確定后，不同的譯碼規(guī)則就有不同的平均錯(cuò)誤譯碼概率。譯碼規(guī)則是人們根據(jù)一定的準(zhǔn)則予以選擇的，所以選擇合適的譯碼規(guī)則，就可成為降低平均錯(cuò)誤譯碼概率，提高信息傳輸有效性的一種可控制的手段。說明:317.1.3費(fèi)諾不等式著名的費(fèi)諾(Fano)不等式正確地描述了平均錯(cuò)誤譯碼概率與信道疑義度H(X︱Y)的內(nèi)在聯(lián)系，即

費(fèi)諾不等式并沒有指定在什么樣的準(zhǔn)則下選擇譯碼規(guī)則,所以，雖然平均錯(cuò)誤譯碼概率與選擇的譯碼規(guī)則有關(guān)，但不論采用什么準(zhǔn)則選擇譯碼規(guī)則，費(fèi)諾不等式(7-6)都是普遍成立的。費(fèi)諾不等式(7-6)表明，收到信道輸出隨機(jī)變量后，對(duì)輸入隨機(jī)變量仍然存在的平均不確定性H(X︱Y)由二部分組成：第一部分是收到輸出隨機(jī)變量后，按選則的譯碼規(guī)則譯碼時(shí)，是否產(chǎn)生錯(cuò)誤譯碼的平均不確定性H()；第二部分是當(dāng)平均錯(cuò)誤譯碼概率為時(shí)，到底是哪一個(gè)信源符號(hào)被錯(cuò)誤譯碼的最大平均不確定性1oga(r-1)。7.1.3費(fèi)諾不等式327.2譯碼準(zhǔn)則7.2.1最大后驗(yàn)概率譯碼準(zhǔn)則按什么準(zhǔn)則來選擇合適的譯碼規(guī)則，使其平均錯(cuò)誤譯碼概率達(dá)到最小，是提高由給定信源、給定信道組成的信息傳輸系統(tǒng)的可靠性的關(guān)鍵問題。設(shè)基本離散信道傳遞矩陣為由可得個(gè)確定的后驗(yàn)概率,同樣把這確定的后驗(yàn)概率排列成一個(gè)后驗(yàn)概率矩陣7.2譯碼準(zhǔn)則7.2.1最大后驗(yàn)概率譯碼準(zhǔn)則33后驗(yàn)概率矩陣由給定的信源X的概率分布和信道的傳遞概率，可求得信道輸出隨機(jī)變量Y的s個(gè)概率分量

再把注意力回到(7-5)式所示的平均錯(cuò)誤譯碼概率上來，(7-5)式指明了，平均錯(cuò)誤譯碼概率，取決于信道輸出隨機(jī)變量Y的概率空間、信道的后驗(yàn)概率分布以及人們規(guī)定好的譯碼規(guī)則。(7-8)和(7-10)表明，對(duì)于給定信源和給定信道來說，后驗(yàn)概率和信道輸出隨機(jī)變量Y的概率分布也都是固定不變的。顯然，要使平均錯(cuò)誤譯碼概率最小，勢必要使達(dá)到最大。勢必要使達(dá)到最大。后驗(yàn)概率矩陣34若把這個(gè)最大者所對(duì)應(yīng)的信源符號(hào)記為，即有因此必須選擇譯碼規(guī)則

這就是最大后驗(yàn)概率譯碼準(zhǔn)則。由最大后驗(yàn)概率譯碼函數(shù)構(gòu)成的譯碼規(guī)則，一定能使平均錯(cuò)誤譯碼概率達(dá)到最小值由此可見，采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則，一定能使平均錯(cuò)誤譯碼概率達(dá)到最小值。而最小平均錯(cuò)誤譯碼概率取決于給定信源和給定信道的統(tǒng)計(jì)特性。這就是說，當(dāng)信源和信道給定后，信息傳輸?shù)目煽啃宰罡叱潭纫簿痛_定了。而這個(gè)最高的可靠程度，必須用最大后驗(yàn)概率準(zhǔn)則來選則譯碼規(guī)則，才能得以實(shí)現(xiàn)。編碼理論第7章課件35[例7-1]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為試選擇譯碼規(guī)則，使其平均錯(cuò)誤譯碼概率達(dá)到最小值,并計(jì)算其值?解:因信道輸入符號(hào)非先驗(yàn)等概，故只能采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則。由(7-8)式和(7-9)式計(jì)算出后驗(yàn)概率矩陣考慮信道輸出符號(hào)與信道輸入符號(hào)一一對(duì)應(yīng)，選擇譯碼譯碼規(guī)則采用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則的最小平均錯(cuò)誤譯碼概率[例7-1]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為367.2.2最大似然譯碼準(zhǔn)則若要用最大后驗(yàn)概率準(zhǔn)則選擇譯碼規(guī)則,則首先要根據(jù)給定的信源統(tǒng)計(jì)特性和給定的信道統(tǒng)計(jì)特性，由(7-8)式算出與有關(guān)的r個(gè)后驗(yàn)概率。顯然，這會(huì)給具體操作帶來一些困難和不方便。在某些特定條件下，信源等概時(shí),最大后驗(yàn)概率準(zhǔn)則能得到一定程度的簡化，因?yàn)閯t可有選擇譯碼規(guī)則這種選擇譯碼規(guī)則的準(zhǔn)則，稱之為最大似然譯碼準(zhǔn)則。顯然，最大似然準(zhǔn)則是在信道輸入符號(hào)(信源輸出符號(hào))先驗(yàn)等概特定條件下的最大后驗(yàn)概率準(zhǔn)則，其平均錯(cuò)誤譯碼概率同樣達(dá)到最小值，由(7-16)和(7-17)式，得7.2.2最大似然譯碼準(zhǔn)則37[例7-2]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為試選擇譯碼規(guī)則，使其平均錯(cuò)誤譯碼概率達(dá)到最小值,并計(jì)算其值?解:因信道輸入符號(hào)先驗(yàn)等概，故采用最大似然準(zhǔn)則選擇譯碼規(guī)則。按最大似然準(zhǔn)則得到譯碼規(guī)則,并考慮信道輸出符號(hào)與信道輸入符號(hào)一一對(duì)應(yīng)，選擇譯碼函數(shù)所以，在采用最大似然準(zhǔn)則選擇譯碼規(guī)則時(shí)，就不必像一般的最大后驗(yàn)概率準(zhǔn)則那樣，由給定信道矩陣中的信道傳遞概率(前向概率)換算成后驗(yàn)概率(后向概率)，再比較后驗(yàn)概率的大小來選擇譯碼規(guī)則了。這就是最大似然準(zhǔn)則比最大后驗(yàn)概率準(zhǔn)則的方便之處。采用最大似然準(zhǔn)則選擇譯碼規(guī)則的最小平均錯(cuò)誤譯碼概率的具體計(jì)算值[例7-2]設(shè)某信道的信道矩陣及信道輸入符號(hào)的概率分別為387.3編碼原則7.3.1編碼的功能下面以二元對(duì)稱信道為例說明編碼的作用。[例7-2]二元對(duì)稱離散無記憶信道的信道矩陣

設(shè)p=0.01,,輸入符號(hào)“0”和“1”先驗(yàn)等慨，分析其直接傳輸及編碼傳輸?shù)男Ч?。解：因?yàn)樾旁聪闰?yàn)等慨，則采用最大似然準(zhǔn)則選擇譯碼規(guī)則平均錯(cuò)誤譯碼概率必定達(dá)到最小值0.01；

7.3編碼原則7.3.1編碼的功能39對(duì)信道輸入符號(hào)“0”和“1”進(jìn)行重復(fù)編碼，把“0”變成“000”，把“1”變成“111”。這時(shí)，采用最大似然準(zhǔn)則選擇譯碼規(guī)則，最小平均錯(cuò)誤譯碼概率

若選“000”代表信源符號(hào)“0”；選“001”代表信源符號(hào)“1”，這種譯碼規(guī)則的最小平均錯(cuò)誤譯碼概率0.01。在隨機(jī)編碼中碼字的不同選擇，會(huì)導(dǎo)致不同的最小平均錯(cuò)誤譯碼概率，那么應(yīng)遵循什么原則挑選碼字，才能得到盡可能小的最小平均錯(cuò)誤譯碼概率呢?下面討論這個(gè)問題。對(duì)信道輸入符號(hào)“0”和“1”進(jìn)行重復(fù)編碼，把407.3.2最小漢明距離譯碼準(zhǔn)則簡單重復(fù)編碼減少平均錯(cuò)誤譯碼概率是以降低信息傳輸率R作為代價(jià)的。即“犧牲有效性，換取可靠性”?，F(xiàn)在要討論的問題是,在隨機(jī)編碼中，當(dāng)消息數(shù)M和碼字長度N保持不變的條件下，即信道信息傳輸率(碼率)保持不變條件下，應(yīng)遵循什么原則挑選碼字，才能得到盡可能小的最小平均錯(cuò)誤譯碼概率?信道的輸入端有M個(gè)長度為N的由“0”和“1”組成的碼符號(hào)序列(碼字),信道的輸出端有個(gè)長度為N的碼符號(hào)序列。離散無記憶信道的N次擴(kuò)展信道有個(gè)傳遞概率，它們是7.3.2最小漢明距離譯碼準(zhǔn)則41(7-23)式可由漢明距離表示為在M個(gè)消息先驗(yàn)等概的條件下，采用最大似然準(zhǔn)則選擇譯碼規(guī)則。對(duì)來說，若有即編碼理論第7章課件42考慮到在一般情況下都有，且，所以(7-26)式又可改寫為

則選擇譯碼規(guī)則(7-27)和(7-28)式就是用漢明距離“語言”表述的最大似然準(zhǔn)則。它表明，在信道M個(gè)輸入消息先驗(yàn)等概的條件下，離散無記憶信道的N次擴(kuò)展信道的某一輸出序列，翻譯成與的漢明距離中的最小者所對(duì)應(yīng)的輸入消息,則其平均錯(cuò)誤譯碼概率達(dá)到最