返回学习路线

U19：分布式压缩、编码瓶颈与中继界 ​

题目 ​

1. $X$ 为均匀 bit，$Y=X\oplus N$，$N\sim \mathrm{Bern}(0.1)$ 且 $N$ 独立于 $X$。求 Slepian–Wolf 区域，判断 $(0.5,0.5)$ 与 $(0.75,0.75)$。
2. 蝴蝶网络上终点 $t_1$ 已收 $a$，$t_2$ 已收 $b$，中央边只传一个 bit。写出覆盖四种 $(a,b)$ 的 XOR 与各端解码。
3. 对一般三节点中继，分别写完整 DF 内界与切集外界。给一个二者吻合的无噪链，并解释何时不能宣称容量。
4. 中继与终点分别收到源 bit 的独立 $1/4$ 翻转观察，另有一条每次 $1$ bit 的正交无噪中继链。验证无损描述的 CF 约束，并比较其可达率与完整 DF 的中继译码瓶颈。

解答 ​

二元熵 $h_2(0.1)\approx 0.468996$，所以

$$R_X\ge 0.468996,R_Y\ge 0.468996,R_X+R_Y\ge 1.468996.$$

$(0.5,0.5)$ 违反总率；$(0.75,0.75)$ 严格满足三条界，可由足够长块编码可靠实现。独立编码指双方运行时各见一条源，并不要求码本设计独立，也不阻止译码器利用源相关。

中央发送 $c=a\oplus b$。四种情况为：$00\mapsto 0$、$01\mapsto 1$、$10\mapsto 1$、$11\mapsto 0$。$t_1$ 分别用 $c\oplus a$ 得到 $0,1,0,1$，恰为 $b$；$t_2$ 用 $c\oplus b$ 得到 $0,0,1,1$，恰为 $a$。每个终点得到两条独立线性方程。

DF 的可达率为

$$\underset{p(x_1,x_2)}{max}min\{I(X_1;Y_2|X_2),I(X_1,X_2;Y_3)\},$$

切集外界则将第一项放宽成 $I(X_1;Y_2,Y_3|X_2)$。中继必须独自译出消息，而切集允许中继与终点汇总观察，正是这两个第一项的区别。对无噪 $2$ bit 链接 $1$ bit 链的串联网络，两者都为 $1$；流水线转发达到它，因此容量为 $1$。一般信道中内外界有间隙时，只能报告界。

CF 例子中，两份观察不同的概率为 $3/8$，故无损发送中继观察所需条件熵为 $h_2(3/8)\approx 0.954434<1$，确实能通过正交链。终点联合两份观察的可达率为

$$1+h_2(3/8)-2h_2(1/4)\approx 0.331878.$$

完整 DF 受中继单份观察约束，第一项为 $1-h_2(1/4)\approx 0.188722$。CF 不要求中继认出消息，而是传一份终点能利用的观察，所以可突破这项策略瓶颈。它仍须接受网络的真实外界，并不因超过 DF 就已证明一般容量公式。

验收标准 ​

• Slepian–Wolf 同时检查三条界，并把总率收益归于联合译码
• 蝴蝶解码分别使用各终点真实拥有的符号
• 中继式中的输入分布、因果性、条件变量与优化顺序完整
• 只在可达内界与外界吻合时给容量等号