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

一個信宿；

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

多個信宿；

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

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

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

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

信容量問題更復雜（如最大流-最

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

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

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

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

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