在計算機網絡中，線性網絡編碼是中間節點通過線性組合的方式將數據從源節點傳輸到匯節點的程序。

網絡編碼可用于提高網絡的吞吐量、效率和可擴展性，以及減少攻擊和竊聽。 網絡的節點接收多個數據包并組合起來進行傳輸。 該過程可用于在網絡中獲得xxx可能的信息流。

已經證明，從理論上講，線性編碼足以實現單源多播問題的上界。 然而，線性編碼通常是不夠的； 即使對于更一般的線性版本，例如卷積編碼和濾波器組編碼。 為具有任意需求的一般網絡問題尋找最佳編碼解決方案仍然是一個懸而未決的問題。

在線性網絡編碼問題中，一組節點 P {\displaystyle P} 參與將數據從 S {\displaystyle S} 源節點移動到 K {\displaystyle K} 匯節點。 每個節點生成新數據包，這些新數據包是過去接收到的數據包的線性組合，方法是將它們乘以從有限域中選擇的系數，通常大小為 G F ( 2 s ) {\displaystyle GF(2{s})} 。

由于操作是在有限域中計算的，因此生成的消息與原始消息的長度相同。

匯聚節點接收這些網絡編碼消息，并將它們收集在一個矩陣中。 可以通過對矩陣進行高斯消元來恢復原始消息。

網絡由有向圖 G = ( V , E , C ) {\displaystyle {\mathcal {G}}=(V,E,C)} 表示。 V {\displaystyle V} 是節點或頂點的集合，E {\displaystyle E} 是有向鏈接（或邊）的集合，而 C {\displaystyle C} 給出了 E { \displaystyle E} 。 設 T ( s , t ) {\displaystyle T(s,t)} 是從節點 s {\displaystyle s} 到節點 t {\displaystyle t} 的xxx可能吞吐量。 根據xxx流最小割定理，T ( s , t ) {\displaystyle T(s,t)} 的上界是所有割的最小容量，即邊的容量之和 切，在這兩個節點之間。

Karl Menger 證明了在單播場景中總有一組邊不相交的路徑達到上限，稱為xxx流最小割定理。 后來，Ford-Fulkerson 算法被提出來在多項式時間內找到這樣的路徑。

但是，組播場景下的情況比較復雜，實際上，使用傳統的路由思想是達不到這樣一個上限的。 阿爾斯韋德等人。 證明如果可以在中間節點完成額外的計算任務（傳入數據包組合成一個或多個傳出數據包），則可以實現。

蝴蝶網絡經常被用來說明線性網絡編碼如何優于路由。 兩個源節點（在圖片的頂部）具有必須傳輸到兩個目標節點（在底部）的信息 A 和 B。 每個目標節點都想知道 A 和 B。每條邊只能攜帶一個值（我們可以認為邊在每個時隙中傳輸一個位）。

如果只允許路由，則中央鏈路將只能承載 A 或 B，而不能同時承載兩者。 假設我們發送 A 通過中心； 那么左邊的目的地將收到 A 兩次而根本不知道 B。 發送 B 對正確的目的地提出了類似的問題。 我們說路由是不充分的，因為沒有路由方案可以同時將 A 和 B 傳送到兩個目的地。 同時，兩個目的節點知道 A 和 B 總共需要 4 個時隙。

使用一個簡單的代碼，如圖所示，A 和 B 可以通過兩個中繼節點發送符號之和同時傳輸到兩個目的地——使用公式 A+B 對 A 和 B 進行編碼。