香農(nóng)定理深度詳解上課講義

1、香農(nóng)定理深度詳解信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、信源編碼器、信源編碼器a、模型編碼器編碼器1: ,.,qS saa1:,.,qC cWW12,.,liiiiiWxxx1: ,.,rX xxx單符號信源無失真編碼器碼符號碼符號碼字碼字碼長碼長信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介N次擴(kuò)展信源無失真編碼器編碼器編碼器1(,.,)NNSSS12,.,liiiiiWxxx1: ,.,rX xxx1 ,.,1,2,.,iqSaaiN1,2,.,Niq1、信源編碼器、信源編碼器a、模型信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介

2、簡介b、舉例1）ASCII信源編碼器1、信源編碼器、信源編碼器ASCII編碼器編碼器英文字母/符號/命令二進(jìn)代碼碼符號集0，1信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、信源編碼器、信源編碼器信源編碼器信源編碼器IA,B,Z二進(jìn)符號碼符號集0，1信源編碼器信源編碼器II碼符號集點/劃/字母間隔/單詞間隔2）摩爾斯電碼b、舉例2）摩爾斯信源編碼器b、舉例符號電平二進(jìn)代碼點劃字母間隔單詞間隔+ + + + 101110000000000信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介3）中文電報信源編碼器“中中”“0022”“01101 01101 1100

3、1 11001”1、信源編碼器、信源編碼器b、舉例信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介c c、分類、分類等長碼等長碼變長碼變長碼中文電報中文電報莫爾斯電碼莫爾斯電碼有失真編碼有失真編碼無失真編碼無失真編碼I(S;C) H(S)，就存在惟一可譯變長編碼；若RC，則不可能找到一種編碼，使輸出端錯誤概率任意小。 信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介3、香農(nóng)第二定理（、香農(nóng)第二定理（有噪信道編碼定理）信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介說明：說明：1 1、定理糾正了人們傳統(tǒng)固有的可靠性和有效性矛盾的觀點，、定理糾正了人

4、們傳統(tǒng)固有的可靠性和有效性矛盾的觀點，為信道編碼理論和技術(shù)的研究指明了方向。為信道編碼理論和技術(shù)的研究指明了方向。2 2、定理僅指出編碼的存在性，未給出編碼的具體方法。、定理僅指出編碼的存在性，未給出編碼的具體方法。3、定理指出：、定理指出：RC是可靠傳輸?shù)谋匾獥l件，但并未指出編碼是可靠傳輸?shù)谋匾獥l件，但并未指出編碼序列無限長是可靠傳輸?shù)谋匾獥l件。序列無限長是可靠傳輸?shù)谋匾獥l件。3、香農(nóng)第二定理（、香農(nóng)第二定理（有噪信道編碼定理）AWGN1)Turbo碼：碼：1/2碼率，碼率，BPSK，65536隨機(jī)交織，隨機(jī)交織，18次迭代，次迭代，Pe=10-5, Eb/N0 = 0.7dB2)非規(guī)則非規(guī)

5、則LDPC碼：碼：N = 107, 1/2碼率，碼率， Pe=10-5, Eb/N0 = 0.0045dB4、香農(nóng)進(jìn)一步證明：、香農(nóng)進(jìn)一步證明：R=C時，任意小的差錯概率也是可以達(dá)時，任意小的差錯概率也是可以達(dá)到的。到的。證明基本條件：證明基本條件：1）隨機(jī)編碼）隨機(jī)編碼 2）碼長）碼長 3）最大似然譯碼）最大似然譯碼信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介一、香農(nóng)第一定理三、香農(nóng)第三定理三、香農(nóng)第三定理二、香農(nóng)第二定理不大于一定編碼速率的條件下，使平均失真限 制到最??； 在平均失真不大于某個值的條件下，使編碼 速率限制到最小信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理

6、香農(nóng)三大定理簡介簡介信息率失真理論信息率失真理論1、失真度與信息率失真函數(shù)、失真度與信息率失真函數(shù)a、系統(tǒng)模型信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介信源信源編碼器無噪信道信源編碼器信宿試驗信道UV,.,1ruuAU符號集,.,1svvBV符號集b、失真測度1）單符號失真測度),(vud設(shè)VvUu,定義失真矩陣),(.),(.),(.),(),(.),(1212111srrssvudvudvudvudvudvudd0),(jivud信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、失真度與信息率失真函數(shù)、失真度與信息率失真函數(shù)如果規(guī)定jijijivuv

7、uvud, 1, 0),(，那么失真矩陣為0.11.1.011.10dN=3時，失真度如圖UV信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、失真度與信息率失真函數(shù)、失真度與信息率失真函數(shù)b、失真測度2)序列失真測度設(shè)序列VyyyUxxxjNiN),.,( ,),.,(11定義序列失真測度為NiiiNyxdNyxd1),(1),(信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、失真度與信息率失真函數(shù)、失真度與信息率失真函數(shù)b、失真測度3)平均失真單符號平均失真jijijivudvuPdE,),(),(序列平均失真NiiiyxdENdE1),(1信息論與編

8、碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、失真度與信息率失真函數(shù)、失真度與信息率失真函數(shù)b、失真測度c、信息率失真函數(shù)信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介1、失真度與信息率失真函數(shù)、失真度與信息率失真函數(shù)定義定義 信息率失真函數(shù));(min)()|(VUIDRDijPuvP0P(v|u)I(U;V)R(D)最佳編碼最佳編碼DD例例 設(shè)信源X，符號集為,.,221naaa，等概分布ninPi2,.,1,2/1給定失真測度為jijidji, 0, 1,設(shè)計一種單符號壓縮算法使得平均失真D=1/2，并求壓縮后的信息傳輸率R.信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)

9、香農(nóng)三大定理香農(nóng)三大定理簡介簡介信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介信息率失真函數(shù)性質(zhì)1）當(dāng)D Dmax時,R(D)=03）R(0)=H(X)4）在0D Dmax范圍內(nèi),R(D)是正的、連續(xù)的下凸函數(shù)R(D)DH(X)Dmax0二、香農(nóng)第三定理二、香農(nóng)第三定理（保真度準(zhǔn)則下的信源編碼定理）定理定理4.3 設(shè))(DR為一離散無記憶信源的信息率失真函數(shù)，并且有有限的失真測度D,則對于任意0, 0D，以及任意長的碼長k，一定存在一種碼字個數(shù)為)(2DRkM的信源編碼，使編碼后碼的平均失真度DD 信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介表述二：設(shè))(

10、DR為一離散無記憶信源的信息率失真函數(shù)，并且規(guī)定了有限的失真測度，對于任意的0, 0D則：)(logDRkMR1）若給定了失真D，且，則存在長度為k的碼，它的平均失真度DD 2）若)(DRR 時，無論采用什么編碼，其平均失真大于D信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介二、香農(nóng)第三定理二、香農(nóng)第三定理（保真度準(zhǔn)則下的信源編碼定理）幾點討論1）R(D)確定是保真度準(zhǔn)則條件下，信源信息率壓縮的下限。)()(0XHDR2）R(D)在實際工程中可以作為衡量各種壓縮編碼方法性能優(yōu)劣的一種標(biāo)尺。3）是一種存在定理，其實際應(yīng)用有待于進(jìn)一步研究：a)如何計算符合實際信源的信息率失真函數(shù)

11、R(D)？b)如何尋找最佳編碼方法才能達(dá)到信息壓縮的極限值R(D)？二、香農(nóng)第三定理二、香農(nóng)第三定理（保真度準(zhǔn)則下的信源編碼定理）信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介信信源源信信宿宿限限失失真真信信源源編編碼碼器器限限失失真真信信源源譯譯碼碼器器無無失失真真信信源源編編碼碼器器無無失失真真信信源源譯譯碼碼器器信信道道編編碼碼信信道道譯譯碼碼ABCDEFGH信道信道一般通信系統(tǒng)框圖一般通信系統(tǒng)框圖信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介信息論與編碼基礎(chǔ)信息論與編碼基礎(chǔ)香農(nóng)三大定理香農(nóng)三大定理簡介簡介總結(jié)：總結(jié)：香農(nóng)第二定理（香農(nóng)第二定理（有噪信