Slepian–Wolf 分布式无损压缩定理

编码器虽然不能互看数据，译码器却能利用两序列的相关性。每边无需各自给出足以单独恢复的描述，只需把真序列所在的候选集合缩小到：两边合起来仅剩一对相容的典型序列。

随机分箱为什么给三条界 ​

把每条 $x^n$ 独立分配到约 $2^{n{R}_X}$ 个箱，把每条 $y^n$ 分到约 $2^{n{R}_Y}$ 个箱。发送箱号，译码器在两个箱内寻找唯一联合强典型公理库强典型性Strong typicality · Strongly typical set · Type typicality在有限字母表上逐符号约束经验频率接近真实分布的典型性。对。错误分三类：$Y^n$ 正确而 $X^n$ 错；$X^n$ 正确而 $Y^n$ 错；两者都错。

三类典型候选数量分别约为 $2^{nH(X|Y)}$、$2^{nH(Y|X)}$、$2^{nH(X,Y)}$，撞到指定箱的概率分别约为 $2^{-n{R}_X}$、$2^{-n{R}_Y}$、$2^{-n(R_X+R_Y)}$。在三条严格不等式内，并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。使错误趋零，再取闭包得到边界。

必要性则向译码器额外公开另一条源序列，用Fano 不等式公理库Fano 不等式Fano's inequality用估计错误概率上界条件熵，从而把信息不足转化为推断下界。分别得到两个条件熵下界；对联合恢复再用一次 Fano，得到总率下界。额外公开信息只会帮助译码，因此这些仍是原问题必须满足的界。

令 $X$ 均匀为 bit，$Y=X\oplus N$，其中 $N\sim \mathrm{Bern}(0.1)$ 独立。$X,Y$ 各自均匀，但只以 $0.1$ 概率不同，所以

两个独立使用普通无损压缩器需要总率 $2$；分布式方案可逼近 $(1,0.469)$ 或对称点 $(0.7345,0.7345)$。候选 $(0.5,0.5)$ 虽满足两条单独下界，却违反总率，不能恢复整对源。

当 $Y=X$，条件熵均为零，但总率仍至少为 $1$。当两者独立时，条件熵恢复各自熵，相关性不再带来节约。定理允许小概率整块失败，也不承诺随机分箱的穷举译码高效。

若把 $Y$ 直接交给译码端，并要求每个支持点都正确，问题改为带边信息的严格零错误源编码公理库带边信息的零错误源编码Zero-error source coding with side information以联合支持定义源冲突图，证明编码标签恰是合法着色，并用三值路径例子展示译码端的Y怎样使不相邻源值复用标签。：一次最少标签数由冲突图的染色数决定，长块的最坏固定长度由Witsenhausen 率公理库Witsenhausen 率Witsenhausen rate用强图幂的染色数定义严格零错误固定长描述率，证明极限存在，并显式构造五边形两字五色码及其精确渐近率。刻画。极小但正的支持概率不能被舍弃，因此一般不能把该率替换成 $H(X\mid Y)$。

图中对称点为 $((1+h_2(0.1))/2,(1+h_2(0.1))/2)\approx (0.7345,0.7345)$。绿色区域向右上延伸，坐标单位为 bit/对源符号。

边信息全部放在译码器时，可取一边以其熵率完整发送，再让另一边只付条件熵。Wyner–Ziv 编码公理库Wyner–Ziv 带边信息有损编码Wyner-Ziv coding在编码器看不到边信息时，用辅助描述与分箱得到译码端边信息下的最小有损编码率。进一步允许有损恢复，届时“分箱后利用边信息”仍是核心，但优化对象变成辅助表示与失真约束。