《信息論與編碼》 課件 第7章網(wǎng)絡(luò)信息論初步

1第7章網(wǎng)絡(luò)信息論初步網(wǎng)絡(luò)信息論簡(jiǎn)介網(wǎng)絡(luò)通信的分類(lèi)分布式無(wú)損壓縮網(wǎng)絡(luò)編碼2網(wǎng)絡(luò)信息論簡(jiǎn)介網(wǎng)絡(luò)信息論簡(jiǎn)介3網(wǎng)絡(luò)信息論簡(jiǎn)介網(wǎng)絡(luò)信息論與普通信息論的對(duì)照本章主要內(nèi)容概述4網(wǎng)絡(luò)信息論與普通信息論的對(duì)照普通信息論的研究模型：特點(diǎn)：一個(gè)信源；

一個(gè)信宿；

一個(gè)通道。信源信宿噪聲源信息信息干擾信道5網(wǎng)絡(luò)信息論與普通信息論的對(duì)照網(wǎng)絡(luò)信息論的研究模型：特點(diǎn)：多個(gè)信源；

多個(gè)信宿；

傳輸通道是網(wǎng)絡(luò)式。6網(wǎng)絡(luò)信息論與普通信息論的對(duì)照基本問(wèn)題：網(wǎng)絡(luò)信息論的基本問(wèn)題仍然是有效性和可靠性。7網(wǎng)絡(luò)信息論與普通信息論的對(duì)照有效性：普通信息論：有效性的極限是信源熵H(X)；網(wǎng)絡(luò)信息論：當(dāng)考慮多個(gè)信源之間有合作時(shí)，

有效性的極限是聯(lián)合熵

H(X,Y)=H(X)+H(Y/X)

—分布式壓縮；8網(wǎng)絡(luò)信息論與普通信息論的對(duì)照可靠性：普通信息論：可靠傳輸?shù)臉O限是信道容量；網(wǎng)絡(luò)信息論：當(dāng)傳輸通道是網(wǎng)絡(luò)式的情形，通

信容量問(wèn)題更復(fù)雜（如最大流-最

小割定理等），也需要考慮特殊

的編碼（網(wǎng)絡(luò)編碼）。9網(wǎng)絡(luò)信息論與普通信息論的對(duì)照網(wǎng)絡(luò)信息論與傳統(tǒng)信息論的內(nèi)容對(duì)照分布式無(wú)損壓縮（對(duì)照普通信息論的信源與信源熵：第2章、第5章）網(wǎng)絡(luò)編碼（對(duì)照普通信息論的信道編碼：第3章、第6章）10本章主要內(nèi)容概述由上面的分析，本章主要包括：網(wǎng)絡(luò)信息論的基本概念、分類(lèi)；分布式壓縮；網(wǎng)絡(luò)編碼。11網(wǎng)絡(luò)通信的分類(lèi)網(wǎng)絡(luò)通信的分類(lèi)12網(wǎng)絡(luò)通信的分類(lèi)按信源信宿的數(shù)目分：多播通信：一個(gè)信源，多個(gè)信宿。廣播：一個(gè)信源，任意多個(gè)信宿。信源發(fā)送的信息不針對(duì)特定信宿。網(wǎng)絡(luò)通信：多個(gè)信源，多個(gè)信宿。13網(wǎng)絡(luò)通信的分類(lèi)按信源到信宿是否有中繼分：?jiǎn)翁ㄐ牛盒旁赐ㄟ^(guò)信道直接和信宿通信，不需要中間節(jié)點(diǎn)接力。多跳通信：也叫做中繼通信。信源通過(guò)中間節(jié)點(diǎn)接力，實(shí)現(xiàn)與信宿通信。每一次中間節(jié)點(diǎn)接力，叫做一跳。實(shí)現(xiàn)接力的中間節(jié)點(diǎn)，叫做中繼節(jié)點(diǎn)。14網(wǎng)絡(luò)通信的分類(lèi)中繼通信又可以細(xì)分為兩類(lèi)：放大轉(zhuǎn)發(fā)：中繼節(jié)點(diǎn)直接將接收到的來(lái)自信源的有噪信號(hào)進(jìn)行放大，并將其發(fā)送給后續(xù)目的節(jié)點(diǎn)。解碼轉(zhuǎn)發(fā)：中繼節(jié)點(diǎn)收到前序節(jié)點(diǎn)發(fā)來(lái)的信號(hào)后，先對(duì)接收到的信號(hào)進(jìn)行解調(diào)和解碼，然后將數(shù)據(jù)重新進(jìn)行編碼調(diào)制后發(fā)給后續(xù)節(jié)點(diǎn)。15分布式壓縮分布式壓縮16分布式壓縮分布式壓縮如上圖所示的網(wǎng)絡(luò)通信情形，存在兩個(gè)及以上未經(jīng)壓縮的信源。如果要求接收端能夠無(wú)損地恢復(fù)兩個(gè)信源，最小的總傳輸速率是多少？這就是分布式壓縮問(wèn)題。17分布式壓縮二元離散無(wú)記憶信源的分布式壓縮定義：若有一個(gè)速率對(duì)（R1，R2），R1是X1的傳輸速率，

R2是X2的傳輸速率：可使接收端無(wú)損地恢復(fù)兩個(gè)信源（X1，X2），則稱(chēng)速率對(duì)（R1，R2）對(duì)分布式無(wú)損信源編碼是可達(dá)的。則可達(dá)速率對(duì)（R1，R2）滿(mǎn)足下圖所示的界：18分布式壓縮19分布式壓縮簡(jiǎn)單解釋如下：當(dāng)R1>H(X1)時(shí)，只要R2=H(X2/X1)，就有可能實(shí)現(xiàn)無(wú)損解壓縮；當(dāng)R2>H(X2)時(shí)，只要R1=H(X1/X2)，就有可能實(shí)現(xiàn)無(wú)損解壓縮；當(dāng)R1<H(X1)時(shí)，則需要R2=H(X1，X2)-R1

，即R1+R2=H(X1，X2），才有可能實(shí)現(xiàn)無(wú)損解壓縮。這三段線(xiàn)段組成了所謂的外界（OuterBound）20分布式壓縮另一方面：只要R1>H(X1)并且R2>H(X2)，則一定可以實(shí)現(xiàn)無(wú)損解壓縮。這兩段線(xiàn)段組成了所謂的內(nèi)界（InnerBound）21分布式壓縮內(nèi)界可以理解為兩個(gè)信源不需要合作，實(shí)現(xiàn)無(wú)損解壓縮所需的條件；而外界則是當(dāng)兩個(gè)信源有合作時(shí)的情形。22分布式壓縮有協(xié)助的無(wú)損壓縮問(wèn)題：如果圖中接收者只需要無(wú)損恢復(fù)其中一個(gè)信源（例如X），而另一個(gè)信源（協(xié)助者，Y）的編碼器向解碼器提供經(jīng)編碼的邊信息來(lái)幫助降低第一個(gè)編碼器的碼率。那么，

X所需要傳輸?shù)男畔⒙适嵌嗌伲?3分布式壓縮24分布式壓縮此時(shí)，內(nèi)界和外界如上圖所示。簡(jiǎn)單解釋如下：如果沒(méi)有協(xié)助者，即R2=0，則R1>=H(X)對(duì)無(wú)損解壓縮X是充分必要的；如果協(xié)助者無(wú)損地將Y發(fā)送給解碼器，即R2>=H(Y)時(shí)，則R1>=H(X/Y)對(duì)無(wú)損解壓縮X是充分必要的。當(dāng)R2<H(Y)時(shí)，接收端不能無(wú)損解壓縮Y，只能得到一個(gè)關(guān)于Y的有損估計(jì)，設(shè)為Z；則需要R1>=H(X/Z)對(duì)無(wú)損解壓縮X是充分必要的。25網(wǎng)絡(luò)編碼網(wǎng)絡(luò)編碼26網(wǎng)絡(luò)編碼蝶形網(wǎng)絡(luò)問(wèn)題：27網(wǎng)絡(luò)編碼圖中，節(jié)點(diǎn)1希望各發(fā)送一個(gè)2bit的消息給目標(biāo)節(jié)點(diǎn)6和7；假設(shè)所有鏈路的容量都是1bit。因?yàn)閮蓚€(gè)消息都必須通過(guò)鏈路（4，5）發(fā)送，因此，在傳統(tǒng)點(diǎn)對(duì)點(diǎn)通信模式下（每個(gè)節(jié)點(diǎn)只進(jìn)行接收-轉(zhuǎn)發(fā)操作，稱(chēng)為路由），需要兩個(gè)單位時(shí)間才能完成。28網(wǎng)絡(luò)編碼如果我們?cè)试S節(jié)點(diǎn)除了進(jìn)行路由操作，還可以完成簡(jiǎn)單的運(yùn)算，對(duì)圖7-10的網(wǎng)絡(luò)，我們假定可以進(jìn)行“模2和”運(yùn)算，那么該2bit的消息就可以在一個(gè)單位時(shí)間內(nèi)送達(dá)兩個(gè)接收者。29網(wǎng)絡(luò)編碼方式如下：中繼節(jié)點(diǎn)2、3和5只進(jìn)行路由操作（接收-轉(zhuǎn)發(fā)），而中繼節(jié)點(diǎn)4發(fā)送從節(jié)點(diǎn)2和節(jié)點(diǎn)3收到的信息的模2和；節(jié)點(diǎn)6（接收者1）在接收到從節(jié)點(diǎn)2傳送過(guò)來(lái)信息和從節(jié)點(diǎn)5轉(zhuǎn)發(fā)的（從節(jié)點(diǎn)4傳送過(guò)來(lái)）信息后，就可以通過(guò)兩者的模2和得到所需要的信息；節(jié)點(diǎn)7（接收者2）也可以通過(guò)類(lèi)似的操作，得到所需要的信息。30網(wǎng)絡(luò)編碼網(wǎng)絡(luò)上節(jié)點(diǎn)進(jìn)行的這種運(yùn)算稱(chēng)為“網(wǎng)絡(luò)編碼”。31網(wǎng)絡(luò)編碼于是，和傳統(tǒng)信息論相似，有以下兩個(gè)問(wèn)題：（1）多信源多信宿網(wǎng)絡(luò)通信的容量（最大通信能力）是多少？（2）為達(dá)到網(wǎng)絡(luò)通信容量，需要采用什么樣的方法？32網(wǎng)絡(luò)編碼--網(wǎng)絡(luò)通信容量單播圖網(wǎng)絡(luò)的通信容量單播網(wǎng)絡(luò)的通信容量，等于最小割集的容量，或者稱(chēng)為最小割集的最大流量（最小割-最大流），即式中，S是有向圖的一個(gè)割集。33網(wǎng)絡(luò)編碼--網(wǎng)絡(luò)通信容量多播圖網(wǎng)絡(luò)的通信容量圖中，信源節(jié)點(diǎn)1希望向信宿節(jié)點(diǎn)集傳送不同消息（多播）。34網(wǎng)絡(luò)編碼--網(wǎng)絡(luò)通信容量信宿節(jié)點(diǎn)集為D的多播圖網(wǎng)絡(luò)容量存在上界：式中，C(S)是從信源節(jié)點(diǎn)1到信宿節(jié)點(diǎn)j的一個(gè)割集S的容量。式的右端，可以理解為集合D中的所有目的節(jié)點(diǎn)容量（最大流-最小割）中的最小值。35網(wǎng)絡(luò)編碼網(wǎng)絡(luò)編碼分為線(xiàn)性網(wǎng)絡(luò)編碼和非線(xiàn)性網(wǎng)絡(luò)編碼，僅介紹線(xiàn)性網(wǎng)絡(luò)編碼。所謂線(xiàn)性網(wǎng)絡(luò)編碼，是指中繼節(jié)點(diǎn)所使用的網(wǎng)絡(luò)編碼函數(shù)和譯碼函數(shù)都是線(xiàn)性函數(shù)，一般僅為簡(jiǎn)單的加法和乘法運(yùn)算。36網(wǎng)絡(luò)編碼線(xiàn)性網(wǎng)絡(luò)編碼示意圖如圖所示：