第4章離散信道ppt課件

1、信息論與編碼理論第4章 離散信道4.1 離散信道的數(shù)學(xué)模型n由于干擾的存在，信道的輸出Y與信道的輸入X不完全相同，用條件概率p(y|x)描畫(huà)。n而輸入和輸出又有各自的統(tǒng)計(jì)特性，分別用 和 表示。XPYP 4.2 信道的分類n根據(jù)輸入輸出事件的時(shí)間特性n離散信道：GSMn連續(xù)信道：有線電視、廣播n半連續(xù)信道n根據(jù)輸入輸出個(gè)數(shù)n兩端信道單路信道）：n多元接入信道：信道的復(fù)用n廣播信道：廣播n根據(jù)統(tǒng)計(jì)特性n恒參信道：信道的統(tǒng)計(jì)特性不隨時(shí)間發(fā)生變化。n隨參信道：信道的統(tǒng)計(jì)特性隨時(shí)間發(fā)生變化。n根據(jù)記憶特性n無(wú)記憶信道：信道的輸出僅與當(dāng)前的輸入有關(guān)，與以前的輸入無(wú)關(guān)。n有記憶信道：信道的輸出不僅與當(dāng)前的

2、輸入有關(guān)，與以前的輸入也有關(guān)系。幾種特殊信道n無(wú)噪無(wú)損信道：輸入集和輸出集之間存在一一對(duì)應(yīng)的關(guān)系。n有噪無(wú)損信道：有噪無(wú)損信道的一個(gè)輸入符號(hào)可能對(duì)應(yīng)多個(gè)輸入符號(hào)，而一個(gè)輸出符號(hào)只對(duì)應(yīng)一個(gè)輸入符號(hào)。n無(wú)噪有損信道：無(wú)噪有損信道的一個(gè)輸入符號(hào)只對(duì)應(yīng)一個(gè)輸入符號(hào)，而一個(gè)輸出符號(hào)可能對(duì)應(yīng)多個(gè)輸入符號(hào)。n無(wú)用信道：輸入與輸出相互獨(dú)立，沒(méi)有任何關(guān)系。4.3 離散無(wú)記憶信道4.3.1 離散信道的數(shù)學(xué)模型n離散無(wú)記憶信道中，當(dāng)前的輸出yj僅與當(dāng)前的輸入xi有關(guān)，與過(guò)去的輸入無(wú)關(guān)，即yj出現(xiàn)的概率僅與xi有關(guān)n信道轉(zhuǎn)移矩陣或者信道矩陣1112121222|12ssY XrrrsppppppPppp例4-3n假設(shè)

3、串口通信的誤碼率為4%，即A發(fā)送“0而B(niǎo)接收到“1的概率是0.04，A發(fā)送“1而B(niǎo)接收到“0的概率也是0.04，可以得到該信道的信道轉(zhuǎn)移矩陣|0.960.040.040.96Y XPn二進(jìn)制對(duì)稱信道n簡(jiǎn)稱為BSCBinary Symmetric Channel）n二元：輸入和輸出符號(hào)集均為0,1n對(duì)稱：1變成0和0變成1的概率相等。np(0|0)=p(1|1)=1-p，p(0|1)=p(1|0)=pnBSC的信道矩陣：ppPpp4.3.2 信道疑義度和噪聲熵n定義定義4-1 稱輸入空間稱輸入空間X對(duì)輸出空間對(duì)輸出空間Y的條件的條件熵熵n 為信道疑義度。為信道疑義度。n含義：收到全部輸出符號(hào)含義

4、：收到全部輸出符號(hào)Y以后，對(duì)輸入符以后，對(duì)輸入符號(hào)號(hào)X尚存在的平均不確定性。尚存在的平均不確定性。n這種不確定性是由信道干擾引起的。這種不確定性是由信道干擾引起的。n對(duì)無(wú)噪信道：對(duì)無(wú)噪信道：H(X|Y)=0。nH(X|Y)H(X)：收到輸出符號(hào)：收到輸出符號(hào)Y以后，總能以后，總能消除一些對(duì)消除一些對(duì)X的不確定性，獲得一些信息。的不確定性，獲得一些信息。 (|)()log (|)ijijijH X Yp abp ab n【定義4-1】 稱信道的輸入空間X對(duì)輸出空間Y的條件熵n為信道疑義度。n信道疑義度的含義是觀察到信道的輸出之后仍然保留的關(guān)于信道輸入的平均不確定性。n這種對(duì)X尚存在的不確定性是由

5、于傳輸過(guò)程中的信道干擾引起的。(|)()log (|)ijijXYH X Yp x yp xy 4.3.3 平均互信息n定義定義4-3 原始信源熵與信道疑義度之差稱為原始信源熵與信道疑義度之差稱為平均互信息。平均互信息。nI(X;Y)=H(X)-H(X|Y)n平均互信息具有非負(fù)性。平均互信息具有非負(fù)性。n含義：接收到信道的輸出符號(hào)集含義：接收到信道的輸出符號(hào)集Y之后，平之后，平均每個(gè)符號(hào)獲得的關(guān)于信道輸入符號(hào)集均每個(gè)符號(hào)獲得的關(guān)于信道輸入符號(hào)集X的的信息量，即通過(guò)信道傳送過(guò)去的信息量。信息量，即通過(guò)信道傳送過(guò)去的信息量。( | )( | )(; )()log()log( ;)( )( )XYX

6、Yp x yp y xI X Yp xyp xyI Y Xp xp y兩個(gè)定理n定理4-1 對(duì)于固定的信道，平均互信息I(X;Y)是信源概率分布p(x)的上凸函數(shù)。n固定信道：信道傳遞概率p(y|x)不變n定理4-2 對(duì)于固定的信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的下凸函數(shù)。n固定信源：信源概率分布p(x)不變( | )( | )(; )()log( | ) ( )log( )( | ) ( )XYXYXp y xp y xI X Yp xyp y x p xp yp y x p x信源信源信道信道平均互信息的例子n例例4-6 信源：信源： 信道：信道：n則互信息量：則互

7、信息量：(0,0)(0) (0|0)(0,1)(0) (1|0)(1,0)(1) (0|1)(1,1)(1) (1|1)p xyp xp yxpp xyp xp yxpp xyp xp yxpp xyp xp yxp011XPppPpp( | )(; )( ;)()log()( )( )XYp y xI X YI Y Xp xyHppH pp y(0)(0,0)(1,0)(1)(1)(0,1)(1,1)(1)p Yppppppp Ypppppp固定信道固定信道p p固定固定從從0 0到到1 1變化變化固定信源固定信源固定固定p p從從0 0到到1 1變化變化4.4 信道的組合n組合方式n 并行

8、：積信道 串行：級(jí)聯(lián)信道n 例如：Internet 例如：GSMn重點(diǎn)介紹級(jí)聯(lián)信道串聯(lián)信道）n假設(shè)串聯(lián)的兩個(gè)信道為信道假設(shè)串聯(lián)的兩個(gè)信道為信道I和信道和信道II，信道，信道I的傳的傳遞概率為遞概率為p(y|x)，信道，信道II的傳遞概率為的傳遞概率為p(z|xy)。n定理定理4-3 若隨機(jī)變量若隨機(jī)變量X,Y,Z構(gòu)成一個(gè)馬爾可夫鏈構(gòu)成一個(gè)馬爾可夫鏈p(z|xy)=p(z|y)），則有），則有nI(X;Z)I(X;Y) I(X;Z)I(Y;Z)n定理定理4-3叫做數(shù)據(jù)處理定理，它的含義是通過(guò)串聯(lián)叫做數(shù)據(jù)處理定理，它的含義是通過(guò)串聯(lián)信道的傳輸，只會(huì)丟失信息，不會(huì)增加信息，至信道的傳輸，只會(huì)丟失信息

9、，不會(huì)增加信息，至多保持原來(lái)的消息量。這是信息不增性原理。多保持原來(lái)的消息量。這是信息不增性原理。信道Ip(y|x)信道IIp(z|xy)XYZ例4-7 兩個(gè)二元對(duì)稱信道串聯(lián)n一個(gè)馬爾可夫鏈，則串聯(lián)信道總的信道矩陣為n那么 I(X;Y)=1-H(p)n I(X;Z)=1-H(2p(1-p)n從圖中能夠看出n I(X;Z)I(X;Y)011/21/2XP1211ppPPpp221222(1)2 (1)2 (1)(1)ppppPPPppppn例4-8n信道I和信道II的信道矩陣分別為nX,Y,Z構(gòu)成一個(gè)馬爾可夫鏈，那么|11110033302/31/311001/32/322Y XZ YPP|11

10、111110033333302/31/311111001/32/326322Z XY XZ YPPP 4.5 信道容量4.5.1 信息傳輸率n在信息傳輸過(guò)程中，信道每傳遞一個(gè)符號(hào)所能攜帶載荷的平均信息量稱為信道的信息傳輸率，記作R。n若平均傳輸一個(gè)符號(hào)需要t秒，而每一個(gè)符號(hào)傳送的信息量為I(X;Y)，則信道每秒傳輸?shù)男畔⒘繛閚通常將Rt稱為信息傳輸速率，或者傳輸速率。(; )RI X Y1(; )tRI X Yt4.5.2 信道容量n定義4-4 信道容量定義為平均互信息的最大值：nC=maxp(x)I(X;Y)n由定理4.2.1知，I(X;Y)是p(x)的上凸函數(shù)，稱使I(X;Y)取最大值的p

11、(x)為最佳輸入分布。n信道容量表示信道傳送信息的最大能力。n由I(X;Y)的定義式可知， I(X;Y)是由信道特性p(y|x)和信源特性p(x)共同決定的，n但是容量C已對(duì)所有n可能的p(x)取最大值，因此n容量C僅與信道特性p(y|x)有關(guān)，n也就是說(shuō)，容量C是信道的固有n特性，與信源無(wú)關(guān)。( | )( | )(; )()log( | ) ( ) log( )( | ) ( )XYXYXp y xp y xI X Yp xyp y x p xp yp y x p x信道容量的例子例4-10）n 信源： 信道：n則互信息量：n從圖中可以看出，當(dāng)=1/2時(shí)，I(X,Y)取最大值nC=1-H(p

12、)011XPppPpp(; )()( )I X YHppH p固定信道固定信道p p固定固定從從0 0到到1 1變化變化4.5.3 三種特殊信道的信道容量n無(wú)噪無(wú)損信道n有噪無(wú)損信道n無(wú)噪有損信道無(wú)噪無(wú)損信道n輸出與輸入是一一對(duì)應(yīng)關(guān)系，n 即信道矩陣為單位矩陣。n因此信道疑義度H(X|Y)=0，噪聲熵H(Y|X)=0。n則I(X;Y) =H(X)-H(X|Y)=H(X)n =H(Y)-H(Y|X)=H(Y)n因此信道容量nC=maxp(x)I(X;Y) )=maxp(x)H(X)=logrn=maxp(x)H(Y)=logs有噪無(wú)損信道n一個(gè)輸入對(duì)應(yīng)多個(gè)互不n 相交的輸出，即信道矩n 陣的每一

13、列只有一個(gè)非n 零元素。n由于知道輸出之后，必然能夠確定其對(duì)應(yīng)的輸入是什么，因此信道疑義度H(X|Y)=0。n則I(X;Y)=H(X)-H(X|Y)=H(X)n因此信道容量nC=maxp(x)I(X;Y)=maxp(x)H(X)=logr1/31/61/200000010000001/43/4P無(wú)噪有損信道n一個(gè)輸出對(duì)應(yīng)多個(gè)互不相交n 的輸入，即信道矩陣的每一行n 只有一個(gè)“1”，其余元素均為0。n由于知道輸出之后，必然能夠確定其對(duì)應(yīng)的輸入是什么，因此噪聲熵H(Y|X)=0。n則I(X;Y)=H(Y)-H(Y|X)=H(Y)n因此信道容量nC=maxp(x)I(X;Y)=maxp(x)H(Y)

14、=logs100100100010001001P4.5.4 對(duì)稱信道的信道容量n定義4-5 信道矩陣的每一行都是其他行的不同排列，則稱此類信道為輸入對(duì)稱信道。n定義4-6 信道矩陣的每一列都是其他列的不同排列，則稱此類信道為輸出對(duì)稱信道。n定義4-7 若一個(gè)離散無(wú)記憶信道，既是輸入對(duì)稱信道，又是輸出對(duì)稱信道，這類信道稱為對(duì)稱信道。0.40.60.60.40.50.5P0.70.20.10.10.70.2P1111336611116633P 1/21/31/61/61/21/31/31/61/2P對(duì)稱信道的容量n定理4-4 若一個(gè)離散對(duì)稱信道有r個(gè)輸入符號(hào)，s個(gè)輸出符號(hào)，則當(dāng)輸入為等概分布時(shí)，達(dá)

15、到信道容量C，且nC=logs-H(p1p2 ps )n 式中，p1 p2 ps 為信道矩陣中的任一行。n“當(dāng)輸入為等概分布時(shí)，達(dá)到信道容量C的含義是最佳輸入為等概分布。對(duì)稱信道容量的例子n例 n這是一個(gè)對(duì)稱信道n最佳輸入為：n信道容量為：nC=logs-H(p1 p2 ps )=log3-H(1/2,1/3,1/6)1/21/31/61/61/21/31/31/61/2P111333XP111111log3logloglog0.1262233664.5.5 一般信道的容量n對(duì)于一般的離散無(wú)記憶信道而言，信道容量的計(jì)算比較復(fù)雜，可以用迭代算法實(shí)現(xiàn)。n迭代步驟如下：n取初始分布p(0)(x)。n

16、根據(jù)公式4-21計(jì)算P(k)(xi|yj)。n根據(jù)公式4-22計(jì)算p(k+1)(xi)。n根據(jù)公式4-23計(jì)算C(k+1)。n假設(shè)| C(k+1) C(k) | ，則轉(zhuǎn)向步驟7。n令k = k+1，轉(zhuǎn)向步驟2。n輸出p(k+1)(xi)和C(k+1)。4.5.6 信源和信道的匹配n信源與信道達(dá)到匹配的含義：信源處于最佳輸入分布，使得信息傳輸率R達(dá)到了信道容量C。n但通常情況下，讓信源處于最佳輸入分布并不容易，此時(shí)信道有剩余：n信道剩余度=C-I(X;Y)n信源編碼的目的就是通過(guò)編碼，改變?cè)夹旁吹慕y(tǒng)計(jì)特性，使得信道剩余度盡可能小。原始信源信道不匹配原始信源信道信源編碼基本匹配本章小結(jié)n信道可以從不同的角度分類。從輸入和輸出符號(hào)的時(shí)間特性分，可以分為離散信道、連續(xù)信道和半連續(xù)信道。從輸入和輸出端的