带边信息的索引编码

形式陈述

发送者知道 $n\ge1$ 条消息 $x_1,\ldots,x_n$ ，每个消息组合都允许出现。接收者 $i$ 要恢复 $x_i$ ，并预先知道索引集 $S_i\subseteq[n]\setminus\{i\}$ 中的消息。索引编码寻找最短的定长公共广播：编码函数 $f:\mathbb F_q^n\to\mathbb F_q^\ell$ 给出 $B=f(x_1,\ldots,x_n)$ ，使每个接收者从 $(B,x_{S_i})$ 恢复 $x_i$ ，并最小化域符号数 $\ell$ 。

本页先取每条消息为一个有限域符号并要求零错误。用有向图表示边信息，约定 $i\to j$ 表示接收者 $i$ 已知 $x_j$ 。与一般源编码不同，压缩收益来自译码者各自持有的边信息，而非假定源消息相关。

标量线性码广播 $B=Lx$ 。若存在拟合矩阵 $M$ 满足 $M_{ii}=1$ 、当 $j\notin S_i\cup\{i\}$ 时 $M_{ij}=0$ ，且各行都在 $L$ 的行空间中，则接收者可算出 $M_i x$ ，再减去已知项得到 $x_i$ 。最小标量线性长度等于所有拟合矩阵的最小秩。

直觉

同一个 XOR 对不同接收者有不同用途。知道 $x_2$ 的人可以从 $x_1+x_2$ 取回 $x_1$ ，知道 $x_1$ 的人则取回 $x_2$ 。公共广播不必把每条消息逐条重发，只需让每个人结合已有信息完成自己的解码。

最小秩刻画只覆盖指定域上的标量线性码。把消息拆成长向量、改用另一有限域或允许非线性编码，最短长度可能改变。

例子与边界

三个接收者构成有向环

令 $S_1=\{2\},S_2=\{3\},S_3=\{1\}$ ，消息是 bit。广播两位

b_1=x_1+x_2,\qquad b_2=x_2+x_3

即可。接收者 1 用 $b_1+x_2$ ；接收者 2 用 $b_2+x_3$ ；接收者 3 先由 $b_1+x_1$ 求 $x_2$ ，再由 $b_2+x_2$ 求 $x_3$ 。

若 $(x_1,x_2,x_3)=(1,0,1)$ ，广播 $(1,1)$ ，三人依次恢复 $1,0,1$ 。两个广播比直接发送三位节省一位，却不能缩成一位。

证明下界时，向一个联合译码者额外给 $x_3$ 。它可模仿接收者 2 从广播恢复 $x_2$ ，再模仿接收者 1 恢复 $x_1$ 。因 $x_1,x_2$ 是两个独立均匀 bit，给定 $x_3$ 后广播仍须区分四种可能，故至少长两位。这个下界连非线性码也适用，所以本例两位确实最优。

边信息的方向不能反读

在上例，箭头 $1\to2$ 表示 1 已经知道 2 的消息，而非需要把 1 的消息发往 2。画图前固定约定，可以避免把一张网络路由图误当成边信息图。

如果人人已知除自己外的全部消息，二元消息的一次总 XOR 就够（一般域取所有消息之和）；如果人人没有边信息，公共广播必须包含全部独立消息的信息量，无法凭编码无条件缩短。

推论与应用

缓存更新是自然场景：客户端已有不同旧数据，服务器通过公共广播补齐缺失块。设计时应先列出每个接收者真实拥有的内容，再检查逐个解码等式。仅展示一个低秩矩阵而未核对哪些项为已知，可能让译码器用上它实际上没有的数据。

参考资料

Bar-Yossef、Birk、Jayram 与 Kol，“Index Coding with Side Information”，最小秩刻画、图结构与一般码下界。

形式陈述 ​

三个接收者构成有向环 ​

边信息的方向不能反读 ​

反向链接

形式陈述

三个接收者构成有向环

边信息的方向不能反读