第六章有噪信道編碼定理

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

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

列中最大的那個(gè)元素所對(duì)應(yīng)的信源符號(hào)．當(dāng)不是等概分布時(shí)，仍可采用最大似然譯碼準(zhǔn)則，但不一定能使最小．4、平均錯(cuò)誤概率的進(jìn)一步推導(dǎo)平均正確概率例6.1已知信道矩陣，制定譯碼規(guī)則，求出錯(cuò)誤概率．解：根據(jù)最大似然譯碼準(zhǔn)則(1)另選擇譯碼規(guī)則由最大似然譯碼準(zhǔn)則，仍選第(1)組要使最小，使用最小錯(cuò)誤概率準(zhǔn)則當(dāng)輸入不是等概率分布譯碼函數(shù)為：輸入不是等概分布時(shí)，最大似然譯碼準(zhǔn)則的平均錯(cuò)誤概率不是最小的．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)生錯(cuò)誤的不確定性有關(guān).

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

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

結(jié)論:

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

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