带边信息的零错误源编码

编码器不必告诉对方“我一定是哪一个源值”，只要让对方结合自己手中的 $Y$ 后能唯一定位即可。因此，两个从不会与同一个 $y$ 同时相容的源值，可以共用标签。

但编码器不知道当前 $Y$，必须提前使用同一张编码表，保证所有可能 $y$ 都能处理。这种全局一致的标签安排，正好是图着色。

三种源值只需一位标签 ​

取 $X\in \{a,b,c\}$、$Y\in \{0,1\}$，仅四个联合支持点概率为正；为了计算方便，先令它们各占 $1/4$：

当 $Y=0$ 时，$a,b$ 必须区分，形成边 $ab$；当 $Y=1$ 时，$b,c$ 必须区分，形成边 $bc$。$a,c$ 没有共同相容的 $y$，所以没有边。

编码表取 $e(a)=e(c)=0$、$e(b)=1$。译码表为

四个支持点逐一代入都恢复正确。由于存在一条冲突边，一个标签不可能够用，因此最少标签数恰为2。

没有边信息时，三个源值都要区分，需要三条标签、固定二进制长度2位；这里一位就够。节省来自合法支持限制，不是从小概率错误里省出来的。

为什么着色正好刻画编码 ​

若相邻 $x,x^{\prime }$ 赋同一标签，取见证它们相邻的 $y$。译码器收到的 $(e(x),y)$ 与 $(e(x^{\prime }),y)$ 完全相同，却被要求输出两个不同值，必有一个支持点出错。因此任何合法编码都必须是正确着色。

反过来，给定正确着色，固定标签 $z$ 和边信息 $y$。这个色类中至多有一个 $x$ 与 $y$ 相容，否则两者相邻而同色。译码器输出这个唯一值；若一个都没有，该组合不会发生，填什么值都不影响正确性。

图相同，概率可以不同 ​

把上表四个正概率改为 $0.49,0.01,0.01,0.49$，并不改变支持、路径图或最少标签数。可是在已知 $Y$ 时，源值几乎由 $Y$ 决定，条件熵变得很小。

严格零错误仍要处理那两类罕见事件。若把其中一个小概率直接删成零，图可能少一条边，才会改变这个固定长问题。

这里的目标不同于普通源编码公理库信源码Source code以码字表示信源符号或符号块，并区分单射、串联唯一可译与前缀结构。的平均码长优化。图着色先最小化标签集合大小；给颜色按概率再作前缀编码，会形成另一种带概率权重的目标，不能用一个染色数同时回答所有问题。

对独立同分布的块源，两个 $X$ 串发生冲突需要存在同一个完整 $Y$ 串同时相容。由无记忆支持，这变成每一坐标相等或相邻，进而得到强图幂的着色率公理库Witsenhausen 率Witsenhausen rate用强图幂的染色数定义严格零错误固定长描述率，证明极限存在，并显式构造五边形两字五色码及其精确渐近率。。

Slepian–Wolf 定理公理库Slepian–Wolf 分布式无损压缩定理Slepian-Wolf theorem两个相关离散无记忆源分别编码、共同译码时，条件熵与联合熵精确给出无损压缩速率区域。的 $H(X\mid Y)$ 结论允许块错误概率趋零，不要求每个有限块长的每个支持点都正确。两者都利用译码端边信息，但删除小概率例外是否被允许，是实质差别。

如果译码端只需要某个函数值而不是整个 $X$，有些冲突还可解除。函数计算的特征图公理库函数计算的特征图Characteristic graph for function computation只连接在共同边信息下产生不同函数值的源输入，给出一次着色码和完整概率例子，再明确区分严格零错与条件图熵的趋零块错误率。只连接在相同 $y$ 下会给出不同目标函数值的输入，必须重新画图，而不是沿用恢复整个源的着色。