“若两个编码器分别看到相关源,而译码器同时收到两边描述,独立编码并不要求分别支付两个边缘熵。Slepian–Wolf 定理以两个条件熵下界和一个联合熵总率界刻画可达区域;随机分箱让译码器利用相…”
形式陈述
设
以
这里条件熵表示已知另一条序列后剩下的不确定性。对数底为
直觉
编码器虽然不能互看数据,译码器却能利用两序列的相关性。每边无需各自给出足以单独恢复的描述,只需把真序列所在的候选集合缩小到:两边合起来仅剩一对相容的典型序列。
随机分箱为什么给三条界
把每条
三类典型候选数量分别约为
必要性则向译码器额外公开另一条源序列,用Fano 不等式分别得到两个条件熵下界;对联合恢复再用一次 Fano,得到总率下界。额外公开信息只会帮助译码,因此这些仍是原问题必须满足的界。
例子与边界
令
两个独立使用普通无损压缩器需要总率
当
若把
图中对称点为
推论与应用
边信息全部放在译码器时,可取一边以其熵率完整发送,再让另一边只付条件熵。Wyner–Ziv 编码进一步允许有损恢复,届时“分箱后利用边信息”仍是核心,但优化对象变成辅助表示与失真约束。
参考资料
- Slepian 与 Wolf,“Noiseless Coding of Correlated Information Sources”,1973。
- El Gamal 与 Kim,《Lecture Notes on Network Information Theory》2010 完整 v4,Chapter 11;ISIT 2011 教程中 Distributed Lossless Source Coding 部分。