信息論第六章課件

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

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

列中最大的那個元素所對應的信源符號．當不是等概分布時，仍可采用最大似然譯碼準則，但不一定能使最?。鶕?jù)最大似然譯碼準則，我們可以直接根據(jù)信道矩陣選定譯碼函數(shù)．104、平均錯誤概率的進一步推導平均正確概率4、平均錯誤概率的進一步推導平均正確概率11例6.1已知信道矩陣，制定譯碼規(guī)則，求出錯誤概率．解：根據(jù)最大似然譯碼準則(1)另選擇譯碼規(guī)則例6.1已知信道矩陣，制定譯碼規(guī)則，求出錯誤概率．解：12由最大似然譯碼準則，仍選第(1)組要使最小，使用最小錯誤概率準則當輸入不是等概率分布譯碼函數(shù)為：輸入不是等概分布時，最大似然譯碼準則的平均錯誤概率不是最小的．由最大似然譯碼準則，仍選第(1)組要使最小，使用最小錯136.2錯誤概率與編碼方法6.2.1簡單重復編碼的錯誤概率6.2.2簡單重復編碼的信息傳輸率6.2.4最小距離譯碼準則6.2.3不同編碼的錯誤概率6.2.5用漢明距離計算

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

結論:

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

——二元對稱無記憶信道,輸入等概分布6.2.5用漢明距離計算27總結：編碼方法：使選取的M個碼字中任意兩兩不同碼字的距離盡量大。譯碼方法：把譯成與它最鄰近的那個發(fā)送碼字，即使盡量小?？偨Y：編碼方法：使選取的M個碼字中任意譯碼方法：把286.3聯(lián)合典型序列6.3.1定義聯(lián)合典型序列6.3.2三個定理6.3聯(lián)合典型序列6.3.1定義聯(lián)合典型序296.3.1定義聯(lián)合典型序列無記憶n次擴展信道單符號離散信道6.3.1定義聯(lián)合典型序列無記憶n次擴展信道單符30定義：n長的序列對滿足(1)是典型序列;(2)是典型序列;(3)對于任意小的正數(shù)，存在n使稱序列對為聯(lián)合典型序列。的典型序列集表示為的典型序列集表示為的聯(lián)合典型序列集表示為定義：n長的序列對滿足(1)是31信息論第六章課件326.3.2三個定理定理6.1（聯(lián)合漸進等分割性）對于任意小的正數(shù),當n足夠大時,則6.3.2三個定理定理6.1（聯(lián)合漸進等分割性）33定理6.1表明(1)兩個隨機變量情況下，信源和聯(lián)合信源都具有漸進等分割性。隨著n的增大，典型序列集出現(xiàn)的概率增大，且趨于等概分布。(2)典型序列是擴展信道輸入端高概率出現(xiàn)的序列；典型序列是擴展信道輸出端高概率出現(xiàn)的序列；聯(lián)合典型序列對是那些信道輸入和輸出間密切關聯(lián)，經(jīng)常出現(xiàn)的序列對。定理6.1表明(1)兩個隨機變量情況下，信源34定理6.2對于任意小的正數(shù)足夠大(1)(2)定理6.2表明(1)已知典型序列條件下，與構成聯(lián)合典型序列的的集合為,即左上角每一列中至多有個黑點。(2)同理，已知典型序列條件下，其對應行在圖左上角至多個黑點。定理6.2對于任意小的正數(shù)足夠大(35定理6.3若和統(tǒng)計獨立并與有相同的邊緣分布，則定理6.3表明（1）隨機選擇序列對是統(tǒng)計獨立的聯(lián)合典型序列對的概率約等于。（2）對某一典型序列，與它統(tǒng)計獨立的聯(lián)合典型序列對可能有個。定理6.3若和統(tǒng)計獨立并與36整體分析（三個定理）結論(2)輸出端的典型序列數(shù)共約(3)選擇碼字的原則是，其對應的典型序列互不重疊。(4)輸入端可選取的最多碼字數(shù)(1)發(fā)送某一典型序列，一定高概率地傳送到與它構成聯(lián)合典型序列的那些序列上,共有個對應的典型序列。整體分析（三個定理）結論(2)輸出端的典型序列數(shù)共約376.4有噪信道編碼定理定理6.4（有噪信道編碼定理）設離散無記憶信道，為其信道傳遞概率，其信道容量為C。當信息傳輸率R<C時；只要碼長n足夠長，總可以在輸入符號集中找到個碼字組成的一組碼和相應的譯碼規(guī)則，使譯碼的錯誤概率任意小。當碼長n增大時，如果M數(shù)不變，顯然可使減小，因為可增大。6.4有噪信道編碼定理定理6.4（有噪信道編碼定理38設離散無記憶信道,其信道容量為C。當信息傳輸率R>C,則無論碼長n多長，總也找不到一種編碼，使譯碼錯誤概率任意小。定理6.5有噪信道編碼逆定理設離散無記憶信道39定理6.6（有噪連續(xù)信道編碼定理）對于限帶高斯白噪聲加性信道，噪聲功率為Pn，帶寬為W，信號平均功率受限為Ps，則（1）當，總可以找到一種信道編碼在信道中以信息傳輸率R傳輸信息，而使錯誤概率任意小。（2）當，找不到一種信道編碼，在信道中以R傳輸信息而使錯誤概率任意小。定理6.6（有噪連續(xù)信道編碼定理）（2）當406.5聯(lián)合信源信道編碼定理1、第一部分：信源編碼(2)信源壓縮編碼只與信源有關，不依賴于信道。(3)形成了其一個理論分支——數(shù)據(jù)壓縮理論與技術。針對各自信源的不同特點，進行不同的數(shù)據(jù)壓縮，用最有效的二元碼來表達這些不同的信源。6.5聯(lián)合信源信道編碼定理1、第一部分：信源編碼(2)412、第二部分：信道編碼(1)信道編碼只需針對信道特性進行，不用考慮不同信源的不同特性，其輸入端只是接收一系列二元碼，編碼與信源無關。(2)形成了一個理論分支——糾錯碼理論3、這種分兩步編碼的處理方法，可以大大降低通信系統(tǒng)的復雜度。2、第二部分：信道編碼(1)信道編碼只需針對信道特性進行，42檢錯和糾錯的規(guī)則：1、要發(fā)現(xiàn)(檢測)e個隨機錯誤，要求碼的最小距離2、要糾正e個隨機錯誤，則要求3、要糾正e個隨機錯誤同時檢測個錯誤，則要求檢錯和糾錯的規(guī)則：1、要發(fā)現(xiàn)(檢測)e個隨機錯誤，要求碼243第6章有噪信道編碼定理6.1錯誤概率和譯碼規(guī)則6.2錯誤概率與編碼方法6.3*聯(lián)合典型序列6.4有噪信道編碼定理6.5聯(lián)合信源信道編碼定理第6章有噪信道編碼定理6.1錯誤概率和譯碼規(guī)則6.2446.1錯誤概率和譯碼規(guī)則通信過程并不是在信道輸出端就結束了,要經(jīng)過譯碼過程才到達消息的終端，因此譯碼過程和譯碼規(guī)則對系統(tǒng)的錯誤概率影響很大.例如：已知二元信道(1)發(fā)送符號“0”,接收到符號仍為“0”的概率是(2)譯碼時，收到符號“0”時，若譯碼器譯為符號“0”，則正確譯碼的概率是(3)發(fā)送“0”收到“1”,譯成“1”，概率為6.1錯誤概率和譯碼規(guī)則通信過程并不是在信道輸45此譯碼規(guī)則下，平均錯誤概率發(fā)送“0”，譯成“1”的概率發(fā)送“1”,譯成“0”的概率譯對概率此譯碼規(guī)則下，平均錯誤概率發(fā)送“0”，譯成“1”的概率發(fā)送“46新譯碼規(guī)則：接收符號“0”，譯成符號“1”接收符號“1”，譯成符號“0”結論：錯誤概率既與信道的統(tǒng)計特性有關，也與譯碼規(guī)則有關．新譯碼規(guī)則：接收符號“0”，譯成符號“1”接收符號“1”，譯47輸入符號集輸出符號集s個輸出符號中的每一個都可以譯成r

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

列中最大的那個元素所對應的信源符號．當不是等概分布時，仍可采用最大似然譯碼準則，但不一定能使最?。鶕?jù)最大似然譯碼準則，我們可以直接根據(jù)信道矩陣選定譯碼函數(shù)．534、平均錯誤概率的進一步推導平均正確概率4、平均錯誤概率的進一步推導平均正確概率54例6.1已知信道矩陣，制定譯碼規(guī)則，求出錯誤概率．解：根據(jù)最大似然譯碼準則(1)另選擇譯碼規(guī)則例6.1已知信道矩陣，制定譯碼規(guī)則，求出錯誤概率．解：55由最大似然譯碼準則，仍選第(1)組要使最小，使用最小錯誤概率準則當輸入不是等概率分布譯碼函數(shù)為：輸入不是等概分布時，最大似然譯碼準則的平均錯誤概率不是最小的．由最大似然譯碼準則，仍選第(1)組要使最小，使用最小錯566.2錯誤概率與編碼方法6.2.1簡單重復編碼的錯誤概率6.2.2簡單重復編碼的信息傳輸率6.2.4最小距離譯碼準則6.2.3不同編碼的錯誤概率6.2.5用漢明距離計算

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

結論:

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

——二元對稱無記憶信道,輸入等概分布6.2.5用漢明距離計算70總結：編碼方法：使選取的M個碼字中任意兩兩不同碼字的距離盡量大。譯碼方法：把譯成與它最鄰近的那個發(fā)送碼字，即使盡量小?？偨Y：編碼方法：使選取的M個碼字中任意譯碼方法：把716.3聯(lián)合典型序列6.3.1定義聯(lián)合典型序列6.3.2三個定理6.3聯(lián)合典型序列6.3.1定義聯(lián)合典型序726.3.1定義聯(lián)合典型序列無記憶n次擴展信道單符號離散信道6.3.1定義聯(lián)合典型序列無記憶n次擴展信道單符73定義：n長的序列對滿足(1)是典型序列;(2)是典型序列;(3)對于任意小的正數(shù)，存在n使稱序列對為聯(lián)合典型序列。的典型序列集表示為的典型序列集表示為的聯(lián)合典型序列集表示為定義：n長的序列對滿足(1)是74信息論第六章課件756.3.2三個定理定理6.1（聯(lián)合漸進等分割性）對于任意小的正數(shù),當n足夠大時,則6.3.2三個定理定理6.1（聯(lián)合漸進等分割性）76定理6.1表明(1)兩個隨機變量情況下，信源和聯(lián)合信源都具有漸進等分割性。隨著n的增大，典型序列集出現(xiàn)的概率增大，且趨于等概分布。(2)典型序列是擴展信道輸入端高概率出現(xiàn)的序列；典型序列是擴展信道輸出端高概率出現(xiàn)的序列；聯(lián)合典型序列對是那些信道輸入和輸出間密切關聯(lián)，經(jīng)常出現(xiàn)的序列對。定理6.1表明(1)兩個隨機變量情況下，信源77定理6.2對于任意小的正數(shù)足夠大(1)(2)定理6.2表明(1)已知典型序列條件下，與構成聯(lián)合典型序列的的集合為,即左上角每一列中至多有個黑點。(2)同理，已知典型序列條件下，其對應行在圖左上角至多個黑點。定理6.2對于任意小的正數(shù)足夠大(78定理6.3若和統(tǒng)計獨立并與有相同的邊緣分布，則定理6.3表明（1）隨機選擇序列對是統(tǒng)計獨立的聯(lián)合典型序列對的概率約等于。（2）對某一典型序列，與它統(tǒng)計獨立的聯(lián)合典型序列對可能有個。定理6.3若和統(tǒng)計獨立并與79整體分析（三個定理）結論(2)輸出端的典型序列數(shù)共約(3)選擇碼字的原則是，其對應的典型序列互不重疊。(4)輸入端可選取的最多碼字數(shù)(1)發(fā)送某一典型序列，一定高概率地傳送到與它構成聯(lián)合典型序列的那些序列上,共有個對應的典型序列。整體分析（三個定理）結論(2)輸出端的典型序列數(shù)共約806.4有噪信道編碼定理定理6.4（有噪信道編碼定理）設離散