網絡編碼

網絡編碼是一種通過中繼節點對接收到的信息進行編碼來達到提高多播網絡容量的技術。Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung在2000年首次提出網絡編碼的概念。

s試圖向$t_{1},t_{2}$組播兩條消息x,y。線路cd上會需要同時傳輸x,y，一般的傳輸方案行不通。

在右圖的網絡拓撲中，s節點試圖向$t_{1},t_{2}$組播兩條消息x,y。設每條消息占用的帶寬為1，每個節點之間的網絡帶寬也為1，那麼每個節點之間只能同時傳輸一條消息。線路cd上會需要同時傳輸x,y，這在一般的傳輸方案中是行不通的，所以需要網絡編碼在c處將x,y異或，合成一條消息然後發送。

• 在傳統的數據傳輸技術中，中繼節點只負責數據的存儲轉發，而基於網絡編碼技術的網絡的中繼節點在具備傳統中繼功能的基礎上，會根據網絡編碼規則將接收到的信息進行線性或非線性處理再進行傳播，這種做法最直觀的優勢是減少了傳輸次數。利用圖論中最大流最小割原理論證了網絡編碼可以達到網絡最大信息流。
• 網絡編碼的相關領域：資訊理論、圖論、編碼理論

線性網絡編碼

假設網絡是有向的，執行線性網絡編碼時每個節點收到所有連入線路的數據後，再執行編碼，然後把數據從連出線路發出。新的數據包括執行線性編碼所用的係數以及合成後的數據。

例如組播源發送三條封包，$p_{1}=1$，$p_{2}=2$，$p_{3}=3$。封包經過一系列的中間節點，目標節點收到的封包是$((5,8,1),24),((2,3,7),29),((9,6,5),36)$。目標節點對下列矩陣求解，可得$p_{1},p_{2},p_{3}$的值。

${\begin{bmatrix}24\\29\\36\end{bmatrix}}={\begin{bmatrix}5&8&1\\2&3&7\\9&6&5\end{bmatrix}}{\begin{bmatrix}p_{1}\\p_{2}\\p_{3}\end{bmatrix}}\Rightarrow {\begin{cases}24=5p_{1}+8p_{2}+p_{3}&\\29=2p_{1}+3p_{2}+7p_{3}&\\36=9p_{1}+6p_{2}+5p_{3}&\end{cases}}$或${\begin{bmatrix}p_{1}\\p_{2}\\p_{3}\end{bmatrix}}={\begin{bmatrix}5&8&1\\2&3&7\\9&6&5\end{bmatrix}}^{-1}{\begin{bmatrix}24\\29\\36\end{bmatrix}}$

隨機線性網絡編碼

隨機線性網絡編碼可以取得更好的組播傳輸速率，較為實用。在實際網絡中，節點會將來自連入線路的封包緩存起來，當節點需要發送封包時再將緩存的封包執行網絡編碼，然後發出。

例如節點A有2個上游節點X,Y，X向A發送了封包$((2,2,1),2x_{1}+2x_{2}+x_{3})$($2x_{1}+2x_{2}+x_{3}$是數據體，（2,2,1）是對數據體執行線性編碼時所用的係數）,Y向A發送了封包$((1,5,4),x_{1}+5x_{2}+4x_{3})$。當A需要發送數據時，便把緩存的這兩個封包取出來，隨機選擇2個係數（如2和1），獲得新的數據體$(2x_{1}+2x_{2}+x_{3})\times 2+(x_{1}+5x_{2}+4x_{3})\times 1=5x_{1}+9x_{2}+6x_{3}$和新的合成係數$(2,2,1)\times 2+(1,5,4)\times 1=(5,9,6)$。所以A就把合成後的數據體$5x_{1}+9x_{2}+6x_{3}$連同合成係數(5,9,6)，向下游節點發送出去。