Shannon 零错误容量与强图积

形式陈述

设 $G$ 是有限非空简单混淆图。它的强积 $G\boxtimes H$ 以顶点对 $(x,y)$ 为顶点；两个不同顶点 $(x,y),(x',y')$ 相邻，当且仅当

(x=x'\text{ 或 }x\sim_Gx') \quad\text{且}\quad (y=y'\text{ 或 }y\sim_Hy'). \tag{1}

记 $G^{\boxtimes n}$ 为 $n$ 次强幂。无记忆信道上，两个输入串可能产生相同输出串，恰好是每一坐标的输入相等或相邻。所以无反馈、固定块长 $n$ 的最优零错误消息数为

M_n=\alpha(G^{\boxtimes n}).

图的 Shannon 容量定义为消息增长因子

\Theta(G)=\lim_{n\to\infty}\alpha(G^{\boxtimes n})^{1/n} =\sup_{n\ge1}\alpha(G^{\boxtimes n})^{1/n}. \tag{2}

对应的信息率是

C_0(W)=\log_2\Theta(G_W)\quad\text{bit/use}.

$\Theta$ 本身不是每次使用的比特数；文献也有直接把取对数的量称作图容量的约定，使用公式前应先核对。[1]

直觉

两个串要发生混淆，每一坐标都必须能“配合”产生同一输出。只要有一个坐标明确不能混淆，整对串就能区分。这给设计者留下空间：第一坐标很相近的两条消息，可以故意把第二坐标放得很远。

逐次独立选一次最优码，只利用了每一坐标都安全的方案；联合编码允许不同消息对在不同坐标被区分，可能获得更大的总码本。

红框标出00在强积中的闭邻域，含自身和与它混淆的输入；其余四个蓝色码点都在框外。模5的首尾相邻也已计入。

例子与边界

一次 $C_5$ 只有两个互不混淆输入。两次联合使用时，选择

\mathcal C=\{(i,2i\bmod5):i=0,1,2,3,4\} =\{00,12,24,31,43\}.

任取两个不同码字，令第一坐标差为 $d\in\{1,2,3,4\}$ 。若 $d=\pm2\pmod5$ ，第一坐标已经不相邻。若 $d=\pm1$ ，第一坐标虽然相邻，第二坐标差为 $2d=\pm2$ ，所以第二坐标不相邻。

因此每一对都由某一坐标区分，五个码字构成强积中的独立集。于是

\alpha(C_5^{\boxtimes2})\ge5>2^2, \qquad \Theta(C_5)\ge\sqrt5.

这已经证明两次独立选码不是最优。要把下界升级为精确容量，还需对所有块长的上界；Lovász theta 函数给出的正是 $\sqrt5$ 。

若 $I$ 是 $G^{\boxtimes r}$ 的独立集、 $J$ 是 $G^{\boxtimes s}$ 的独立集，把两段串拼接得到 $I\times J$ 。任意两份拼接串只要在某一段不同，就由该段的独立性找到不混淆坐标。因此

\alpha(G^{\boxtimes(r+s)}) \ge\alpha(G^{\boxtimes r})\alpha(G^{\boxtimes s}).

令 $a_n=\log_2\alpha(G^{\boxtimes n})$ ，并置 $a_0=0$ （空块只有一个码字），则 $a_{r+s}\ge a_r+a_s$ ，并有 $0\le a_n\le n\log_2|V(G)|$ 。

固定块长 $r$ ，把 $n=kr+t$ ， $0\le t<r$ 。由超可加性， $a_n\ge ka_r+a_t\ge ka_r$ ，故

\liminf_{n\to\infty}\frac{a_n}{n}\ge\frac{a_r}{r}.

它对每个 $r$ 成立；另一方面每项 $a_n/n$ 都不超过这些比值的上确界。因此上下极限相同，极限等于上确界，式 (2) 得证。这不表示某个有限块长一定达到极限。

强积要求每一坐标“相等或相邻”。笛卡尔积只连接恰有一个坐标改变且该坐标相邻的顶点；OR 积则只要某个坐标相邻就连边，而不管其他坐标。它们给出不同约束。

例如 $C_5$ 中的串 $00$ 与 $12$ ，第一坐标相邻、第二坐标不相邻：在强积中不相邻，可以同处零错误码；在 OR 积中相邻。把 OR 积误放进式 (2)，会直接否定刚才的五消息码。

推论与应用

完全图的所有强幂仍完全，故 $\Theta(K_m)=1$ ；无边图的强幂仍无边，故 $\Theta(\overline K_m)=m$ 。因此有限信道具有正的无反馈零错误容量，当且仅当存在一对输出支持不交的输入，也就是混淆图不完全。

普通Shannon 信道容量允许错误概率随块长趋零，可删除极小概率的坏事件；严格零错误容量不允许这一步。两者都研究长块，但错误标准不同，不可直接把 $\max I(X;Y)$ 代入式 (2)。

分数团覆盖和 theta 都给出跨越全部块长的证书。另一个对偶方向是Witsenhausen 率：发送源描述时要给强幂的全部顶点着色，而不是从中选一个独立集。相同图积因此出现于两个不同的优化任务。

参考资料

[1] László Lovász, On the Shannon Capacity of a Graph, 1979，§§I–II：容量极限、五边形两字码及强积。
[2] Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan and Giannicola Scarpa, Zero-error source-channel coding with entanglement, §1.1：经典模型中的强幂、独立数与着色数。本文只使用该节的经典定义。