信息論與編碼課件復(fù)習(xí)總結(jié)

1、1總復(fù)習(xí)總復(fù)習(xí)重要的概念及運算重要的概念及運算 熵及其計算熵及其計算 互熵（平均互信息）及其計算互熵（平均互信息）及其計算 信道容量及其計算（特別是對稱及準對稱信道信道容量及其計算（特別是對稱及準對稱信道容量）容量） 馬爾科夫信源的平穩(wěn)分布馬爾科夫信源的平穩(wěn)分布 即時碼的判定、信源編碼方法（特別是霍夫曼即時碼的判定、信源編碼方法（特別是霍夫曼編碼）編碼） 失真矩陣及平均失真度、失真定義域失真矩陣及平均失真度、失真定義域重要的定理（香農(nóng)三大定理及香農(nóng)公式重要的定理（香農(nóng)三大定理及香農(nóng)公式） 無失真信源編碼定理無失真信源編碼定理 有噪信道編碼定理有噪信道編碼定理 香農(nóng)公式香農(nóng)公式 限失真信源編碼定

2、理限失真信源編碼定理21.1.信息的如何度量？信息的如何度量？ 熵及互熵（平均互信息）、信道容量熵及互熵（平均互信息）、信道容量2. 2. 需要解決的問題：需要解決的問題： 信息傳輸?shù)目煽啃耘c有效性問題信息傳輸?shù)目煽啃耘c有效性問題 信源編碼與信道編碼（香農(nóng)三大定理）信源編碼與信道編碼（香農(nóng)三大定理）通信的基本問題（主要問題、關(guān)鍵問題）通信的基本問題（主要問題、關(guān)鍵問題）3)(log)(1log)(iiixpxpxI 自信息量自信息量聯(lián)合自信息量聯(lián)合自信息量)(log)(1log)(jijijiyxpyxpyxI 條件自信息量條件自信息量)|(log)|(1log)|(jijijiyxpyxpy

3、xI 4互信息量互信息量I(xi ; yj)()|(logijixpyxp 5平均自信息量平均自信息量（熵）（熵）)()(ixIEXH )(logixpE qiiixpxp1)(log)( H(X)表示信源的平均不確定度表示信源的平均不確定度平均信息量平均信息量 H(X)表示信源的隨機性表示信源的隨機性 H(X)表示信源輸出表示信源輸出每個符號所提供的平均信息每個符號所提供的平均信息量量 H(X)表示信宿所能獲得的最大信息量表示信宿所能獲得的最大信息量 6條件熵條件熵 XYijjiXYijjixypyxpxyIyxpXYH)|(log)( )|()()|(聯(lián)合熵聯(lián)合熵 XYjijiXYjiji

4、yxpyxpyxIyxpYXH)(log)( )()(),(平均互信息量（互熵）平均互信息量（互熵）);(YXI XYjijiyxIyxp);()( 名稱名稱 符號符號 關(guān)關(guān) 系系 圖圖 示示 無無 條條 件件 熵熵 條條 件件 熵熵 條條 件件 熵熵 聯(lián)聯(lián) 合合 熵熵 交交 互互 熵熵)|()()();()|()()|()(XYHXYHXHYXIYXHXHYXHXH )(XH)(YH)|(YXH)|(XYH)()(YXHXYH );();(XYIYXI )|()()();()|()()|()(YXHXYHYHYXIXYHYHXYHYH );()()()()|(YXIXHYHXYHYXH );

5、()()()()|(YXIYHXHXYHXYH );()|()|();()()()|()()|()()(YXIXYHYXHYXIYHXHYXHYHXYHXHXYH )()()()|()|()()|()()|()();(XYHYHXHYXHXYHXYHXYHYHYXHXHYXI YXYXYXYXYXYX8 信道由信道由傳遞概率矩陣唯一決定，傳遞概率矩陣傳遞概率矩陣唯一決定，傳遞概率矩陣稱為稱為信道矩陣信道矩陣P。111212122212ssrrrspppppppppP 信道的描述信道的描述9信道容量信道容量( )max(; )defp xCI X Y信道容量表征信道信道容量表征信道傳送信息的最大

6、能力傳送信息的最大能力。實際中信道傳送的信息量必須小于信道容量。實際中信道傳送的信息量必須小于信道容量。信道容量與信源分布無關(guān)信道容量與信源分布無關(guān)10損失熵損失熵 ：信源符號通過有噪信道傳輸后所：信源符號通過有噪信道傳輸后所引起的信息量損失，即引起的信息量損失，即信道疑義度信道疑義度 H(X|Y)。噪聲熵噪聲熵：在已知集：在已知集 X的條件下，對于集的條件下，對于集 Y尚尚存在的不確定性，即條件熵存在的不確定性，即條件熵 H(Y|X) 。11離散信道對照表離散信道對照表分分類類無噪無噪無損信道無損信道有噪有噪無損信道無損信道無噪有損無噪有損信道信道定定義義H(X|Y)=0（無損）（無損） H

7、(Y|X)=0（無噪）（無噪）H(X|Y)=0（無損）（無損）H(Y|X)0（有噪）（有噪）H(X|Y)0（有損）（有損）H(Y|X)=0（無噪）（無噪）特特點點一一對應(yīng)一一對應(yīng)一多對應(yīng)一多對應(yīng)多一對應(yīng)多一對應(yīng)12分分類類 無噪無噪無損信道無損信道有噪有噪無損信道無損信道無噪有損無噪有損信道信道信信道道容容量量 條條件件 信道輸入為等概信道輸入為等概分布分布 信道輸入為等概信道輸入為等概分布分布 使信道輸出為等使信道輸出為等概分布概分布p(y)=1/s的輸?shù)妮斎敕植既敕植?log bit/Cr符號log bit/Cr符號log bit/Cs符號1( )p xr1( )p xr( )p x13

8、mjijijixpabpabpmaYHYHXYHYHYXIC1)()(log)(log)()()()(|);(*特殊特殊DMC的信道容量的信道容量為為等等概概分分布布。對對稱稱信信道道的的輸輸出出分分布布也也分分布布。道道，故故輸輸入入分分布布為為等等概概對對稱稱信信道道必必是是準準對對稱稱信信14特殊特殊DMC的信道容量的信道容量 ppppP11)(1)1log()1(log1)1log()1(log2log)(log)(log1pHppppppppabpabpmCmjijij 15特殊特殊DMC的信道容量的信道容量 mjjijijibpabpabpYaxIC1)()(log)();(16特

9、殊特殊DMC的信道容量的信道容量符符號號bit/4471.045.01.0log1.01.01.0log1.045.08.0log8.0)()(log)();(1 mjjijijibpabpabpYaxIC 8 . 01 . 01 . 01 . 01 . 08 . 03P1.0)(,45.0)()()()()(21)()(231121 bpbpbpabpapbpapapniijij 準準對對稱稱信信道道17霍夫曼霍夫曼(Huffman)編碼編碼 費諾費諾(Fano)編碼編碼平均碼長平均碼長 qiiilspL1)(編碼效率編碼效率LSH)(即時碼存在即時碼存在（唯一可譯碼存在唯一可譯碼存在）的充

10、要條）的充要條件為：件為：11 qilir克拉夫特克拉夫特不等式不等式18譯碼規(guī)則譯碼規(guī)則 使平均錯誤概率使平均錯誤概率pE最小為最小為選擇譯碼規(guī)則的選擇譯碼規(guī)則的準則準則(1) 最大后驗概率譯碼規(guī)則最大后驗概率譯碼規(guī)則理想觀測者規(guī)則理想觀測者規(guī)則 選擇譯碼函數(shù)選擇譯碼函數(shù)F(yj)x*，使之滿足條件，使之滿足條件(2) 最大似然譯碼規(guī)則最大似然譯碼規(guī)則 選擇譯碼函數(shù)選擇譯碼函數(shù)F(yj)x*，使之滿足條件，使之滿足條件ixypxypijj 對對 )|()|(*iyxpyxpjij 對對 )|()|(*19平均錯誤概率平均錯誤概率 *,)()|(),(xXYxXYExpxypyxpp若輸入為等

11、慨分布，則若輸入為等慨分布，則 *,)|(1xXYExyprp20 單個符號的失真度的全體構(gòu)成的矩單個符號的失真度的全體構(gòu)成的矩陣陣 ，稱為失真矩陣，稱為失真矩陣),(jiyxd),(),(),(),(),(),(),(),(),(212221212111mnnnmmbadbadbadbadbadbadbadbadbadd失真矩陣失真矩陣21平均失真平均失真 由于由于xi和和yj都是隨機變量，所以失真函數(shù)都是隨機變量，所以失真函數(shù)d(xi，yj)也是也是隨機變量，限失真時的失真值，只能用它的數(shù)學(xué)期隨機變量，限失真時的失真值，只能用它的數(shù)學(xué)期望或統(tǒng)計平均值，因此將失真函數(shù)的數(shù)學(xué)期望稱為望或統(tǒng)計平

12、均值，因此將失真函數(shù)的數(shù)學(xué)期望稱為平均失真平均失真，記為，記為nimjjiijinimjjijibadabpapbadbapD1111),()/()(),()(22對于離散無記憶信源，對于離散無記憶信源，R(D)函數(shù)可寫成函數(shù)可寫成 p(ai)，i1，2，n 是信源符號概率分布；是信源符號概率分布； p(bj/ai)，i1，2，n，j1，2，m 是轉(zhuǎn)移概率分布；是轉(zhuǎn)移概率分布； p(bj)，j1，2，m 是接收端收到符號概率分布。是接收端收到符號概率分布。 nimjjijijiPPbpabpabpapDRDij11)()/(log)/()(min)();(min)(YXIDRDP信息率失真函數(shù)

13、信息率失真函數(shù)23R(D)函數(shù)的定義域函數(shù)的定義域 UVvudupD),(min)(min UVvudupD),()(minmax24香農(nóng)三大定理香農(nóng)三大定理無失真信源編碼定理：無失真信源編碼定理：平均碼長大于等于信源熵平均碼長大于等于信源熵有噪信道編碼定理：有噪信道編碼定理：信息傳輸率小于等于信道容量信息傳輸率小于等于信道容量 限失真信源編碼定理：限失真信源編碼定理：信息傳輸率大于等于信息率失真函數(shù)信息傳輸率大于等于信息率失真函數(shù))(SHNL CR )(DRR 壓縮有限，接近無限壓縮有限，接近無限傳輸有限，接近無限傳輸有限，接近無限壓縮有限，接近無限壓縮有限，接近無限25香農(nóng)公式香農(nóng)公式香香農(nóng)農(nóng)公公式式1logNSWC