信息論與編碼第三章 離散信道

1、第三章 離散信道3.1 信道的數(shù)學(xué)模型和分類 離散信道：I/O的R、V的取值都是離散的信道；連續(xù)信道：入/出R、V的取值都是連續(xù)的信道；半散半續(xù)：、R、V離散出R、V連續(xù)或相反。離散信道，必須確定其主要參數(shù)： 輸入 ： 輸出 ： 信道的傳輸作用 ： 1、主要參數(shù)表示法：單符號(hào)： 多符號(hào)： 2、信道矩陣表示法： 3、圖示法： b1 b2 bs b1 b2 bs離散信道分類：A、理想信道：輸入輸出一一對(duì)應(yīng)， 且B、有干擾無記憶信道 ：或：C、有干擾有記憶信道 ： 例：二進(jìn)制對(duì)稱信道；二進(jìn)制擴(kuò)展信道。一般離散信道的一些概率關(guān)系 1、輸入符號(hào)ai, 輸出符號(hào)bj的聯(lián)合概率前向概率 ： 后向（驗(yàn)）概率2

2、、輸出符號(hào)bj的概率：3、信宿收列符號(hào)bj后，推測輸入符號(hào)ai的后驗(yàn)概率： 由貝葉斯定律 且：先驗(yàn)概率 3.2 信道疑義度及平均互信息3.2.1交互信息量 信息流通的根本問題 :通信前后對(duì)信道輸入ai不確定性消除的量。1.站在信道的輸出端觀察2.站在信道的輸入端觀察3、站在通信系統(tǒng)的總體立場觀察 通信前： 通信后： 單位也為：bit (2)； nat (e)； Hart (10)3.2.2后驗(yàn)概率與交互信息量的關(guān)系 交互信息量log 后驗(yàn)概率先驗(yàn)概率1、 這時(shí) ，為無噪信道。 2、 ，后驗(yàn)概率與先驗(yàn)概率的比值大于1，3、4、 ，引伸一下，ai和bj統(tǒng)計(jì)獨(dú)立時(shí) ： 且 說明ai和bj之間的約束程

3、度不同，交互信息量也各不相同，所以，即是ai和bj之間交互信息量的測試，也是ai和bj之間統(tǒng)計(jì)約束程度的一個(gè)體現(xiàn)者。3.2.3 自信息量兩種含意 1、 自信息量可被理解為要完全消除對(duì) 不確定性，唯一確定 所必須獲取的最大信息量。 2 、 自信息量可理解為符號(hào)bj所能提供的最大信息量。 由信息函數(shù)確定的自信息量I（x），就是要唯一確定隨機(jī)事件（符號(hào)）x所必須的最大信息量，或者說是隨機(jī)事件x所能提供的最大信息量。1、取 , 因?yàn)闊o失真信源編碼的一一對(duì)應(yīng)性，所以可認(rèn)為有 收到就意味著確切無誤地收到消息a4，完全消除了a4的不確定度，這時(shí)碼字bj011和消息a4之間的交互信息量，就是消息a4的自信息量

4、，（ 是確定a4所必須的最大信息量）。 2、仍取但取bj為碼字“011”中的第一個(gè)碼符號(hào)“0”，因?yàn)檫@時(shí)有 ，發(fā)消息a4就意味著確切無誤地出現(xiàn)bj”0”，這時(shí)，從a4中獲取關(guān)于第一個(gè)碼符號(hào)“0”的信息量就是“0”的自信息量。 bit ，I（0）可理解為第一個(gè)碼符號(hào)“0”對(duì)a4所能提供的最大信息量。 從以上討論可知，自信息量只不過是交互信息量在后驗(yàn)概率 （或 這一特定情況下的特例，為此，在這里我們要提請(qǐng)注意，交互信息理論才體現(xiàn)出信息理論關(guān)于信息測度的完整觀點(diǎn)。 3.2.4 平均交互信息量 3.2.5 平均交互信息量的物理意義信道疑義度 （損失熵）： 噪聲熵： 聯(lián)合熵（共熵）： H（x y） 1、

5、 表示收到y(tǒng)前、后關(guān)于x的不確定性的消除的量。2、 表示發(fā)x前、后，關(guān)于y的不確定性的消除的量。 平均交互信息量就是通信前、后平均不確定度的消除的量。 3.3 平均互信息的特性1、非負(fù)性 ：2、極值性： 3、對(duì)稱性：4、與各類熵的關(guān)系：損失熵 噪聲熵5、平均互信息的凸函數(shù)性 定理3.1 平均互信息 是輸入信源概率分布 的型凸函數(shù)。證明：固定信道，即信道的傳遞概率 是固定的平均互信息 將只是 的函數(shù)，簡寫成 選擇信源符號(hào)集X的兩種已知的概率分布 和 ，對(duì)應(yīng)的聯(lián)合概率分布為： 和 式中： 是型凸函數(shù)，對(duì)上式第一項(xiàng)，根據(jù)詹森不等式： =log 同理： 得： 證畢 。 匹配信源： ， 由信道的傳遞概率

6、所決定。定理3.2：平均互信息 是信道傳遞概率 的型凸函數(shù)。（與定理3.1對(duì)偶 ）總可以找到一個(gè)信道，其傳遞概率為：使平均交互信息量達(dá)列極小值 。 3.4 離散無記憶信道的擴(kuò)展信道例：二進(jìn)制對(duì)稱信道的二次擴(kuò)展信道矩陣為：無記憶信道的N次擴(kuò)展信道的平均互信息定理3.3，若信道的輸入隨機(jī)序列為 ，通過信道傳輸，接收到的隨機(jī)序列為 ，假如信道是無記憶的，即信道傳遞概率滿足： 則存在無記憶N次擴(kuò)展信道： 式中xi和yi是隨機(jī)序列X和Y中對(duì)應(yīng)的第i位隨機(jī)變量。 證明：設(shè)某一輸入為 輸出為： X和Y的平均互信息： ，信道是無記憶的 另一方面： 當(dāng)信源是無記憶時(shí)，有： 因此上式等號(hào)成立。 定理3.4：若信道

7、輸入隨機(jī)序列為 ，通過信道傳輸，接收到的隨機(jī)序列 ，信道的傳遞概率為 ，若信源是無記憶的，則存在；3.5串聯(lián)信道的互信息平均交互信息量：（X，Y）；（X，Z）； （Y，Z）；（XY，Z）；（X，YZ） 1、 當(dāng)且僅當(dāng)時(shí)一切 都有 才能使等式成立。 2、 當(dāng)且僅當(dāng)時(shí)一切 都有 才能使等式成立。 3、當(dāng)隨機(jī)序列 構(gòu)成馬氏鏈時(shí)，則有： ， 當(dāng)且僅當(dāng)時(shí)一切 都有 才能使等式成立。信息處理定理（數(shù)據(jù)處理定理、信息不增原理） 根據(jù)3得出結(jié)論：通過串聯(lián)信道的傳輸只會(huì)丟失信息，且傳輸中丟失的信息量，不論以后的系統(tǒng)如何處理，只要 不觸及到丟失信息過程的輸入端，就不能恢復(fù)已丟失的信息 數(shù)據(jù)處理為歸并過程，將X的若

8、干個(gè)符號(hào)組成一組（分類），即：B1UB2UU Bm， Bm=(b1,bs），B1B2Bm=直觀地分類數(shù)據(jù)處理意味著使觀察變得粗略，處理結(jié)果只能使對(duì)X的不確定性減少而不會(huì)增加，即信息量減少。任何無源處理過程（不涉及原始信源），總是丟失信息的，最多是保持原有信息不變。 3.6 信道容量一、信道容量的定義平均交互信息量的最大值， 比特/信道符號(hào)或： 一般仍稱Ct為信道容量。 例：二進(jìn)制對(duì)稱信道的平均交互信息量：當(dāng) 時(shí) ，得： 信道容量C與信源無關(guān)，它只是信道傳輸p的函數(shù)，與信道統(tǒng)計(jì)特性有關(guān)。 二、信道容量的一般計(jì)算方法作一輔助函數(shù)： 可推得一般情況下的偏導(dǎo)數(shù)為： 假設(shè)使平均交互信息量達(dá)到極大值的輸入

9、概率分布 即： 令 ： 則： 由這個(gè)C值，可解得對(duì)應(yīng)的輸出概率：解出達(dá)到容量的最佳輸入概率分布：但需滿足 條件 ，否則令某些ai的概率等于0，重算。由式：又由式： 對(duì)所有ai 結(jié)論：一般離散信道的平均交互信息量達(dá)到極大值（即等于信道容量）的充分必要條件是輸入概率分布 滿足： 判定定理： 或： 當(dāng)信道平均交互信息量達(dá)到信道容量時(shí)，輸入信源X的符號(hào)集中每一個(gè)信源符號(hào)ai對(duì)輸出端提供的信息量相同，只是概率為0的符號(hào)除外。 三、常見離散信道的信道容量1、離散無噪信道 ：2、擴(kuò)展信道：信源等概分布時(shí)，具有擴(kuò)展性能的信道達(dá)到信道容量 3、歸并信道： 4、強(qiáng)對(duì)稱離散信道 ：時(shí)達(dá)到最大值， 非唯一 當(dāng) 時(shí)，才

10、有A、 輸入隨機(jī)變量等概分布時(shí)，信道達(dá)到C，同時(shí)輸出隨機(jī)變量也等概分布，達(dá)最大熵 ；B、后驗(yàn)概率與傳遞概率相等， ；C、信道疑義度（損失熵）與噪聲熵相等 即，當(dāng)達(dá)到信道容量時(shí)，由“歸并”和“擴(kuò)展”噪聲引起的 平均不確定度相等。D、噪聲引起的平均不確定度隨信道的錯(cuò)誤傳遞概率 的減少而 。 最常用到的強(qiáng)對(duì)稱離散信道是二進(jìn)制對(duì)稱離散信道5、對(duì)稱離散信道 ：如離散信道的信道矩陣中每一行都是相同符號(hào)集 諸元素的不同排列組成，并且每一列也都是由相同符號(hào)集 諸元素的不同排列組成，則稱為對(duì)稱離散信道 與強(qiáng)對(duì)稱離散信道區(qū)別：A、強(qiáng)對(duì)稱離散信道的輸入符號(hào)數(shù)q等于輸出符號(hào)數(shù)s； 而對(duì)稱離散信道的q不一定等于s，不一定是方陣；B、強(qiáng)對(duì)稱離散信道：行和列是同一集合，此處不一定；C、強(qiáng)對(duì)稱離散信道的信道矩陣中列和=行和=1，而對(duì)稱離散信道的中每列之和不一定等于1；D、強(qiáng)對(duì)稱離散信道矩陣中對(duì)角線上的元素都是正確傳遞概率 ，其它全為錯(cuò)誤傳遞 ，而此處矩陣中雖然每行、每列具有可排列性，但不一定是對(duì)稱矩陣。 3.7 信道容量的迭代計(jì)算作輔助函數(shù)：同理，作輔助函數(shù)：迭代算法的基本公式及步驟如下 ： A、先假定一組 作為起始值 ，最合理的假定是起始概率分布為等概， ，將其固定變動(dòng)得：B、計(jì)算C、計(jì)算D、計(jì)算E、計(jì)算 類推，一般有：當(dāng)?shù)螖?shù) 時(shí)， ，可證明逼近收斂3.8 信源與信道