Witsenhausen 率

信道编码从全部顶点中挑出一个互不混淆的子集；源编码却不能挑掉任何可能源串，必须把全部顶点分成若干互不冲突的色类。

块编码的收益来自色类形状更灵活。单字颜色的逐坐标组合只是一个可行方案，最优长块色类可以斜着穿过乘积空间，而不必是逐字色类的笛卡尔积。

C5的两字五色编码表 ​

一次五边形有奇环，不能用两色；用三色可以做到，所以 $\chi (C_5)=3$。两次编码时，对顶点 $(i,j)\in {\mathbb{Z}}_5^2$ 定义

完整标签表为：

检查它是不是合法着色公理库图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。。相邻的不同顶点，其两个坐标差 ${\delta }_i,{\delta }_j$ 都在 $\{0,\pm 1\}$，且不全为0。如果同色，就有 ${\delta }_j=2{\delta }_i(\mathrm{mod}5)$。当 ${\delta }_i=\pm 1$，右边是 $\pm 2$，不可能等于允许的 ${\delta }_j$；当 ${\delta }_i=0$，等式又迫使 ${\delta }_j=0$。两种情况都矛盾。

因此25个源串只需五个标签，给出两字率 $\frac{1}{2}{\log }_{2}5$；逐字三色则有9个组合标签。只发送一个两字块时，二进制取整分别是3位与4位。长期使用时，要把 $k$ 份块标签联合编号：五色方案的全部 $5^k$ 个标签序列只需 $\lceil k{\log }_{2}5\rceil$ 位，逐字三色方案的 $9^k$ 个标签序列则需 $\lceil k{\log }_{2}9\rceil$ 位；除以 $2k$ 才分别趋于 $\frac{1}{2}{\log }_{2}5$ 与 ${\log }_{2}3$。若机械地给每个两字块固定分配3位，再串接下去，率仍是 $3/2$，不会自动消去每块的取整损失。

为什么这里能算出精确渐近率 ​

每个色类都是独立集，所以对任意图 $H$，

五边形的容量证书公理库Shannon 零错误容量与强图积Shannon capacity of a graph由无记忆支持推导强图积，证明独立数的超乘性及容量极限，并用五个二字码展示联合编码收益。已给出 $\alpha (C_5^{⊠n})\le (\sqrt{5}{)}^n$，故

两字五色表不断拼接给出偶数块长的反向上界；奇数块长再加一份三色标签，其常数开销除以块长后消失。因此

这不是说所有图的源描述率都等于信道容量。本例的对称结构使上下界恰好闭合；两个定义仍分别优化染色数和独立数。

三点路径的整段答案 ​

对路径 $a-b-c$，逐字两色给出 $\chi (G^{⊠n})\le 2^n$。另一方面，限制输入每一坐标只能取相邻的 $a,b$，得到一个有 $2^n$ 个顶点的完全子图，必须使用 $2^n$ 个颜色。因此每个块长恰为 $2^n$，$R_W(G)=1$。

若三点路径的四个支持概率是 $0.49,0.01,0.01,0.49$，则 $H(X\mid Y)=h_2(0.02)\approx 0.1414$，仍不改变 $R_W=1$。趋零错误与严格零错误的差距可以很大。

极限由次可加性保证 ​

把一个 $r$ 字着色和一个 $s$ 字着色的标签并列，可得到 $r+s$ 字着色：如果两份长串相邻且不同，至少有一个不同的子块在其强幂里相邻，其标签必不同。因此

令 $b_n={\log }_2\chi (G^{⊠n})$，并置 $b_0=0$（空块只需一个标签），则它次可加。固定 $r$，写 $n=kr+t$，有 $b_n\le k{b}_r+b_t$；$0\le t<r$ 的余项有统一常数上界。除以 $n$ 得 $lim sup{b}_n/n\le b_r/r$，再对 $r$ 取下确界，与显然的下界相合，证明式 (1)。

一般地，色类大小下界与逐字着色给出

图熵公理库图熵与随机独立集Graph entropy · Körner graph entropy以包含真实顶点的随机独立集定义图熵，证明稳定集多面体公式，并算出路径与均匀五边形，区分随机辅助信息、着色熵和固定长强积率。会同时考虑顶点频率和独立集，并对应不同的平均描述与图积设置。使用时应先声明：是否每个支持串都必须正确、是否固定最坏码长、使用强积还是 OR 积。仅说“零错误压缩率”不足以确定哪一个数。