第8章網(wǎng)絡(luò)信息理論簡介

1、普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著1第8章 網(wǎng)絡(luò)信息理論簡介n8.1 概論n8.2 網(wǎng)絡(luò)信道的分類n8.3 網(wǎng)絡(luò)信道的信道容量域n8.4 網(wǎng)絡(luò)中相關(guān)信源的信源編碼普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著28.1 概論概論n單用戶通信系統(tǒng)：只有一個(gè)輸入信源和一個(gè)輸出信源，單向通信。n多用戶通信系統(tǒng)：信道的輸入端和輸出端涉及到兩個(gè)或兩個(gè)以上的信源和信宿，雙向通信。n網(wǎng)絡(luò)信息論：還有許多未解決的問題，至今沒有一套完整的網(wǎng)絡(luò)信息理論。即使將來能夠發(fā)現(xiàn)，也可能因?yàn)樘珡?fù)雜而不能實(shí)現(xiàn)。研究的目的在于可告訴通信設(shè)計(jì)者距離網(wǎng)絡(luò)最優(yōu)化多近，也可啟發(fā)設(shè)計(jì)者獲得提高通信性能的

2、途徑。普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著3網(wǎng)絡(luò)信息論研究的主要內(nèi)容：n網(wǎng)絡(luò)信道的信道容量。這種信道的容量不能簡單地用一實(shí)數(shù)表示，可傳輸?shù)男畔⒙室膊荒苡谜龑?shí)軸上一個(gè)區(qū)間來代表，而需用多維空間中的一個(gè)區(qū)域來表示。n網(wǎng)絡(luò)信道編碼定理。即證明在上述網(wǎng)絡(luò)信道容量范圍內(nèi)，一定有一種編碼方式，能夠可靠地傳輸信息。n相關(guān)信源的信源編碼問題。研究相互關(guān)聯(lián)的多個(gè)信源進(jìn)行無失真和有失真編碼時(shí)的可達(dá)速率區(qū)域。8.1 概論概論普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著4（1）多址接入信道）多址接入信道(MAC)： 多個(gè)信道輸入信號，可供多個(gè)信源同時(shí)接入，但只有一個(gè)信道輸出信號。

3、n如衛(wèi)星上行、移動上行、光纖上行；CDMA、TDMA 8.2 網(wǎng)絡(luò)信道的分類信源1信源2信源M編碼器1編碼器2編碼器M信道譯碼器U1U2UMX2XMYU1U2UMX1普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著5(2)廣播信道廣播信道：單一輸入端口和多個(gè)輸出端口n與一般的廣播概念不同的是，各信宿要接收的信息并不一定相同。n如衛(wèi)星下行、CATV、移動下行信源1信源2信源M譯碼器1譯碼器2譯碼器M信道編碼器YMXU1U2UMY18.2 網(wǎng)絡(luò)信道的分類普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著6（3）中繼信道）中繼信道：可以看成廣播信道和多址接入信道的組合，是一對用戶之

4、間經(jīng)過多種途徑中轉(zhuǎn)所進(jìn)行的單向通信。一個(gè)輸入信號和一個(gè)輸出信號。n如中繼微波接力系統(tǒng)、一對地面站可經(jīng)一個(gè)或多個(gè)衛(wèi)星中轉(zhuǎn)或者經(jīng)地面通信轉(zhuǎn)接而實(shí)現(xiàn)單向通信。 信源中繼點(diǎn)信道譯碼器XY1X1Y信道信道8.2 網(wǎng)絡(luò)信道的分類普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著7（4）雙向信道）雙向信道：兩個(gè)發(fā)送端和兩個(gè)接收端n許多實(shí)用信道本質(zhì)上都是雙向信道。 信源1接收端2編碼器1譯碼器2譯碼器1編碼器2接收端1信源2雙向信道X1X2Y1Y28.2 網(wǎng)絡(luò)信道的分類普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著8（5）多端網(wǎng)絡(luò)）多端網(wǎng)絡(luò)：由多個(gè)信源和多個(gè)信宿經(jīng)過多個(gè)信道組成 ，一般要用

5、圖論方法研究。信源1編碼器1譯碼器1信宿1通信網(wǎng)X1Y1信源2信源m編碼器2編碼器m譯碼器2譯碼器n信宿2信宿nU2UmX2XmY2Ym8.2 網(wǎng)絡(luò)信道的分類普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著98.3.1 離散多址接入信道n為了信息的可靠傳輸，各發(fā)送者不但要克服信道噪聲，而且還要克服各發(fā)送端彼此之間的串?dāng)_。 8.3 網(wǎng)絡(luò)信道的信道容量域信源U1信源U2編碼器f1編碼器f2信道p(y/x1,x2)X2YU1U2X1譯碼器g普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著10n使 Pe 0的速率對 (R1,R2) 稱為可達(dá)速率對，所有可達(dá)速率對的集合稱為多址信道的

6、信道容量域。n定理： 二址接入信道 X1X2,P(y|x1x2),Y的容量區(qū)域，由滿足下述凸殼的閉包給定n其中 , C(P1,P2) 是在乘積空間X1X2上，對所有可能的輸入概率分布求得的可達(dá)速率對(R1,R2)的集合。 12121122211212( ,)(,):0(;/)0(;/)0(,; )C P PR RRI X YXRI XYXRRI XXY121122( ,)( )()P x xP x P x普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著11 R2 I(X1,X2;Y)I(X2;Y/X1) A C I(X2;Y) D 0 B R1 I(X1;Y) I(X1;Y/X2)

7、I(X1,X2;Y) 二址接入信道的可達(dá)速率域普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著12nB點(diǎn)：發(fā)送者2不傳送任何信息時(shí)，發(fā)送者1可傳送的最大信息率。n此時(shí)發(fā)送者 1 可傳送的信息率 大于單用戶的情況 12(;/)I X YX1(; )I X Y普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著13nD 點(diǎn)：發(fā)送者1以最大的信息傳輸率發(fā)送時(shí)，發(fā)送者2能夠發(fā)送的最大信息傳輸率。n該值是在信道中將X2傳送到Y(jié)，而把X1看作為噪聲而求得的。此時(shí)，相當(dāng)于X2以信息率 I(X2;Y) 在單用戶信道中傳輸?shù)慕Y(jié)果。n因?yàn)?I(X2;Y)=I(X1,X2;Y)-I(X1;Y/X2)

8、，所以，當(dāng)接收端知道X2的碼字也在發(fā)送時(shí)，就要在信道傳輸?shù)慕Y(jié)果中將X2的碼字“減”出來。n區(qū)域中的點(diǎn) A，C和B，D點(diǎn)有相似的含義。 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著14n當(dāng)給定某個(gè)輸入分布 ，可得某區(qū)域C(P1 , P2)；不同的輸入分布可得不同的區(qū)域。因此二址接入信道的容量區(qū)是所有可能C(P1 , P2) 的凸閉包，是一個(gè)多角形的凸包。 121122( ,)( )()P x xP x P x112211221122112()()221()()1212()()max(;/)max(;/)max(,; )P xPxP xPxP xPxCI X YXCI XYXCI X

9、XY R2C12C2 0 C1 C12 R1 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著15n上述結(jié)論很容易推廣到 T 個(gè)獨(dú)立發(fā)送端的一般情況。已知條件概率 p(y/x1,x2,xT)，此時(shí)各發(fā)送端可達(dá)速率范圍為1111( ),( )max(;/)(1,2, )TtttttTP xPxRCI X Y XXXXtT普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著16n例：例：求二址獨(dú)立的二元對稱信道的容量區(qū)域，發(fā)送者X1和發(fā)送者X2，接收端Y。 1p1 0 0X1 p1 p1 1 1 1p1 1p2 Y 0 0X2p2 p2 1 1 1p2普通高等教育“十一五”國家級規(guī)

10、劃教材信息論基礎(chǔ) 曹雪虹編著17n計(jì)算得第一信道的信道容量 C1=1H(p1), 第二信道的信道容量為 C2=1H(p2)。n因?yàn)檫@兩信道是互相獨(dú)立的，所以沒有彼此干擾。R2 C2=1-H(p2) 容量區(qū)域 0 C1=1-H(p1) R1獨(dú)立二進(jìn)制對稱信道的容量普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著18n例：二址接入二元和信道 Y=X1+X2 R2(bit)1.5 AC2=1 0.5 B 0 0.5 C1= 1 C12=1.5 R1(bit) 圖8-12 二址二元和信道的容量區(qū)域普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著19n各信源來的信號在接收端相加，并受

11、加性高斯噪聲 ( 均值為零，方差為 ) 的干擾。n信道輸出n二址(m=2)時(shí)，X1、X2與Z相互獨(dú)立 8.3.2 高斯多址接入信道高斯多址接入信道 1miiYXZ2n1222SSnE YPP普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著20n信號平均功率受限：n可達(dá)速率區(qū)是滿足下式的凸閉包：1122211212(;/)(;/)(,; )RI X YXRI XYXRRI XXY122212,SSE XPE XP8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著218.3.2 高斯多址接入信道高斯多址接入信道 12212122121

12、21212121( ; /)( /)( /,)(/)(/,)(/)( /,)()( )1()log22CCCCCCCCCnI X Y XH Y XH Y X XH XXZ XH XXZ X XH X Z XH Z X XH X ZH ZH X Ze普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著22n在平均功率受限的情況下，正態(tài)分布時(shí)熵最大n即只有當(dāng)輸入 ，并且互相獨(dú)立時(shí)上式才能達(dá)到極大值。112212211(;/)log2()log2221log(1)2SnnSnI X YXe PeP 8.3.2 高斯多址接入信道高斯多址接入信道 1212(0,),(0,)SSXNPXNP普通高等

13、教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著231122121212111222221212121221max (;/)log(1)21max (;/)log(1)21max (,; )log(1)2XXXXXXSP PnSP PnSSP PnPRCI X Y XPRCI X Y XPPRRCI X X Y8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著24 R2 C12 C2 A C C12-C1 D 0 B R1 C12-C2 C1 C12高斯二址接入信道的可達(dá)容量域8.3.2 高斯多址接入信道高斯多址接入信道 12121222

14、122SnSnSSnPRCPRCPPRRC普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著25n凸五邊形：nB點(diǎn)是發(fā)送者 1 能傳送的最大信息傳輸率C1；nD點(diǎn)是發(fā)送者1傳送最大信息率C1情況下，發(fā)送者2所能傳送的信息率C12C1。這時(shí)發(fā)送者1被看成噪聲，計(jì)算輸出Y與X2之間的互信息得2122SSnPRCP8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著26n在高斯信道下，可把譯碼考慮成兩步： 接收端將發(fā)送端1看成噪聲的一部分，先將發(fā)送端2的碼字譯碼出來。若 ，譯碼錯(cuò)誤概率可達(dá)任意小。 將已成功譯出的發(fā)送端2“減”去，若 則發(fā)送

15、端 1 的碼字能成功譯出。n所以，容量區(qū)域中各個(gè)角點(diǎn)的速率對是可達(dá)的。2122SSnPRCP112SnPRC8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著27 R2 C12 C2 A C C12-C1 D 0 B R1 C12-C2 C1 C12n在許多實(shí)際情況中，常采用時(shí)分多路通信方式。但該方式不是最佳的方案。若兩發(fā)送端各占一半的傳送時(shí)間，可達(dá)容量區(qū)域是 AB 連線所圍的區(qū)域。 8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著28n若設(shè)在總傳送時(shí)間 T 內(nèi)，QT用來傳送X1，(1

16、- Q)T 用來傳送X2，其中 。那么在傳送 X1時(shí)， ；在傳送 X2 時(shí)， 。若保持平均功率不變，則傳送 X1 時(shí)功率可以提高到 ，而 X2功率可提高到 ?？傻?1Q20X 10X 1/SPQ21SPQ8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著29112log(1)2SnPQRQ222(1)log 12(1)SnPQRQ8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著30 R2 C12 C2 A C E C12-C1 D 0 B R1 C12-C2 C1 C12nQ 不同時(shí)，

17、得到不同的 (R1,R2)，即曲線 AEB 所決定的區(qū)域。顯然，除了 Q =1，Q=0 和 Q = 即 B,A,E 三點(diǎn)外，其它情況都在容量界線 ( 截角矩形 ) 之下?？梢娫跁r(shí)分方式下，C,D 對應(yīng)的速率對是達(dá)不到的。112/()SSSPPP普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著31n對于頻分多路通信方式，每個(gè)發(fā)送者的傳輸速率依賴于所允許傳輸?shù)膸?。考慮信號功率分別為 PS1和PS2的二個(gè)發(fā)送端，所占帶寬為 W1和W2。這兩帶寬不重疊，且總帶寬 W=W1+W2。令Q =W1/W是發(fā)送者 1 所占帶寬比，(1-Q)=W2/W是發(fā)送者 2 所占帶寬比，可達(dá)速率對是 12110

18、12202log 12log 12SSPWRN WPWRN W普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著32n將Q和（1Q）代入，令w=1,可得單位頻帶內(nèi)傳輸率n因此，改變W1和W2( 即 Q 不同時(shí) )，給出的可達(dá)速率區(qū)也為圖中曲線 AEB 所決定的區(qū)域。110log(1)2SPQRN WQ220(1)log 12(1)SPQRN WQ普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著33n在相同的平均功率約束下，時(shí)分多址和頻分多址可達(dá)到的信息傳輸速率均小于理論給出的容量域。但適當(dāng)設(shè)計(jì)時(shí)隙分配或帶寬分配的比例，時(shí)分多址和頻分多址都可使速率達(dá)到理論容量域所給的最大值，即

19、E點(diǎn)。n碼分多址技術(shù)中所有信道輸入信號都占用信道的全部帶寬和時(shí)間，各信號間不存在時(shí)隙分配或帶寬分配問題。因此，碼分多址的可達(dá)速率域與理論容量域一致。在這一意義上，我們認(rèn)為碼分多址是比較理想的方式。 8.3.2 高斯多址接入信道高斯多址接入信道 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著348.4 網(wǎng)絡(luò)中相關(guān)信源的信源編碼網(wǎng)絡(luò)中相關(guān)信源的信源編碼n研究多個(gè)相關(guān)信源的編碼問題;n在實(shí)際通信中，常常某個(gè)信宿收到來自不同源的編碼信息。 各信源獨(dú)立：分別處理，單信源通信； 各信源相關(guān)：各種相關(guān)信源編碼模型。普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著35信源1信源2編 碼

20、器1編碼器2譯碼器1譯碼器2u1lu2lR22R21R12u”1lu”2lu2lR11u1l兩個(gè)信源和兩個(gè)譯碼器之間可有16種不同的聯(lián)接方式 8.4.1 相關(guān)信源編碼相關(guān)信源編碼普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著36兩個(gè)相關(guān)信源編碼的最基本結(jié)構(gòu)：兩個(gè)信源均為離散無記憶信源。信源1信源2編碼器1編碼器2譯碼器u1lu2lR2R1u1lu2l普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著37n采用一個(gè)編碼器：對于單個(gè)信源U進(jìn)行編碼，傳輸信息率需滿足RH(U)，才能實(shí)現(xiàn)無失真編碼；對于兩個(gè)信源U1和U2聯(lián)合編碼，傳輸信息率需滿足RH(U1,U2)，才能使譯碼錯(cuò)誤概

21、率為任意小。 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著38n采用二個(gè)獨(dú)立的編碼器：uR1H(U1), R2H(U2) R=R1+R2=H(U1)+H(U2)u二個(gè)信源相關(guān)：R=? RH(U1,U2) 普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著39n例 設(shè)信源X1和X0相互獨(dú)立， 若X2=X1X0，則 H(X1)=H(X2)=1 bit/sym H(X2/X1)=H(X0)=0.5 bit/symn因此，在已知X1的情況下，要確定X2只需0.5 bit，而不需1 bit，因?yàn)閄1與X2有關(guān)聯(lián)性，已知X1時(shí)，已提供了一些關(guān)于X2的信息量，因此只需再獲得H(X2/X

22、1)的信息量，就能完全確定X2。5 . 05 . 0101PX11. 089. 0100PX5 . 05 . 0102PX普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著40n由此可見，編碼時(shí)只需保證： R1 H(X1)，R2H(X2/X1)，RH(X1)+H(X2/X1)=H(X1,X2)n這種X1所能提供關(guān)于X2的信息，或X2所能提供關(guān)于X1的信息，稱為邊信息。普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著41n相關(guān)信源編碼定理(Slepian-Wolf)： 對于任意離散無記憶信源X1和X2，所有的可達(dá)速率對(R1,R2)滿足相關(guān)信源編碼1122211212(/)(/

23、)(,)RH XXRH XXRRH XX R2H(X1,X2) 可達(dá)速率域 H(X2)H(X2/X1) H(X1/X2) H(X1) H(X1,X2) R1普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著428.4.2 具有邊信息的信源編碼具有邊信息的信源編碼 n譯碼器只是希望估計(jì)出信源U1的輸出;n對信源U2的數(shù)據(jù)進(jìn)行編碼的目的，只是作為邊信息以輔助譯碼器恢復(fù)信源U1，而不需要保留信源U2本身的信息。n因此，U2信源所提供的邊信息可以壓縮到小于它自身的熵值，而信源U1的數(shù)據(jù)能夠很好地進(jìn)行無失真壓縮。 信源U1信源U2編碼器編碼器R2U1R1譯碼器普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著43n由于U2依賴于U1，可看成是將U1作為輸入的虛擬信道的輸出。U2經(jīng)編碼器輸出可用輔助的隨機(jī)變量 Z 來描述。n譯碼器需依據(jù)U1的壓縮數(shù)據(jù)流和Z重現(xiàn)輸出U1。信源U1虛擬信道編碼器編碼器U2U1U1譯碼器Z單符號具有邊信息的信源編碼普通高等教育“十一五”國家級規(guī)劃教材信息論基礎(chǔ) 曹雪虹編著44n若用速率R2來描述U2