函数计算的特征图

源恢复的标签要把所有仍可能的 $X$ 分开；函数计算只要把会产生不同答案的输入分开。因此可以不区分“对象不同，但对本次任务永远等价”的输入。

这种等价必须逐个合法 $y$ 检查。只有在某个 $y$ 下函数值相同，不足以全局合并；只要另一个共同相容的 $y$ 会产生不同值，两输入之间仍应有边。

一份完整的支持与函数表 ​

令 $X\in \{a,b,c\}$，$Z={\mathbf{1}}_{\{X=c\}}$，目标为 $f(X,Y)=Z\oplus Y$。联合概率如下，六个格子都为正：

恢复整个 $X$ 时，任何两个源值都与同一个 $y$ 相容，冲突图为 $K_3$，需要三条消息。计算 $f$ 时，$a,b$ 在两个 $y$ 下都给相同答案，因此边 $ab$ 消失；$ac,bc$ 仍是边。

编码器发送 $e(a)=e(b)=0,e(c)=1$，也就是发送 $Z$。译码器计算 $e(X)\oplus Y$。每个支持点都正确，消息数从3降为2。由于图中仍有边，一个消息不够，所以一次最优性也得到证明。

条件图熵可以完整算出 ​

$G_f$ 的两个极大独立集为 $\{a,b\}$ 与 $\{c\}$。任一可行集合变量 $W$ 都能扩成其中之一；这个确定后处理仍满足 $W-X-Y$；对每个正概率 $Y=y$ 应用数据处理不等式公理库数据处理不等式Data processing inequality对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。再平均，便知它不增加条件互信息。因此最优可直接取 $W$ 对应 $Z$，

从表中有 $P(Y=0)=5/8$，$P(Z=1\mid Y=0)=1/10$；$P(Y=1)=3/8$，$P(Z=1\mid Y=1)=1/2$。于是

相比之下，完整恢复的条件熵公理库条件熵Conditional entropy已知一个随机变量后另一个随机变量剩余不确定性的平均值。为

第二项是 $Z=0$ 时还要辨认 $a,b$ 的成本。目标函数不需要这项信息，所以它可以消失。

0.668122不等于严格零错固定长率 ​

因为表中全支持，长度 $n$ 的每个 $Z$ 串都可能与任意 $Y$ 串相容。若两个不同 $Z$ 串被赋同一标签，固定同一个 $Y$ 串，两个目标向量 $Z^n\oplus Y^n$ 必不同。因此严格零错必须区分全部 $2^n$ 个 $Z$ 串，固定长至少为 $n$ 位；直接发 $Z^n$ 达到这个界。

所以同一问题中，一次最少消息数是2，严格零错固定长率是1，而允许块错误趋零时最优率约为0.668122。三个数不矛盾，它们使用不同的错误与资源标准。

一次着色与独立集为何足够 ​

若相邻输入同色，式 (1) 的见证 $y$ 会使译码器面对相同记录却需要输出不同函数值，故不可能正确。若色类独立，固定色类和 $y$ 后，所有相容输入的函数值必相同；任选一个相容输入计算 $f$ 即可。

随机独立集版本同样成立：给定 $W=w,Y=y$，所有支持内的 $x\in w$ 都给出同一函数值。因此存在确定恢复函数 $g$，使 $f(X,Y)=g(W,Y)$ 几乎必然。

Markov 条件不能省略。编码器只能按观察到的 $X$ 选择清单，不能偷看当前 $Y$ 后决定用哪一个 $W$。仅写“$W$ 是包含 $X$ 的独立集”却让其条件分布依赖 $Y$，会赋予编码端未声明的边信息。

趋零错误率的证明机制 ​

固定一个满足条件的 $P_{W\mid X}$。编码器用随机码本覆盖典型 $X^n$，寻找与它匹配的 $W^n$，候选码本大小约为 $2^{nI(X;W)}$；再用随机分箱，让译码端借助 $Y^n$ 消除约 $I(Y;W)$ 的描述成本。由 $W-X-Y$，

译码端以高概率恢复 $W^n$ 后，逐坐标用 $g(W_i,Y_i)$ 算出函数。典型性失败、覆盖失败和分箱冲突都只保证总概率趋零，因此不能把这个论证改名为每块严格无错。

反向证明把一个长块消息与其他坐标的边信息组合成单坐标辅助变量，利用源的无记忆性得到 Markov 条件，再用信息链式法则下界消息率。错误趋零使极限辅助变量满足函数值确定性；同一辅助值支持的输入因而构成式 (1) 的独立集，得到式 (2) 的下界。[1,2]

如果研究严格零错的函数块图，其边还要求存在一个完整的共同相容 $Y^n$，并至少一坐标输出不同。一般有零支持时，不能无条件把它直接写成 $G_f$ 的 OR 幂；OR 着色可提供充分方案，却可能加入不必要的冲突。这也是必须先从通信语义画图的原因。