網(wǎng)絡(luò)編碼--信道編碼最權(quán)威專家王新梅教授學(xué)術(shù)講座ppt

1、1網(wǎng)絡(luò)編碼西安電子科技大學(xué)ISN國家重點實驗室2005年3月2 概 要1. 網(wǎng)絡(luò)編碼的提出及現(xiàn)狀2. 網(wǎng)絡(luò)編碼的基本原理3. 基于網(wǎng)絡(luò)編碼的糾錯碼4. 無線組播中的網(wǎng)絡(luò)編碼5. 結(jié)束語31. 網(wǎng)絡(luò)編碼的提出在現(xiàn)有通信網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點只是對收到的信息進行存儲和轉(zhuǎn)發(fā)，扮演著轉(zhuǎn)發(fā)器的角色。但是從信息理論的觀點來說，沒有理由讓節(jié)點只能進行存儲轉(zhuǎn)發(fā)，可以讓節(jié)點對多條輸入邊上收到的信息進行一定的線性或非線性操作（編碼），然后再發(fā)送出去，起著編碼器的作用。 網(wǎng)絡(luò)編碼正是根據(jù)這思想而產(chǎn)生的。在接收節(jié)點上，通過一定的運算，譯出信源所發(fā)的信息。4網(wǎng)絡(luò)編碼的提出n2000年，R. Ahlswede等人在IEEE t

2、rans-IT上發(fā)表了一篇題為“網(wǎng)絡(luò)信息流”的文章 ，提出了網(wǎng)絡(luò)編碼的概念；n那么， 什么是網(wǎng)絡(luò)編碼呢？ 網(wǎng)絡(luò)編碼能給我們帶來什么好處呢？5網(wǎng)絡(luò)編碼的提出n（點對點點對點的最小割最大流定理）的最小割最大流定理） 對于已知的網(wǎng)絡(luò)流圖，從發(fā)點 到收點 的流量 的最大值小于或等于任何一個割切的容量，即 記 。 min( , )urcut S uSuurmin( , )uCcut S u9uC 6網(wǎng)絡(luò)編碼的提出一個組播(multicast: point to multipoint)傳輸，信源為 ，接收節(jié)點集合為 ，那么可達最高組播速率為 如果采用傳統(tǒng)傳輸方法，可能無法達到速率 。如果采用網(wǎng)絡(luò)編碼，可達

3、到該最高速率 。S12 ,.,Nu uu12min,.,NuuuCCCCCC7網(wǎng)絡(luò)編碼的提出一個經(jīng)典例子2C 采用網(wǎng)絡(luò)編碼后，達到速率 。8網(wǎng)絡(luò)編碼的提出網(wǎng)絡(luò)編碼帶來的好處：n使組播傳輸速率達到最小割最大流決定的網(wǎng)絡(luò)容量的上限n節(jié)省網(wǎng)絡(luò)帶寬資源消耗n均衡網(wǎng)絡(luò)負載n提高網(wǎng)絡(luò)魯棒性9網(wǎng)絡(luò)編碼的發(fā)展過程n2000年，Ahlswede等提出了網(wǎng)絡(luò)編碼的概念。n2002年，Koetter等給出了網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造算法，是指數(shù)時間算法（集中式）。n2002年，Cai等提出了基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)糾錯碼概念。n2002年， Cai等提出了采用網(wǎng)絡(luò)編碼時的信息完安全性問題。n2003年，Sander等給出了網(wǎng)絡(luò)編

4、碼的多項式時間算法（集中式）。 n2003年，Chou等提出了分布式網(wǎng)絡(luò)編碼，通過仿真得到其性能。n2003年，Ho等也提出了隨機網(wǎng)絡(luò)編碼（分布式）。n2004年，Wu等將網(wǎng)絡(luò)編碼應(yīng)用于無線網(wǎng)絡(luò)以節(jié)省能量。10網(wǎng)絡(luò)編碼的現(xiàn)狀n線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼；n分布式網(wǎng)絡(luò)編碼和集中式網(wǎng)絡(luò)編碼；n網(wǎng)絡(luò)編碼在組播和非組播網(wǎng)絡(luò)中的應(yīng)用n目前，組播集中式線性網(wǎng)絡(luò)編碼算法主要有兩種：代數(shù)構(gòu)造方式和多項式時間算法；112. 網(wǎng)絡(luò)編碼的基本原理n信息傳輸網(wǎng)絡(luò)可用圖 表示n信源節(jié)點集：n信宿節(jié)點集：n邊 的頭節(jié)點用 表示 邊 的尾節(jié)點用 表示( ,)G V E12 ,s sV12 ,Uu uV( )h ev( )

5、t eveen假設(shè)每條邊容量為1比特/單位時間（可通過合適選取單位時間大小和將鏈路進行拆分實現(xiàn)）12網(wǎng)絡(luò)編碼的基本原理n網(wǎng)絡(luò)編碼的數(shù)學(xué)描述 (適用于組播和非組播傳輸） 對邊集 中的每條邊 ，存在一種 映射： 這是對應(yīng)于每條邊的編碼函數(shù)。 ( ,)ev vE22: ( ):mmee t evfFF13網(wǎng)絡(luò)編碼的基本原理n網(wǎng)絡(luò)編碼的數(shù)學(xué)描述(適用于組播和非組播傳輸） 目的節(jié)點 為了得到所需信息，存在映射： 映射 是對應(yīng)于目的節(jié)點 的第 個信源符號的譯碼函數(shù)。 ,22: ( ):mmu ie t eugFF,u iguiu14網(wǎng)絡(luò)編碼的基本原理n線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造 設(shè)所有信源 的總信息輸出速率是

6、 比特/單位時間。把它們的輸出進行一個定序，如下： 其中 是節(jié)點 的信息輸出速率。12,.v vn11121212( ,1),.,( ,( ), (,( )1),.,(,( )(), .X vX vvX vvX vvv( )iviv15網(wǎng)絡(luò)編碼的基本原理n線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造 設(shè) 是無延遲的通信網(wǎng)絡(luò)。我們稱這樣的編碼為線性網(wǎng)絡(luò)編碼，如果對于網(wǎng)絡(luò)中的每一條邊 的傳輸符號均滿足： 其中 。 ( ,)G V E,: ()( ),: ()( )( ) ( )( , )( ) e ee h et ei ee ee h et eevev ie如果節(jié)點 不是一個信源節(jié)點否則,2,mi ee eF( , )

7、ev v16網(wǎng)絡(luò)編碼的基本原理n線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造 定義 矩陣 和 矩陣 如下： 則系統(tǒng)轉(zhuǎn)移矩陣為：1()MA IFnEAEEF, ()0 ji eji jt eA是信源節(jié)點否則, ( )()0 ije eiji jh et eF否則A是信源輸出到所有鏈路的轉(zhuǎn)移矩陣，1()IF是鏈路間的轉(zhuǎn)移矩陣。17網(wǎng)絡(luò)編碼的基本原理n組播線性網(wǎng)絡(luò)編碼成功的條件 組播通信網(wǎng)絡(luò)中， 信源輸出向量： 接收節(jié)點 接收向量: 其中, 是接收節(jié)點 的系統(tǒng)轉(zhuǎn)移矩陣。 于是，為了由接收到的信息向量 解出信 源輸入 ，則必須要求系統(tǒng)轉(zhuǎn)移矩陣 可逆。12 . nz zzz zuuM r rz zuMuur ruMu,1,2

8、, . uuuu nrrrr rz z183. 基于網(wǎng)絡(luò)編碼的糾錯碼 基于網(wǎng)絡(luò)編碼的差錯控制是針對網(wǎng)絡(luò)、而非一條鏈路或一條路徑進行操作的。通過合適的選擇信源空間，可以糾正傳輸網(wǎng)絡(luò)中幾條鏈路上發(fā)生的傳輸錯誤，這是一個比較新的差錯控制方式，稱之為基于網(wǎng)絡(luò)編碼的差錯控制 。19基于網(wǎng)絡(luò)編碼的糾錯碼n參與多播傳輸?shù)逆溌窋?shù)用 表示。n組播網(wǎng)絡(luò)的網(wǎng)絡(luò)容量 為 比特/單位時間。 KnC20基于網(wǎng)絡(luò)編碼的糾錯碼n如果從某條鏈路上輸出的符號不等于輸入的符號，那么稱發(fā)生錯誤。n如果在傳輸網(wǎng)絡(luò)中總共有 條鏈路發(fā)生錯誤，就稱為網(wǎng)絡(luò)發(fā)生了 個錯誤。n如果一個基于網(wǎng)絡(luò)編碼的糾錯碼能糾正所有錯誤個數(shù)小于等于 的情況，就稱該

9、碼是 -差錯控制碼。TTTT21基于網(wǎng)絡(luò)編碼的糾錯碼 把發(fā)生在傳輸網(wǎng)絡(luò)上的錯誤用一個 維行向量 表示，稱為錯誤向量。如果其 中有 個分量不為零，則稱錯誤向量重為 。 12( .)Ke eee e,1,2,12 . . uuu nnuurrrz zzMG e e接收符號:網(wǎng)絡(luò)譯碼后:1,1,2,1,2,1 . . uuu nuuu nuuuyyyrrrMGMz ze e(當有錯誤發(fā)生時):ttK其中 是 的子矩陣。uG1()IF22基于網(wǎng)絡(luò)編碼的糾錯碼uU1( , ):( )uuHt uGMwte ee e對于接收節(jié)點 , 定義 t-錯誤圖樣集合如下：對于接收節(jié)點 ，定義t-錯誤圖樣的差分集合如

10、下：1( , )- : ,( , ) :( )2 uuHt ut uGMwtfg g g ge ee euU(,)u Ut ut 讓23基于網(wǎng)絡(luò)編碼的糾錯碼對于任意 , 和 可分,即能糾任意重量小于等于 t 的錯誤，當且僅當, z zz zZz z( ) t zzzz z z(如果存在 和 ，滿足 ，則存在錯誤圖樣 和 ，使 ，即 ，則會出現(xiàn) 和 不可分的情況。)( ) t zzzzz z z zg ggzzzzggzzzzz z z zg24基于網(wǎng)絡(luò)編碼的糾錯碼對于一個線性網(wǎng)絡(luò)編碼,要使任意兩個信源向量 和 可分, 當且僅當( ) ( )tt 0 0z zz zZ =z z z z25基于網(wǎng)

11、絡(luò)編碼的糾錯碼z z z z,z z z zZ 如果能夠構(gòu)造一個 奇偶校驗矩陣 , 滿足對于所有的 ,有()nknHTHw w0 0( ) tw0w0那么讓 （ 是 維空間）,則對于任意 , 和 可分。 : :, TnqHZ :Fz zz z0 0z z關(guān)鍵問題：給定一個有限域 ， 值能夠達到多大？ qFkkZ :26基于網(wǎng)絡(luò)編碼的糾錯碼矩陣 的構(gòu)造(Varshamov 算法）：H()nkn構(gòu)造過程：1: 將 劃分成多個子集合 。 其中 對于 必須滿足 且向量 的最后一個非零分量的位置是 。( ) t( )(0,1,., )it in0( ) t 0 0( )(1)itin w w( ) tw

12、 ww wi27基于網(wǎng)絡(luò)編碼的糾錯碼2： 令 維列向量空間 ，1 nkq0 0KF()nk111:, (, .,)( )iiijjjniwwwwt k kk kh h0 0w wK(2)nkiqinKFH1i 是由 的前 列向量得到，即28基于網(wǎng)絡(luò)編碼的糾錯碼(1) 從 中任選一列作為 。1n kqKF1h hinH3：(2) 從 中任選一列作為 。2()n kq1 1h hKF2h h(i) 從 中任選一列作為 。11(,.,)n kqii2 2h hhh hhKFih h持續(xù)上面操作直到 ，因此得到矩陣 。29基于網(wǎng)絡(luò)編碼的糾錯碼11( )(,.,)0n kTTTiiGFq2 2hhhhh

13、hK可成功構(gòu)造出 的條件：H對于線性網(wǎng)絡(luò)編碼，如果 ，則對任意 有1(,.,)( )niwwtw w1(, . ,)( )niwwtw w( )0GF q30基于網(wǎng)絡(luò)編碼的糾錯碼11( )(,.,)0( ) /(1)0( ) /(1)n kTTTiin kin kiGFqqtqqtq 2 2hhhhhhK可成功構(gòu)造出 的條件：H12112( ) /(1)(1)/(1)(1)( )(1)1)/(1)(1)tjitjjjtKUqjtqqqKUqj因為31基于網(wǎng)絡(luò)編碼的糾錯碼可成功構(gòu)造出 ，即構(gòu)造出基于網(wǎng)絡(luò)編碼的糾錯碼，可糾任何滿足 的錯誤 。211(1)tn kjjKqUqj因此當有限域大小 滿足

14、Hq12( .)Ke eet12( .)Ke eee e32基于網(wǎng)絡(luò)編碼的糾錯碼根據(jù)上述構(gòu)造校驗矩陣的方法，對于給定的有限域 可得到 的一個下界值：k211(1)tn kjjKqUqjqF但此構(gòu)造方法復(fù)雜度過大，有待找出一種可行的方法，來構(gòu)造出 達到該下界值的 校驗矩陣。k()nknk的一個上界值（Hamming 界）：0(1)ntiiqnqi Z其中min( , )u Uncut s u33易知 ，為使 ， ，根據(jù)下界值知 就可以構(gòu)造出該糾錯碼。需要計算的差分錯誤圖樣的總個數(shù)有 基于網(wǎng)絡(luò)編碼的糾錯碼小規(guī)模網(wǎng)絡(luò)的糾錯碼構(gòu)造：5k 7n 1t 82q 122778(1)(1) )/(1)4289

15、7C qCqq344. 無線組播中的網(wǎng)絡(luò)編碼無線組播特性：如果節(jié)點i向節(jié)點j和k發(fā)射相同的信息時，節(jié)點i上的發(fā)射功率：,max,),( ,kijikjippp如果節(jié)點i向節(jié)點j和k發(fā)射不同的信息時，i上的發(fā)射功率：,( , ),ij ki ji kppp35無線組播中的網(wǎng)絡(luò)編碼一個例子（傳統(tǒng)路由）：36無線組播中的網(wǎng)絡(luò)編碼一個例子（利用網(wǎng)絡(luò)編碼來節(jié)省能量）：37無線組播中的網(wǎng)絡(luò)編碼另一個例子（無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的信息互換 ）：傳統(tǒng)方法基于網(wǎng)絡(luò)編碼的方法38無線組播中的網(wǎng)絡(luò)編碼n利用無線組播特性降低能量消耗時，用到以下兩點： 廣播特性 無線通信網(wǎng)絡(luò)固有的； 節(jié)點的輸出邊上必須攜帶相同的信息

16、使用網(wǎng)絡(luò)編碼。 39無線組播中的網(wǎng)絡(luò)編碼 對于任何邊 ，這里的 是非源節(jié)點，我們假定其上傳輸相同的信號 ，表示為 ：)(veO)(vY : ()()( )( )ev h ev and t evY vY vv40無線組播中的網(wǎng)絡(luò)編碼類似的，接收節(jié)點輸出的隨機過程可表示為:, : ( )( )( , )( )i euv h eu and t evZ u iY v41無線組播中的網(wǎng)絡(luò)編碼n定理： 由 表征的無線組播網(wǎng)絡(luò)是可解的當且僅當對于所有的接收節(jié)點 相應(yīng)的系統(tǒng)轉(zhuǎn)移矩陣 的行列式在多項式環(huán) 上非零。 ),(BFAuU1()TuuMA IFB,2,mieieueF42無線組播中的網(wǎng)絡(luò)編碼基于無線組播特性的無線網(wǎng)絡(luò)編碼有以下特點：n可以實現(xiàn)以網(wǎng)絡(luò)的最大流傳輸信息，這是網(wǎng)絡(luò)中容量的理論上限；n可以降低無線網(wǎng)絡(luò)中的能量消耗，這對以電池為能源供給的無線網(wǎng)絡(luò)來說，是至關(guān)重要的；n這