隨機(jī)線性網(wǎng)絡(luò)編碼PPT課件

1、簡要介紹簡要介紹對(duì)于除了信宿節(jié)點(diǎn)外的所有中間節(jié)點(diǎn)，只要在一個(gè)足夠大的有限對(duì)于除了信宿節(jié)點(diǎn)外的所有中間節(jié)點(diǎn)，只要在一個(gè)足夠大的有限域上隨機(jī)選擇它們輸入鏈路到輸出鏈路的映射，且各節(jié)點(diǎn)映射關(guān)域上隨機(jī)選擇它們輸入鏈路到輸出鏈路的映射，且各節(jié)點(diǎn)映射關(guān)系的選取是相互獨(dú)立的，從而保證各信宿能以較高概率成功譯碼系的選取是相互獨(dú)立的，從而保證各信宿能以較高概率成功譯碼各鏈路上的系數(shù)向量和信源發(fā)各鏈路上的系數(shù)向量和信源發(fā)送的信息進(jìn)行同步傳輸，信息送的信息進(jìn)行同步傳輸，信息在通過編碼節(jié)點(diǎn)時(shí)，系數(shù)向量在通過編碼節(jié)點(diǎn)時(shí)，系數(shù)向量根據(jù)隨機(jī)選取的映射關(guān)系進(jìn)行根據(jù)隨機(jī)選取的映射關(guān)系進(jìn)行更新，最終信宿節(jié)點(diǎn)收到的輸更新，最終信宿

2、節(jié)點(diǎn)收到的輸入信息將包含輸入鏈路對(duì)應(yīng)的入信息將包含輸入鏈路對(duì)應(yīng)的全局編碼向量和信源發(fā)送的信全局編碼向量和信源發(fā)送的信息流，然后采用高斯消元法息流，然后采用高斯消元法（解線性方程組）正確譯碼獲（解線性方程組）正確譯碼獲得信源原始傳輸?shù)男畔⒌眯旁丛紓鬏數(shù)男畔⒌?頁/共22頁簡要介紹簡要介紹我們考慮的問題我們考慮的問題怎樣構(gòu)建隨機(jī)線性網(wǎng)絡(luò)編碼怎樣構(gòu)建隨機(jī)線性網(wǎng)絡(luò)編碼怎樣在分布網(wǎng)絡(luò)中有效的將信息傳輸?shù)浇邮展?jié)點(diǎn)怎樣在分布網(wǎng)絡(luò)中有效的將信息傳輸?shù)浇邮展?jié)點(diǎn)第2頁/共22頁編碼模型編碼模型做出的假設(shè)做出的假設(shè)每條鏈路的容量是一比特每單元，如果某條邊的容量大于一比特每條鏈路的容量是一比特每單元，如果某條邊的容

3、量大于一比特每單位時(shí)間，則看做是幾條并行的邊。如果邊的容量不是整數(shù)，則每單位時(shí)間，則看做是幾條并行的邊。如果邊的容量不是整數(shù)，則將時(shí)間單元取得大一點(diǎn)，使得小數(shù)部分可以近似成整數(shù)。將時(shí)間單元取得大一點(diǎn)，使得小數(shù)部分可以近似成整數(shù)。假設(shè)每條鏈路的延遲是一樣的。假設(shè)每條鏈路的延遲是一樣的。對(duì)于線性相關(guān)源，我們認(rèn)為每一個(gè)獨(dú)立信源的熵率是一比特每單對(duì)于線性相關(guān)源，我們認(rèn)為每一個(gè)獨(dú)立信源的熵率是一比特每單位時(shí)間，如果不是，則將它們變成一些并行的熵率是一比特每單位位時(shí)間，如果不是，則將它們變成一些并行的熵率是一比特每單位時(shí)間的源的集合。時(shí)間的源的集合。對(duì)于任意相關(guān)源，我們要求信源的熵是整數(shù)，并且有著任意的聯(lián)

4、對(duì)于任意相關(guān)源，我們要求信源的熵是整數(shù)，并且有著任意的聯(lián)合概率分布合概率分布對(duì)于不同的節(jié)點(diǎn)，它們要處理的隨機(jī)過程之間是相互獨(dú)立的，這對(duì)于不同的節(jié)點(diǎn)，它們要處理的隨機(jī)過程之間是相互獨(dú)立的，這個(gè)假設(shè)符合通信網(wǎng)絡(luò)一般的情況個(gè)假設(shè)符合通信網(wǎng)絡(luò)一般的情況第3頁/共22頁 Add your title in here編碼模型編碼模型多信源的多信源的Slepian WolfSlepian Wolf定理：定理：有有r r個(gè)離散的無記憶信息源個(gè)離散的無記憶信息源 , ,它們是隨機(jī)二進(jìn)制序列，它們是隨機(jī)二進(jìn)制序列，對(duì)每個(gè)信源獨(dú)立進(jìn)行編碼，再進(jìn)行聯(lián)合譯碼，其性能跟所有信源對(duì)每個(gè)信源獨(dú)立進(jìn)行編碼，再進(jìn)行聯(lián)合譯碼，其性

5、能跟所有信源聯(lián)合編碼是一致的。只要滿足在聯(lián)合編碼是一致的。只要滿足在r r個(gè)信源中任取個(gè)信源中任取k k個(gè)信源的和速率，個(gè)信源的和速率，不能小于這不能小于這k k個(gè)信源以剩余的個(gè)信源以剩余的r-kr-k個(gè)信源為條件的熵，而對(duì)于總的個(gè)信源為條件的熵，而對(duì)于總的和速率不能小于這和速率不能小于這r r個(gè)信源的聯(lián)合熵。個(gè)信源的聯(lián)合熵。 rXXX,21第4頁/共22頁 Add your title in here編碼模型編碼模型不考慮不考慮延遲延遲考慮考慮延遲延遲考慮邊容量為考慮邊容量為1 1的情況，的情況，每個(gè)節(jié)點(diǎn)在等到所有每個(gè)節(jié)點(diǎn)在等到所有進(jìn)入此節(jié)點(diǎn)的信息后進(jìn)入此節(jié)點(diǎn)的信息后才發(fā)往離開此節(jié)點(diǎn)的才發(fā)往

6、離開此節(jié)點(diǎn)的出邊出邊有著有著v v個(gè)節(jié)點(diǎn)和信息傳輸速率是個(gè)節(jié)點(diǎn)和信息傳輸速率是r r的的循環(huán)網(wǎng)絡(luò)可以變成非循環(huán)網(wǎng)絡(luò)，此循環(huán)網(wǎng)絡(luò)可以變成非循環(huán)網(wǎng)絡(luò)，此網(wǎng)絡(luò)有網(wǎng)絡(luò)有kvkv個(gè)節(jié)點(diǎn)，信息傳輸速率大個(gè)節(jié)點(diǎn)，信息傳輸速率大于等于（于等于（k-vk-v）r,r,信息在這種網(wǎng)絡(luò)信息在這種網(wǎng)絡(luò)上的傳輸可以被模仿成原來循環(huán)網(wǎng)上的傳輸可以被模仿成原來循環(huán)網(wǎng)絡(luò)絡(luò)k k個(gè)時(shí)隙的步驟。這種情況我們個(gè)時(shí)隙的步驟。這種情況我們假設(shè)每個(gè)鏈路的延遲是一樣的。假設(shè)每個(gè)鏈路的延遲是一樣的。第5頁/共22頁 Add your title in here編碼模型編碼模型符號(hào)簡介（符號(hào)簡介（1）非循環(huán)圖非循環(huán)圖G=G=（V,EV,E）表

7、示的）表示的網(wǎng)絡(luò)中，每條邊可以根據(jù)網(wǎng)絡(luò)中，每條邊可以根據(jù)網(wǎng)絡(luò)拓?fù)溥M(jìn)行順序編號(hào)網(wǎng)絡(luò)拓?fù)溥M(jìn)行順序編號(hào): :如如 ，對(duì)于每條從，對(duì)于每條從屬于屬于E E的邊，它的源表示為的邊，它的源表示為o( ),o( ),它的目的節(jié)點(diǎn)表示它的目的節(jié)點(diǎn)表示為為d( )d( )。一個(gè)路徑就是一。一個(gè)路徑就是一系列的鏈路集系列的鏈路集合合 ，對(duì)任意的，對(duì)任意的i j, i j, 。Eeee,21ieie)()(1iieoed)(ied)(jed節(jié)點(diǎn)節(jié)點(diǎn)V V 即即d( )d( ) 既稱為既稱為headhead（ ）又稱為又稱為tail( )tail( )邊邊ie1ie邊邊ie1ieO( )O( )ieie進(jìn)入一個(gè)節(jié)點(diǎn)的

8、邊數(shù)稱為一個(gè)節(jié)進(jìn)入一個(gè)節(jié)點(diǎn)的邊數(shù)稱為一個(gè)節(jié)點(diǎn)的入度，由一個(gè)節(jié)點(diǎn)發(fā)出的邊點(diǎn)的入度，由一個(gè)節(jié)點(diǎn)發(fā)出的邊數(shù)稱為節(jié)點(diǎn)的出度，節(jié)點(diǎn)的入度數(shù)稱為節(jié)點(diǎn)的出度，節(jié)點(diǎn)的入度和出度的和稱為節(jié)點(diǎn)的度數(shù)和出度的和稱為節(jié)點(diǎn)的度數(shù)第6頁/共22頁 Add your title in here編碼模型編碼模型 符號(hào)簡介（符號(hào)簡介（2）)(vI定義定義 為所有以節(jié)點(diǎn)為所有以節(jié)點(diǎn)V V為結(jié)束點(diǎn)的邊為結(jié)束點(diǎn)的邊的集合的集合veheadEevI)(:)(定義定義 為所有從節(jié)點(diǎn)為所有從節(jié)點(diǎn)V V開始的邊的集合開始的邊的集合)(0vvetailEev)(:)(0)(vI)(0v接收機(jī)接收機(jī)處的終端鏈路的集合稱為處的終端鏈路的集合稱為

9、)(,(,),2 ,(),1 ,()(vuvXvXvXv 是在節(jié)點(diǎn)是在節(jié)點(diǎn)v v收集到的收集到的u(v)u(v)個(gè)離散隨機(jī)過程個(gè)離散隨機(jī)過程在邊在邊e e上傳輸?shù)碾S機(jī)過程稱為上傳輸?shù)碾S機(jī)過程稱為Y(e)Y(e)第7頁/共22頁 Add your title in here編碼模型編碼模型如圖是一個(gè)非延遲網(wǎng)絡(luò)，對(duì)于鏈路如圖是一個(gè)非延遲網(wǎng)絡(luò)，對(duì)于鏈路e e上的隨機(jī)處理過程滿足上的隨機(jī)處理過程滿足對(duì)于匯節(jié)點(diǎn)的輸出對(duì)于匯節(jié)點(diǎn)的輸出Z Z是由屬于是由屬于 的所有邊上的隨機(jī)過程的所有邊上的隨機(jī)過程Y(e)Y(e)形成形成的的)(uI這里的這里的，都都是從伽羅華域中隨機(jī)是從伽羅華域中隨機(jī)選擇的選擇的如果如果

10、，是獨(dú)是獨(dú)立的，則系統(tǒng)是時(shí)不立的，則系統(tǒng)是時(shí)不變的，否則系統(tǒng)是時(shí)變的，否則系統(tǒng)是時(shí)變的變的第8頁/共22頁 Add your title in here編碼模型編碼模型)(,(,),2 ,(),1 ,(vuvXvXvXx 表示在源節(jié)表示在源節(jié)點(diǎn)觀察到的輸入信號(hào)矢量點(diǎn)觀察到的輸入信號(hào)矢量另另vv點(diǎn)是一個(gè)網(wǎng)絡(luò)的匯結(jié)點(diǎn)，我點(diǎn)是一個(gè)網(wǎng)絡(luò)的匯結(jié)點(diǎn)，我們認(rèn)為們認(rèn)為 是是這個(gè)節(jié)點(diǎn)的輸出過程矢量這個(gè)節(jié)點(diǎn)的輸出過程矢量)(, (,),2 , (),1 , (vvZvZvZz另另M M表示一個(gè)網(wǎng)絡(luò)的傳輸矩陣，這表示一個(gè)網(wǎng)絡(luò)的傳輸矩陣，這樣樣z z= =x x* *M,M,對(duì)于固定的系數(shù)對(duì)于固定的系數(shù)，我們不難看出

11、，我們不難看出，M M矩陣?yán)锏臄?shù)矩陣?yán)锏臄?shù)也是從伽羅華域中選取的。也是從伽羅華域中選取的。第9頁/共22頁 Add your title in here編碼模型編碼模型GF(GF( ) )域域以以m=4m=4為例，它的本原多項(xiàng)式為為例，它的本原多項(xiàng)式為 , ,即即 在伽羅華域中，加法等于對(duì)應(yīng)位異或在伽羅華域中，加法等于對(duì)應(yīng)位異或先給出推導(dǎo)過程先給出推導(dǎo)過程0 0000 10000 0000 10001 0001 0011 10011 0001 0011 1001 0010 0110 0001 0010 0110 0001 0100 0100 可以看出，當(dāng)可以看出，當(dāng)m=4m=4時(shí)，時(shí)，GF(4

12、)GF(4)是一個(gè)包含是一個(gè)包含1515個(gè)數(shù)的有限域，個(gè)數(shù)的有限域，且這且這1515個(gè)數(shù)循環(huán)產(chǎn)生。個(gè)數(shù)循環(huán)產(chǎn)生。在伽羅華域中，每對(duì)應(yīng)一個(gè)在伽羅華域中，每對(duì)應(yīng)一個(gè)m m，會(huì)有一個(gè)相應(yīng)的本原多項(xiàng)，會(huì)有一個(gè)相應(yīng)的本原多項(xiàng)式，根據(jù)這個(gè)本原多項(xiàng)式，就可以推出域里面的值。式，根據(jù)這個(gè)本原多項(xiàng)式，就可以推出域里面的值。 m20141423451415第10頁/共22頁 Add your title in here編碼模型編碼模型傳輸矩陣可以表示為傳輸矩陣可以表示為第11頁/共22頁 Add your title in here編碼模型編碼模型矩陣矩陣 A A為源節(jié)點(diǎn)輸入信息與邊之間的關(guān)為源節(jié)點(diǎn)輸入信息與邊之

13、間的關(guān)系矩陣，矩陣系矩陣，矩陣B B為接收節(jié)點(diǎn)對(duì)接收到的數(shù)為接收節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)進(jìn)行線性組合。單源單匯的節(jié)點(diǎn)的信據(jù)進(jìn)行線性組合。單源單匯的節(jié)點(diǎn)的信息傳輸時(shí)，只要相應(yīng)的轉(zhuǎn)移矩陣是滿秩息傳輸時(shí)，只要相應(yīng)的轉(zhuǎn)移矩陣是滿秩的，則源節(jié)點(diǎn)輸出的信息在接收端就可的，則源節(jié)點(diǎn)輸出的信息在接收端就可以準(zhǔn)確的恢復(fù)。單源多匯的節(jié)點(diǎn)的信息以準(zhǔn)確的恢復(fù)。單源多匯的節(jié)點(diǎn)的信息多播傳輸，利用網(wǎng)絡(luò)編碼時(shí)，只要能保多播傳輸，利用網(wǎng)絡(luò)編碼時(shí)，只要能保證各個(gè)目的節(jié)點(diǎn)對(duì)應(yīng)的網(wǎng)絡(luò)轉(zhuǎn)移矩陣是證各個(gè)目的節(jié)點(diǎn)對(duì)應(yīng)的網(wǎng)絡(luò)轉(zhuǎn)移矩陣是滿秩的，則目的節(jié)點(diǎn)就可以準(zhǔn)確的恢復(fù)滿秩的，則目的節(jié)點(diǎn)就可以準(zhǔn)確的恢復(fù)出原始發(fā)送的信息。出原始發(fā)送的信息。傳輸矩陣

14、可以表示為傳輸矩陣可以表示為第12頁/共22頁編碼模型編碼模型對(duì)有向網(wǎng)絡(luò)來說，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序，定義相應(yīng)的鄰接矩對(duì)有向網(wǎng)絡(luò)來說，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序，定義相應(yīng)的鄰接矩陣陣F F，F(xiàn) F矩陣的第矩陣的第i i行第行第 j j 列元素表示網(wǎng)絡(luò)流圖中第列元素表示網(wǎng)絡(luò)流圖中第i i條邊與第條邊與第 j j 條邊的連接關(guān)系，條邊的連接關(guān)系，F(xiàn) F可表示為可表示為其中其中 表示有向邊表示有向邊 的終點(diǎn)與有向邊的終點(diǎn)與有向邊 的起點(diǎn)重的起點(diǎn)重合，合， 是有限域中的一非是有限域中的一非 0 0 元素，則元素，則M M可表示為：可表示為：這種編碼的構(gòu)造簡單而且有效，但是計(jì)算量大。這種編碼的構(gòu)造簡單而且有效，但是

15、計(jì)算量大。其它,0)()(,jieejietaileheadFji)()(jietaileheadiejejiee ,TBFIAM1)(第13頁/共22頁編碼模型編碼模型圖中節(jié)點(diǎn)圖中節(jié)點(diǎn) v v ，接收到編碼包，接收到編碼包 和和 。節(jié)點(diǎn)。節(jié)點(diǎn) v v 應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼的思想，在有限域中隨機(jī)選取系數(shù)應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼的思想，在有限域中隨機(jī)選取系數(shù)(1,2)(1,2)，并對(duì)接收到的兩個(gè)編碼包進(jìn)行運(yùn)算并對(duì)接收到的兩個(gè)編碼包進(jìn)行運(yùn)算 ，得到新的編碼系數(shù)得到新的編碼系數(shù)(3,10,13)(3,10,13)，并將新的編碼包發(fā)送。，并將新的編碼包發(fā)送。32132xxx32154xxx)54( 2)32( 1

16、321321xxxxxx第14頁/共22頁編碼模型編碼模型隨機(jī)網(wǎng)絡(luò)編碼中中間節(jié)點(diǎn)只需要對(duì)接收到的數(shù)據(jù)進(jìn)行線性組合，隨機(jī)網(wǎng)絡(luò)編碼中中間節(jié)點(diǎn)只需要對(duì)接收到的數(shù)據(jù)進(jìn)行線性組合，而不需要判斷接收到的信息是否線性相關(guān)。這樣在接收節(jié)點(diǎn)處而不需要判斷接收到的信息是否線性相關(guān)。這樣在接收節(jié)點(diǎn)處有可能出現(xiàn)線性相關(guān)的編碼信息導(dǎo)致解碼失敗。對(duì)于任意一個(gè)有可能出現(xiàn)線性相關(guān)的編碼信息導(dǎo)致解碼失敗。對(duì)于任意一個(gè)可行的多播網(wǎng)絡(luò)，如果網(wǎng)絡(luò)編碼部分或所有的編碼系數(shù)都是獨(dú)可行的多播網(wǎng)絡(luò)，如果網(wǎng)絡(luò)編碼部分或所有的編碼系數(shù)都是獨(dú)立的均勻的在一個(gè)有限域立的均勻的在一個(gè)有限域 上選取，則所有的目的節(jié)點(diǎn)能夠成上選取，則所有的目的節(jié)點(diǎn)能夠成

17、功進(jìn)行解碼的概率至少為功進(jìn)行解碼的概率至少為 ，q dq d ，其中，其中 d d 表示目表示目的節(jié)點(diǎn)的數(shù)目，的節(jié)點(diǎn)的數(shù)目， 為隨機(jī)選取編碼系數(shù)的鏈路數(shù)目，為隨機(jī)選取編碼系數(shù)的鏈路數(shù)目，q q為編碼為編碼符號(hào)域的大小。當(dāng)有限域的字母表大小符號(hào)域的大小。當(dāng)有限域的字母表大小 q q 遠(yuǎn)大于接收節(jié)點(diǎn)數(shù)目遠(yuǎn)大于接收節(jié)點(diǎn)數(shù)目 d d 時(shí)，所有的接收節(jié)點(diǎn)可以以很高的概率恢復(fù)出原始信息。采時(shí)，所有的接收節(jié)點(diǎn)可以以很高的概率恢復(fù)出原始信息。采用隨機(jī)線性網(wǎng)絡(luò)編碼的多播網(wǎng)絡(luò)中，多個(gè)源節(jié)點(diǎn)可以相互獨(dú)立，用隨機(jī)線性網(wǎng)絡(luò)編碼的多播網(wǎng)絡(luò)中，多個(gè)源節(jié)點(diǎn)可以相互獨(dú)立，也可以線性相關(guān)。對(duì)于線性相關(guān)的源，隨機(jī)線性編碼起到了信也

18、可以線性相關(guān)。對(duì)于線性相關(guān)的源，隨機(jī)線性編碼起到了信息壓縮的作用。息壓縮的作用。qF)/1(qd第15頁/共22頁方案舉例方案舉例網(wǎng)絡(luò)的目的是每個(gè)節(jié)點(diǎn)都能收到信源發(fā)出的兩個(gè)隨機(jī)過程隨機(jī)流結(jié)構(gòu)隨機(jī)流結(jié)構(gòu)(RF)(RF)源節(jié)點(diǎn)延兩個(gè)軸向分別發(fā)送兩源節(jié)點(diǎn)延兩個(gè)軸向分別發(fā)送兩 個(gè)信息個(gè)信息只接收到一個(gè)信息過程的節(jié)點(diǎn)只接收到一個(gè)信息過程的節(jié)點(diǎn)向其它三個(gè)方向發(fā)送信息向其它三個(gè)方向發(fā)送信息接收到兩個(gè)信息過程的節(jié)點(diǎn)分接收到兩個(gè)信息過程的節(jié)點(diǎn)分別向?qū)?yīng)的軸向發(fā)送相應(yīng)的信息別向?qū)?yīng)的軸向發(fā)送相應(yīng)的信息第16頁/共22頁方案舉例方案舉例隨機(jī)編碼結(jié)構(gòu)隨機(jī)編碼結(jié)構(gòu)(RC)(RC)源節(jié)點(diǎn)延兩個(gè)軸向分別發(fā)送兩源節(jié)點(diǎn)延兩個(gè)軸向分別發(fā)送兩 個(gè)信息個(gè)信息只接收到一個(gè)信息過程的節(jié)點(diǎn)向其它三個(gè)只接收到一個(gè)信息過程的節(jié)點(diǎn)向其它三個(gè)方向發(fā)送信息方向發(fā)送信息接收到兩個(gè)信息過程的節(jié)點(diǎn)向其余的軸向接收到兩個(gè)信息過程的節(jié)點(diǎn)向其余的軸向發(fā)送接收到的信息的線性組合發(fā)送接收到的信息的線性組合對(duì)于接收位置為（對(duì)于接收位置為（x,yx,y）的點(diǎn)，接收）的點(diǎn)，接收機(jī)能接收到兩個(gè)發(fā)送信息的概率為機(jī)能接收到兩個(gè)發(fā)送信息的概率為RFRFRC RC （q q是伽羅華域字母表）是伽羅華域字母表）)2(2)/11(yxq第17頁/共22頁方案舉例方案舉例RFRF方案和方案和RCRC方案