线性网络编码

普通路由要求一个包保持原样穿过网络。编码节点可以把多个包混在一起；只要不同接收者手头已有不同的辅助信息，同一个混合包就能为他们分别补齐不同缺口。

全局编码向量记录“这个包到底是哪几个源包的什么组合”。节点不必理解源数据的语义，只需对向量与负载实施同样的线性运算。

蝴蝶网络的一个 XOR ​

源将 $a,b\in {\mathbb{F}}_2$ 分别送到上、下分支。上分支把 $a$ 送给终点 $t_1$ 并送到中央节点；下分支把 $b$ 送给 $t_2$ 并送到中央节点。中央瓶颈只能传一个 bit，发送 $c=a+b$，再分送两终点。

$t_1$ 得到 $(a,c)$，计算 $b=c+a$；$t_2$ 得到 $(b,c)$，计算 $a=c+b$。例如 $(a,b)=(1,0)$ 时 $c=1$，前者算出 $1+1=0$，后者算出 $1+0=1$。两个接收矩阵分别为

都在 ${\mathbb{F}}_2$ 上可逆。若中央只原样转发 $a$，$t_1$ 仍缺 $b$；只转发 $b$，$t_2$ 仍缺 $a$。XOR 用同一个瓶颈符号同时服务两种缺口。

解码条件是秩，不是包数 ​

收到 $k$ 个包不代表有 $k$ 份独立信息。例如两包编码向量都是 $(1,1)$，接收矩阵只有秩一，无论重复多少次都不能区分 $(a,b)=(0,0)$ 与 $(1,1)$。满秩条件才是正确的验收标准。

实现时先为源包标注标准基向量，节点按拓扑顺序计算局部线性组合，终点用精确行化简公理库行化简Row reduction用初等行变换把矩阵化为阶梯形以求解线性方程组和判定秩。对编码向量矩阵作消元，再将相同消元作用于负载。每一步保持不变量“负载等于编码向量作用于原始数据”。若每包有 $L$ 个域符号，$k$ 包的朴素消元约用 $O(k^3+k^{2}L)$ 次域运算。

确定性存在性证明把各终点某个 $k$ 阶子式看作局部编码系数的多项式。单位容量的最大流最小割及整数性公理库最大流最小割定理Max-flow min-cut theorem以净跨割恒等式和残量可达集证明最大流等于最小割，并给出独立可检查的最优性证书。为每个终点给出 $k$ 条边不交源汇路。对单个终点，沿这些路径选路由系数便使一个接收子式为 $\pm 1$，因此该子式多项式在所用域上不恒为零；各终点的非零子式相乘仍非零。在足够大的域中可同时避开它们的零点。随机线性网络编码公理库随机线性网络编码Random linear network coding · RLNC通过随机选择局部有限域系数构造多播码，并用满秩概率与多项式零点界量化失败风险。进一步直接随机选择这些系数，用非零多项式的零点概率控制失败。