“带边信息的索引编码在接收者已有部分消息时重新设计公共广播,属于不同的通信任务。例如三人分别知道下一人的 bit,广播两个 XOR 即可让所有人恢复自己的 bit。它不违反标准 Indexin…”
形式陈述
发送者知道
本页先取每条消息为一个有限域符号并要求零错误。用有向图表示边信息,约定
标量线性码广播
直觉
同一个 XOR 对不同接收者有不同用途。知道
最小秩刻画只覆盖指定域上的标量线性码。把消息拆成长向量、改用另一有限域或允许非线性编码,最短长度可能改变。
例子与边界
三个接收者构成有向环
令
即可。接收者 1 用
若
证明下界时,向一个联合译码者额外给
边信息的方向不能反读
在上例,箭头
如果人人已知除自己外的全部消息,二元消息的一次总 XOR 就够(一般域取所有消息之和);如果人人没有边信息,公共广播必须包含全部独立消息的信息量,无法凭编码无条件缩短。
推论与应用
缓存更新是自然场景:客户端已有不同旧数据,服务器通过公共广播补齐缺失块。设计时应先列出每个接收者真实拥有的内容,再检查逐个解码等式。仅展示一个低秩矩阵而未核对哪些项为已知,可能让译码器用上它实际上没有的数据。
参考资料
- Bar-Yossef、Birk、Jayram 与 Kol,“Index Coding with Side Information”,最小秩刻画、图结构与一般码下界。