返回学习路线

单元终点任务：为同一张图写出三种编码证书 ​

任务背景 ​

五边形既会描述信道的混淆，也会描述源编码的标签冲突。但“选几个顶点”“给全部顶点染几色”“按出现频率平均花多少信息”是三个不同问题。完成下列任务时，每个数都应同时写明：图边的含义、使用的图积、错误标准和资源单位。

题目 ​

A. 两次五边形信道与容量证书 ​

信道输入、输出均为 ${\mathbb{Z}}_5$，输入 $i$ 以各 $1/2$ 的概率输出 $i$ 或 $i+1$。

1. 画支持表与混淆图公理库零错误信道与混淆图Confusability graph把有限信道的正概率支持转为混淆图，证明一次严格零错误码恰是独立集，并用五边形与微小正噪声说明支持约束。，证明一次只能传两条消息
2. 验证码本 $\{00,12,24,31,43\}$ 的任意两条不混淆；列出其中00与12各自的四个可能输出
3. 用每条边权重 $1/2$ 给出分数团覆盖公理库分数团覆盖的零错误容量上界Fractional clique cover bound给混淆图的团赋覆盖权重，利用独立集每团至多一点和乘积团证书上界全部块长，并用原对偶精确计算C5的5/2。及其对偶证书。它能否已经证明容量精确值？
4. 用 $a=1/\sqrt{5}$ 和正文的三维向量，检查单位长度、非边正交及柄投影；据此得到theta公理库Lovász theta 函数与零错误容量上界Lovász theta function · Lovász number用非邻点正交表示和单位柄向量证明容量上界，再给半正定原对偶及乘积证书，精确算出五边形的√5容量。上界，与码本下界夹出容量
5. 若把两个输出概率改为 $0.99,0.01$，哪些零错误证书保持不变？

B. 真正超过无反馈容量的有限反馈码 ​

现在开放无噪即时反馈。每一步，双方将当前候选消息按编号顺序尽量均分到五个输入：若 $M=5q+r$、$0\le r<5$，前 $r$ 组各有 $q+1$ 条，其余各 $q$ 条。收到输出 $y$ 后，只保留分到 $y-1,y$ 两组的消息，再重新编号与分配。

1. 对 $M=25$ 和 $M=10$，分别算下一步最多剩多少条
2. 定义并计算每步最坏候选数递推。从$$M_0=\lfloor (5/2{)}^{20}\rfloor =90949470$$出发，执行20步，最多剩多少条？
3. 用一对输出支持不交的输入完成收尾。给出固定总使用次数与实际率，验证它严格高于 ${\log }_2\sqrt{5}$
4. 为什么只模拟候选数量就能证明所有输出历史都适用，而不用在脚本里实际分配九千万条消息？说明这个计数检查不承诺编码器的计算与存储高效
5. 对三角形支持超图 $\{a,b\},\{b,c\},\{c,a\}$，每点权重 $1/2$ 给出 $A^{\ast }=3/2$。为什么不能照搬得到正反馈零错误容量？

C. 把五边形改当源冲突图 ​

假设编码器观察一个五值源，译码端的边信息产生同一个 $C_5$ 冲突图；要求每个支持串都严格正确。

1. 一次最少标签数是多少？两字标签 $e(i,j)=j-2i(\mathrm{mod}5)$ 为什么是合法着色？
2. 证明Witsenhausen 率公理库Witsenhausen 率Witsenhausen rate用强图幂的染色数定义严格零错误固定长描述率，证明极限存在，并显式构造五边形两字五色码及其精确渐近率。为 ${\log }_2\sqrt{5}$
3. 把两个两字块的标签一起传送，为什么只需5位，而不是逐块3位共6位？写出一般 $k$ 块的位数公式
4. 若 $X$ 在单字五边形上均匀，计算图熵公理库图熵与随机独立集Graph entropy · Körner graph entropy以包含真实顶点的随机独立集定义图熵，证明稳定集多面体公式，并算出路径与均匀五边形，区分随机辅助信息、着色熵和固定长强积率。与一次最小颜色熵。解释它们为何不等于上一问的固定长强积率

D. 译码目标改变之后，必须重新画图 ​

先考虑只有四个支持点的三值源：$(a,0),(b,0),(b,1),(c,1)$。各点概率可以任取正值。

1. 写出恢复整个X公理库带边信息的零错误源编码Zero-error source coding with side information以联合支持定义源冲突图，证明编码标签恰是合法着色，并用三值路径例子展示译码端的Y怎样使不相邻源值复用标签。的一位编码表和译码表

再考虑以下全支持分布与目标 $f(X,Y)={\mathbf{1}}_{\{X=c\}}\oplus Y$：

$X$	$Y=0$	$Y=1$
$a$	$3/8$	$1/8$
$b$	$3/16$	$1/16$
$c$	$1/16$	$3/16$

2. 分别画出恢复整个 $X$ 与只计算 $f$ 的冲突图，写出一次最少标签数
3. 计算条件图熵 $H_{G_f}(X\mid Y)$ 与 $H(X\mid Y)$
4. 证明严格零错固定长函数率仍为1，并指出为什么趋零块错误率约0.668122不与它冲突
5. 若辅助集合变量 $W$ 被允许偷偷依赖当前 $Y$，它违背了哪一个编码权限条件？

完整解答 ​

A. 每个上界都给出可检查对象 ​

输入 $i$ 的输出支持是 $\{i,i+1\}$。不同输入有共同输出，当且仅当下标差为 $\pm 1$，所以混淆图是五边形。独立集可选 $\{0,2\}$；每个选中点都要占用一个不能再选的后继，故 $2|I|\le 5$，最优恰为2。

码字00的输出为 $\{00,01,10,11\}$，码字12的输出为 $\{12,13,22,23\}$，二者不交。一般地，两码字第一坐标差若为 $\pm 2$，第一坐标就能区分；若为 $\pm 1$，第二坐标差为 $\pm 2$。所以五个码字的输出支持两两不交，总共覆盖20个不同输出对。

五条边各赋覆盖权重 $1/2$，每个顶点被覆盖1，总权重 $5/2$。对偶把五个顶点各赋 $1/2$，每个团总量不超过1，目标同样为 $5/2$，证明该LP最优。乘积团证书给 $\mathrm{\Theta }(C_5)\le 5/2$，但这还不是精确容量。

三维表示为

$$u_i=(\sqrt{1-a}\cos \frac{2\pi i}{5},\sqrt{1-a}\sin \frac{2\pi i}{5},\sqrt{a}),a=1/\sqrt{5},c=(0,0,1).$$

它们长度平方为 $(1-a)+a=1$；非边间距是两个圆周位置，内积 $(1-a)\cos \left(4\pi /5\right)+a=0$；柄投影平方恒为 $a$。因此每个块长的独立集大小都不超过 $(\sqrt{5}{)}^n$。结合两次五消息码，

$$\mathrm{\Theta }(C_5)=\sqrt{5},C_0={\log }_2\sqrt{5}\approx 1.160964.$$

改变正转移概率而不改变支持，不会改变混淆图、码本、分数证书、theta或严格零错误容量；普通互信息容量则可能改变。

B. 21次使用的具体反馈增益 ​

若各输入组大小为 $n_0,\dots ,n_4$，输出 $y$ 留下 $n_{y-1}+n_y$ 条候选。对25，组大小为 $(5,5,5,5,5)$，最多剩10；重新分配10为 $(2,2,2,2,2)$，下一步最多剩4。

令

$$F(M)=\underset{y}{max}(n_{y-1}+n_y),n_j=\lfloor M/5\rfloor +{\mathbf{1}}_{\{j<Mmod5\}}.$$

完整最坏数量表如下：

次数	候选上界	次数	候选上界
0	90,949,470	11	3,816
1	36,379,788	12	1,527
2	14,551,916	13	612
3	5,820,767	14	246
4	2,328,308	15	99
5	931,324	16	40
6	372,530	17	16
7	149,012	18	7
8	59,606	19	4
9	23,843	20	2
10	9,538

第20次之后至多两条。双方知道同一个剩余候选表，发送端用输入0或2表示其中哪一条是真消息；它们的输出支持 $\{0,1\}$ 与 $\{2,3\}$ 不交，故再用一次即可完成。若已只剩一条，也填充一次约定输入，保证总长度固定为21。

实际率为

$$\frac{{\log }_{2}90949470}{21}\approx 1.258979>1.160964.$$

这给出一个有限长反馈码，已经超过任何无反馈块码可达到的渐近零错误率；它还低于反馈上限 ${\log }_2(5/2)\approx 1.321928$。

数量递推充分，是因为每步均衡分组对每个输出的剩余数都有同一个上界，且 $F(M)$ 对整数 $M$ 单调不减：当 $M$ 增加1，只会让某个输入组多一条，其他组不变。实际候选数小于上界时，下一步最坏数也不会更大。编号只用于落实分配规则，不影响这些计数。这个论证没有限制编码器存储/计算成本，脚本检查的也不是九千万条码字的显式执行。

三角形支持信道没有输出支持不交的输入对。无论两个剩余候选下一步选什么输入，总能找共同可能输出，使它们同时存活到任意有限终点。分数收缩可以留下一个小列表，却不能完成最后的零错误区分。因此 $C_{0F}=0$；公式 $\log A^{\ast }$ 的非完全图条件不可省。

C. 独立集变成覆盖全部顶点的色类 ​

一次五边形需三色。两字标签 $j-2i$ 同色意味着坐标差满足 ${\delta }_j=2{\delta }_i(\mathrm{mod}5)$；强积的一条边要求两差都在 $\{0,\pm 1\}$ 且不全为零，两项要求无法同时成立。因此五色表合法，每个色类有五个点。

任意 $n$ 字着色的每个色类至多 $(\sqrt{5}{)}^n$ 个顶点，所以颜色数至少为 $5^n/(\sqrt{5}{)}^n=(\sqrt{5}{)}^n$。两字五色表联合使用达到相同指数增长，得到 $R_W(C_5)={\log }_2\sqrt{5}$。

两份五色标签有25种组合，联合编号只需 $\lceil {\log }_{2}25\rceil =5$ 位。一般 $k$ 块只需 $\lceil k{\log }_{2}5\rceil$ 位，而不是每块先向上取整为3位再拼接。后者始终是 $3/2$ bit/symbol，不能用渐近极限自动消掉每块浪费。

均匀五边形的随机独立集可让 $W$ 在五个非邻点对上均匀、$X\mid W$ 在两点上均匀，故

$$H_G(P)={\log }_{2}5-1={\log }_2(5/2)\approx 1.321928.$$

一次确定着色的最优色类大小为 $2,2,1$，颜色熵为 ${\log }_{2}5-4/5\approx 1.521928$。图熵对应 OR 幂约束下的平均描述率，Witsenhausen率对应强幂与最坏固定长度；一次颜色熵又没有跨块优化。这里数值相近，也不能互换。

D. 函数目标删掉的是具体冲突 ​

四点支持源的图为路径 $a-b-c$。发送 $e(a)=e(c)=0,e(b)=1$；标签0配 $Y=0$ 恢复 $a$，配 $Y=1$ 恢复 $c$；标签1始终恢复 $b$。这张表对所有正概率支持点正确，概率具体大小不影响结论。

后面的全支持分布则使恢复图为 $K_3$，一次需三标签。目标函数只在意 $Z={\mathbf{1}}_{\{X=c\}}$，$a,b$ 对所有 $y$ 都给同样函数值，只有 $ac,bc$ 两条边，一次需两标签。发送 $Z$ 后由译码端异或 $Y$ 即可。

对函数图，只需考虑两个极大独立集 $\{a,b\}$、$\{c\}$，最优辅助变量等价于 $Z$。表中 $P(Y=0)=5/8$、$P(Z=1\mid Y=0)=1/10$，另一条件下 $P(Z=1\mid Y=1)=1/2$，所以

$$H_{G_f}(X\mid Y)=\frac{5}{8}{h}_2(1/10)+\frac{3}{8}\approx 0.668122,$$$$H(X\mid Y)=H(Z\mid Y)+\frac{3}{4}{h}_2(1/3)\approx 1.356844.$$

严格零错时，每个 $Z^n$ 都与每个 $Y^n$ 相容，任意不同 $Z^n$ 都必须用不同消息。因此需要至少 $2^n$ 个消息，率至少1；直接发 $Z^n$ 达到1。Orlitsky–Roche率0.668122允许整块错误概率趋零，正是可以舍弃小概率坏事件的另一个问题。

最后，$W-X-Y$ 要求 $P_{W\mid X,Y}=P_{W\mid X}$：编码器只观察 $X$。让辅助集合按实际 $Y$ 决定，就改变了编码端权限，不能再用于原模型的下界或可达率。

验收标准 ​

• 每条混淆边有共同输出见证，每个码字对有不混淆坐标见证
• 分数覆盖与对偶逐顶点/逐团检查；theta的边零与非边正交方向正确
• 容量增长因子与bit/use、源标签数与固定二进制位数分别记账
• 能从均衡分组算出20步候选表和21次固定总长度，不借用期望停止时间
• 能解释完全图缺少收尾输入对，以及同一混淆图可能对应不同支持超图
• 强积固定长率、OR积平均图熵和函数的趋零错误率不混用
• 函数图逐个共同合法 $y$ 检查；辅助变量的Markov权限未省略

下载 Python 复算脚本。脚本枚举小图、检查向量/矩阵证书、核算概率与所有候选分组上界；渐近结论仍由正文的一般证明与明确引用的编码定理支撑。