線性多播/線性廣播/線性擴散/一般線性網絡碼

原文：出處
線性多播（Linear Multicast，LM）、線性廣播（Linear Broadcast，LB）、線性擴散（Linear Dispersion，LD）、一般線性網絡碼（Generic Linear Network Code，GLNC）是網絡編碼理論中基礎且容易混淆的概念。

在給出這四個概念的定義前先了解幾個定義：

• < # > 表示的是向量集合# 生成的向量空間

對于節點T，VT = <{fd : d ∈ In(T)}> 表示節點T 所有輸入鏈路的全局編碼向量集合{fd: d ∈ In(T)} 所生成的向量空間

對于節點集合$?$ ，KaTeX parse error: Undefined control sequence: \CUP at position 12: V_{\wp} = <\?C?U?P?_{T \in \wp}V_T… 表示節點集合$?$ 中節點所有輸入鏈路的全局向量集合所生成的向量空間

對于鏈路集合ξ ，Vξ = < fe : e ∈ ξ > 表示鏈路集合ξ 的全局編碼向量集合所生成的向量空間

• maxflow(T) 表示信源節點S 到非信源節點T 的最大流
• maxflow{$?$ } 記做信源節點S 到非信源節點集合$?$ 的最大流
• maxflow{ξ} 記做信源節點S 到任意鏈路集合ξ 的最大流
• dim( & ) 表示向量空間的維度，如dim(VT) = 2 表示節點T 所有輸入鏈路的全局編碼向量集合所生成的向量空間的維度為2

---

有了上面的基礎定義，我們看看線性多播/線性廣播/線性擴散/一般線性網絡碼 的一般定義：
線性多播
在有向無環網絡中，記列向量fd 為有限域F 上ω 維線性網絡編碼的全局編碼向量，對于任何非信源節點T ，均存在由其所有輸入鏈路d 的全局編碼向量fd 的集合所生成的向量空間，記做VT = <{fd : d ∈ In(T)}> 。若對于每個滿足maxflow(T) ≥ ω 的非信源節點T ，均有

dim(VT) = ω

此時的線性網絡編碼稱為線性多播。

線性廣播
在有向無環網絡中，記列向量fd 為有限域F 上ω 維線性網絡編碼的全局編碼向量，對于任何非信源節點T ，均存在由其所有輸入鏈路d 的全局編碼向量fd 的集合所生成的向量空間，記做VT = <{fd : d ∈ In(T)}> 。若對于每個的非信源節點T ，均有

dim($V_T$) = min{ω, maxflow(T)}

此時的線性網絡編碼稱為線性廣播。

線性擴散
在有向無環網絡中，記列向量fd 為有限域F 上ω 維線性網絡編碼的全局編碼向量，對于任何非信源節點T ，均存在由其所有輸入鏈路d 的全局編碼向量fd 的集合所生成的向量空間，記做VT = <{fd : d ∈ In(T)}> ，并記由非信源節點集合$?$ 的全局編碼向量集合構成的向量空間為VT = <{fd : d ∈ In(T)}>，若對于每個的非信源節點集合$?$ ，均有

dim($V_{?}$) = min{ω, maxflow($?$)}

此時的線性網絡編碼稱為線性擴散。

一般線性網絡碼
有向無環網絡中，記向量fd 和fe 為有限域F 上ω 維線性網絡編碼的全局編碼向量，對于任意非空鏈路集合ξ = {e1 , e2 , … , em} ? E，其中?ei = Out(Ti)，1 ≤ i ≤ m，m ≤ ω ，若<fd : d ∈ In(Ti)> 不屬于 <fe : e ∈ ξ{ei} >,
記做$V_{T_i}$ $?$ $V_{|e_i}$ ，則$f_{e_1}$ , $f_{e_2}$, $?$ ,$f_{e_m}$（記做fe ，e ∈ ξ）線性無關，則此時線性網絡編碼為一般線性網絡編碼。

上面談到的四個性質具有逐漸增強的關系，線性多播包含線性廣播，包含線性擴散，包括一般線性網絡編碼，但反之不一定成立。

一般線性網絡編碼要求任何鏈路的集合內所有向量盡量滿足線性無關性（min{ω, maxflow(ξ)} ）；當對任意鏈路放松要求，指定為任意節點的流入鏈路集合滿足線性無關，則成為線性擴散；再對任意節點退化為單個非信源節點T ，則為線性廣播；最后將單個節點約束為maxflow(T) ≥ ω 的非信源節點T收到所有信息（ω 個線性無關的）的要求，就是線性多播。

將上面這段話再分來來說：

**線性多播：**對于最大流大于或等于ω 的所有非信源節點，均可以收到信源節點發出的ω 個線性無關的消息。

線性廣播：①. 對于最大流大于或等于ω 的所有非信源節點，均可以收到信源節點發出的ω 個線性無關的消息。②. 所有最大流小于ω 的非信源節點，均可以同時收到信源節點發出的部分消息，其信息總量等于該節點的最大流。收到ω 信息量表示收到了整個信息，線性廣播表示一個非信源節點要么收到整個信息，要么收到最大流信息（每個進入鏈路向量都不相關）。

**線性擴散：**單個非信源節點和多個信源節點集合均滿足廣播性質。線性擴散表示一個非信源節點的集合要么收到了整個信息（ω），否則所有流入到這個集合的鏈路向量不相關。

下面通過幾個例子來說明線性網絡編碼、線性多播、線性廣播、線性擴散和一般線性網絡編碼之間的包含關系：

**(d) 線性網絡碼不是線性多播碼：**非源節點W 不滿足線性多播性質。maxflow(W) > ω = 2 ，而dim(VW) = 1 ≠ ω

**? 線性多播碼不是線性廣播碼：**節點都滿足最大流大于2（只有節點W 滿足）的dim(VW) = 2，是線性多播碼。而非源節點U 的 dim(VU) = 0 ≠ min{ ω = 2, maxflow(U) = 1 } 的性質，所以不是線性多播碼

**(b) 線性廣播碼不是線性擴散碼：**非源節點E 都滿足 dim(VE) = min{ ω , maxflow(E) } 的性質，是線性廣播碼。但是節點集合{T,U} 最大流maxflow({T,U}) = 2，ω = 2 ，而fST 和fSU 兩個列向量線性相關，所以dim(V{T,U}) = 1，不是線性擴散碼。

**(a) 線性擴散碼不是一般線性網絡碼：**當fSW 為紅色列向量，任意個非源節點（T，U，W）集合的流入鏈接向量都滿足最大線性不相關性質，所以是線性擴散碼。但是鏈路fSU 和fSW 鏈路向量相關（而maxflow(fSU 、fSW ) = 2，ω = 2），不滿足一般線性網絡碼的性質。

(a) 線性擴散碼也是一般線性網絡碼：當fSW 為黑色列向量。
最后總結一下：

對于線性多播：只看是否存在一個點，即滿足條件的點

對于線性廣播：是任意的點

對于線性擴散：是看集合

對于一般線性網絡碼，是看集合是否獨立

總結

以上是生活随笔為你收集整理的线性多播/线性广播/线性扩散/一般线性网络码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。