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

1、1網(wǎng)絡(luò)編碼西安電子科技大學(xué)ISN國家重點(diǎn)實(shí)驗(yàn)室2005年3月2 概 要1. 網(wǎng)絡(luò)編碼的提出及現(xiàn)狀2. 網(wǎng)絡(luò)編碼的基本原理3. 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼4. 無線組播中的網(wǎng)絡(luò)編碼5. 結(jié)束語31. 網(wǎng)絡(luò)編碼的提出在現(xiàn)有通信網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)只是對(duì)收到的信息進(jìn)行存儲(chǔ)和轉(zhuǎn)發(fā)，扮演著轉(zhuǎn)發(fā)器的角色。但是從信息理論的觀點(diǎn)來說，沒有理由讓節(jié)點(diǎn)只能進(jìn)行存儲(chǔ)轉(zhuǎn)發(fā)，可以讓節(jié)點(diǎn)對(duì)多條輸入邊上收到的信息進(jìn)行一定的線性或非線性操作（編碼），然后再發(fā)送出去，起著編碼器的作用。 網(wǎng)絡(luò)編碼正是根據(jù)這思想而產(chǎn)生的。在接收節(jié)點(diǎn)上，通過一定的運(yùn)算，譯出信源所發(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（點(diǎn)對(duì)點(diǎn)點(diǎn)對(duì)點(diǎn)的最小割最大流定理）的最小割最大流定理） 對(duì)于已知的網(wǎng)絡(luò)流圖，從發(fā)點(diǎn) 到收點(diǎn) 的流量 的最大值小于或等于任何一個(gè)割切的容量，即 記 。 min( , )urcut S uSuurmin( , )uCcut S u9uC 6網(wǎng)絡(luò)編碼的提出一個(gè)組播(multicast: point to multipoint)傳輸，信源為 ，接收節(jié)點(diǎn)集合為 ，那么可達(dá)最高組播速率為 如果采用傳統(tǒng)傳輸方法，可能無法達(dá)到速率 。如果采用網(wǎng)絡(luò)編碼，可達(dá)

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

4、碼的多項(xiàng)式時(shí)間算法（集中式）。 n2003年，Chou等提出了分布式網(wǎng)絡(luò)編碼，通過仿真得到其性能。n2003年，Ho等也提出了隨機(jī)網(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)造方式和多項(xiàng)式時(shí)間算法；112. 網(wǎng)絡(luò)編碼的基本原理n信息傳輸網(wǎng)絡(luò)可用圖 表示n信源節(jié)點(diǎn)集：n信宿節(jié)點(diǎn)集：n邊 的頭節(jié)點(diǎn)用 表示 邊 的尾節(jié)點(diǎn)用 表示( ,)G V E12 ,s sV12 ,Uu uV( )h ev( )

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

6、 比特/單位時(shí)間。把它們的輸出進(jìn)行一個(gè)定序，如下： 其中 是節(jié)點(diǎn) 的信息輸出速率。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ò)編碼，如果對(duì)于網(wǎng)絡(luò)中的每一條邊 的傳輸符號(hào)均滿足： 其中 。 ( ,)G V E,: ()( ),: ()( )( ) ( )( , )( ) e ee h et ei ee ee h et eevev ie如果節(jié)點(diǎn) 不是一個(gè)信源節(jié)點(diǎn)否則,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é)點(diǎn)否則, ( )()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é)點(diǎn) 接收向量: 其中, 是接收節(jié)點(diǎn) 的系統(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ò)編碼的糾錯(cuò)碼 基于網(wǎng)絡(luò)編碼的差錯(cuò)控制是針對(duì)網(wǎng)絡(luò)、而非一條鏈路或一條路徑進(jìn)行操作的。通過合適的選擇信源空間，可以糾正傳輸網(wǎng)絡(luò)中幾條鏈路上發(fā)生的傳輸錯(cuò)誤，這是一個(gè)比較新的差錯(cuò)控制方式，稱之為基于網(wǎng)絡(luò)編碼的差錯(cuò)控制 。19基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼n參與多播傳輸?shù)逆溌窋?shù)用 表示。n組播網(wǎng)絡(luò)的網(wǎng)絡(luò)容量 為 比特/單位時(shí)間。 KnC20基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼n如果從某條鏈路上輸出的符號(hào)不等于輸入的符號(hào)，那么稱發(fā)生錯(cuò)誤。n如果在傳輸網(wǎng)絡(luò)中總共有 條鏈路發(fā)生錯(cuò)誤，就稱為網(wǎng)絡(luò)發(fā)生了 個(gè)錯(cuò)誤。n如果一個(gè)基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼能糾正所有錯(cuò)誤個(gè)數(shù)小于等于 的情況，就稱該

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

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

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

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

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

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

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

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