“在有限有向无环、单位容量的单源多播网络中,源有 $k\ge1$ 个 $\mathbb F q$ 符号,各终点最小割至少为 $k$。随机线性网络编码让每个节点对每条输出边独立、均匀选取局部组合…”
形式陈述
给定有限、单位容量的有向无环网络,每条边每次传一个有限域
沿拓扑顺序展开后,每条边都携带
它可恢复全部源符号,当且仅当
定理针对单源多播。多个相互独立源分别要送往不同终点时,线性码并不总能达到全部可达率。
直觉
普通路由要求一个包保持原样穿过网络。编码节点可以把多个包混在一起;只要不同接收者手头已有不同的辅助信息,同一个混合包就能为他们分别补齐不同缺口。
全局编码向量记录“这个包到底是哪几个源包的什么组合”。节点不必理解源数据的语义,只需对向量与负载实施同样的线性运算。
例子与边界
蝴蝶网络的一个 XOR
源将
都在
解码条件是秩,不是包数
收到
推论与应用
实现时先为源包标注标准基向量,节点按拓扑顺序计算局部线性组合,终点用精确行化简对编码向量矩阵作消元,再将相同消元作用于负载。每一步保持不变量“负载等于编码向量作用于原始数据”。若每包有
确定性存在性证明把各终点某个
加性污染的方向预算
若在已明确的底域坐标中,传播后的加性错误可写成
要进一步调用Gabidulin插值恢复,还必须把输入化成已知独立求值点下的加性词,并验证其秩预算。这里的观察没有把本页无噪、已知传输矩阵的恢复接口自动扩大为未知网络、丢包和行列擦除的通用处理器。
参考资料
- Li、Yeung 与 Cai,“Linear Network Coding”,IEEE TIT 2003,单源多播的线性充分性。
- El Gamal 与 Kim,《Lecture Notes on Network Information Theory》完整 v4,Chapter 16,无噪网络与蝴蝶例子。