第六章有噪信道編碼定理

第6章有噪信道編碼定理6.1錯誤概率和譯碼規(guī)則6.2錯誤概率與編碼方法6.3*聯(lián)合典型序列6.4有噪信道編碼定理6.5聯(lián)合信源信道編碼定理6.1錯誤概率和譯碼規(guī)則通信過程并不是在信道輸出端就結(jié)束了,要經(jīng)過譯碼過程才到達(dá)消息的終端，因此譯碼過程和譯碼規(guī)則對系統(tǒng)的錯誤概率影響很大.例如：已知二元信道(1)發(fā)送符號“0”,接收到符號仍為“0”的概率是(2)譯碼時，收到符號“0”時，若譯碼器譯為符號“0”，則正確譯碼的概率是(3)發(fā)送“0”收到“1”,譯成“1”，概率為此譯碼規(guī)則下，平均錯誤概率發(fā)送“0”，譯成“1”的概率發(fā)送“1”,譯成“0”的概率譯對概率新譯碼規(guī)則：接收符號“0”，譯成符號“1”接收符號“1”，譯成符號“0”結(jié)論：錯誤概率既與信道的統(tǒng)計特性有關(guān)，也與譯碼規(guī)則有關(guān)．輸入符號集輸出符號集s個輸出符號中的每一個都可以譯成r

個輸入符號中的任何一個，共有種譯碼規(guī)則可供選擇．1、定義：譯碼規(guī)則設(shè)計一個函數(shù)，它對于每一個輸出符號確定一個唯一的輸入符號與其單值對應(yīng)，２、平均錯誤概率好的譯碼規(guī)則、其平均錯誤概率最小.譯碼的條件正確概率：收到符號一定譯成，而發(fā)送的就是，為正確譯碼。條件錯誤概率e表示除了以外的所有輸入符號的集合。平均錯誤概率：譯碼后平均接收到一個符號所產(chǎn)生的錯誤大小。要使最小，應(yīng)使最小，也就是使為最大。如果采用這種譯碼函數(shù)，它對于每一個輸出符號均譯成具有最大后驗(yàn)概率的那個輸入符號，則信道的平均錯誤概率就能最小．稱“最大后驗(yàn)概率準(zhǔn)則”或“最小錯誤概率準(zhǔn)則”。選擇譯碼函數(shù)且滿足條件:３、最大似然譯碼準(zhǔn)則若先驗(yàn)概率等概率則選擇譯碼函數(shù)的條件應(yīng)滿足此譯碼規(guī)則稱“最大似然譯碼準(zhǔn)則”根據(jù)最大似然譯碼準(zhǔn)則，我們可以直接根據(jù)信道矩陣選定譯碼函數(shù)．即收到后，譯成信道矩陣P的第j

列中最大的那個元素所對應(yīng)的信源符號．當(dāng)不是等概分布時，仍可采用最大似然譯碼準(zhǔn)則，但不一定能使最小．4、平均錯誤概率的進(jìn)一步推導(dǎo)平均正確概率例6.1已知信道矩陣，制定譯碼規(guī)則，求出錯誤概率．解：根據(jù)最大似然譯碼準(zhǔn)則(1)另選擇譯碼規(guī)則由最大似然譯碼準(zhǔn)則，仍選第(1)組要使最小，使用最小錯誤概率準(zhǔn)則當(dāng)輸入不是等概率分布譯碼函數(shù)為：輸入不是等概分布時，最大似然譯碼準(zhǔn)則的平均錯誤概率不是最小的．5、費(fèi)諾不等式

PE與H(X|Y)滿足關(guān)系證明:5、費(fèi)諾不等式

5、費(fèi)諾不等式

5、費(fèi)諾不等式

logr0log(r-1)1不管采用什么譯碼規(guī)則,費(fèi)諾不等式成立.

信道疑義度與產(chǎn)生錯誤的不確定性有關(guān).

信道疑義度與錯誤發(fā)生后判斷是哪個輸入符號造成錯誤的最大不確定性有關(guān).6.2錯誤概率與編碼方法6.2.1簡單重復(fù)編碼的錯誤概率6.2.2簡單重復(fù)編碼的信息傳輸率6.2.4最小距離譯碼準(zhǔn)則6.2.3不同編碼的錯誤概率6.2.5用漢明距離計算

6.2.1簡單重復(fù)編碼的錯誤概率1、輸入碼字為單符號“0”,“1”選擇最佳譯碼規(guī)則通信系統(tǒng)一般要求如何提高2、消息重復(fù)發(fā)送3遍——“000”，“111”二元對稱信道的三次擴(kuò)展信道二元對稱信道的三次擴(kuò)展信道根據(jù)最大似然譯碼準(zhǔn)則，確定譯碼函數(shù)3、當(dāng)時當(dāng)時當(dāng)時當(dāng)時6.2.2簡單重復(fù)編碼的信息傳輸率(1)n=1(無重復(fù)),M=2,設(shè)t=1秒(2)當(dāng)n=3,M=2

結(jié)論:

簡單重復(fù)編碼方法,在使降低的同時,也使信息傳輸率R降低很多.M是輸入消息的個數(shù),logM等概率時的信息量6.2.3不同編碼的錯誤概率1、二元對稱信道的三次擴(kuò)展信道錯誤概率增大到單符號時的三倍!但2、在三次擴(kuò)展信道的輸入取M=4方案Ⅰ：方案Ⅱ：6.2.4最小距離譯碼準(zhǔn)則1、碼字距離——漢明距離長度為n的兩個符號序列(碼字)和之間的距離是指和之間對應(yīng)位置上不同碼元的個數(shù)，用符號表示。這種碼字距離稱為漢明距離。2、最小距離在某一碼書中，任意兩個碼字的漢明距離的最小值稱為該碼C的最小距離。方案Ⅰ：方案Ⅱ：結(jié)論：碼C的最小碼距越大，越小傳輸過程中傳輸?shù)接袀€位置發(fā)生了錯誤，個位置沒有錯誤.設(shè)二元對稱信道單個符號傳輸錯誤概率為p,則編碼后信道的傳遞概率3、最小距離譯碼準(zhǔn)則(1)最大似然譯碼準(zhǔn)則滿足信道擴(kuò)展矩陣列元素中最大元素對應(yīng)越小,越大.用漢明距離表示最大似然譯碼準(zhǔn)則:滿足在二元對稱信道中，最小距離譯碼準(zhǔn)則＝最大似然譯碼準(zhǔn)則在任意信道中，也可采用最小距離譯碼準(zhǔn)則，但它不一定等于最大似然譯碼準(zhǔn)則。6.2.5用漢明距離計算

——二元對稱無記憶信道,輸入等概分布總結(jié)：編碼方法：使選取的M個碼字中任意兩兩不同碼字的距離盡量大。譯碼方法：把譯成與它最鄰近的那個發(fā)送碼字，即使盡量小。6.3聯(lián)合典型序列6.3.1定義聯(lián)合典型序列6.3.2三個定理6.3.1定義聯(lián)合典型序列無記憶n次擴(kuò)展信道單符號離散信道定義：n長的序列對滿足(1)是典型序列;(2)是典型序列;(3)對于任意小的正數(shù)，存在n使稱序列對為聯(lián)合典型序列。的典型序列集表示為的典型序列集表示為的聯(lián)合典型序列集表示為6.3.2三個定理定理6.1（聯(lián)合漸進(jìn)等分割性）對于任意小的正數(shù),當(dāng)n足夠大時,則定理6.1表明(1)兩個隨機(jī)變量情況下，信源和聯(lián)合信源都具有漸進(jìn)等分割性。隨著n的增大，典型序列集出現(xiàn)的概率增大，且趨于等概分布。(2)典型序列是擴(kuò)展信道輸入端高概率出現(xiàn)的序列；典型序列是擴(kuò)展信道輸出端高概率出現(xiàn)的序列；聯(lián)合典型序列對是那些信道輸入和輸出間密切關(guān)聯(lián)，經(jīng)常出現(xiàn)的序列對。定理6.2對于任意小的正數(shù)足夠大(1)(2)定理6.2表明(1)已知典型序列條件下，與構(gòu)成聯(lián)合典型序列的的集合為,即左上角每一列中至多有個黑點(diǎn)。(2)同理，已知典型序列條件下，其對應(yīng)行在圖左上角至多個黑點(diǎn)。定理6.3若和統(tǒng)計獨(dú)立并與有相同的邊緣分布，則定理6.3表明（1）隨機(jī)選擇序列對是統(tǒng)計獨(dú)立的聯(lián)合典型序列對的概率約等于。（2）對某一典型序列，與它統(tǒng)計獨(dú)立的聯(lián)合典型序列對可能有個。整體分析（三個定理）結(jié)論(2)輸出端的典型序列數(shù)共約(3)選擇碼字的原則是，其對應(yīng)的典型序列互不重疊。(4)輸入端可選取的最多碼字?jǐn)?shù)(1)發(fā)送某一典型序列，一定高概率地傳送到與它構(gòu)成聯(lián)合典型序列的那些序列上,共有個對應(yīng)的典型序列。6.4有噪信道編碼定理定理6.4（有噪信道編碼定理）設(shè)離散無記憶信道，為其信道傳遞概率，其信道容量為C。當(dāng)信息傳輸率R<C時；只要碼長n足夠長，總可以在輸入符號集中找到個碼字組成的一組碼和相應(yīng)的譯碼規(guī)則，使譯碼的錯誤概率任意小。當(dāng)碼長n增大時，如果M數(shù)不變，顯然可使減小，因?yàn)榭稍龃蟆ＴO(shè)離散無記憶信道,其信道容量為C。當(dāng)信息傳輸率R>C,則無論碼長n多長，總也找不到一種編碼，使譯碼錯誤概率任意小。定理6.5有噪信道編碼逆定理6.5聯(lián)合信源信道編碼定理1、第一部分：信源編碼(2)信源壓縮編碼只與信源有關(guān)，不依賴于信道。(3)形成了其一個理論分支——數(shù)據(jù)壓縮理論與技術(shù)。針對各自信源的不同特點(diǎn)，進(jìn)行不同的數(shù)據(jù)壓縮，用最有效的二元碼來表達(dá)這些不同的信源。2、第二部分：信道編碼(1)信道