反馈下的零错误容量

形式陈述

设有限无记忆信道 $W(y\mid x)$ 具有无噪、即时、免费的输出反馈：第 $t$ 次输入可以是消息 $m$ 与过去输出 $y^{t-1}$ 的函数 $x_t=e_t(m,y^{t-1})$ 。接收端在固定总次数 $n$ 后必须对每个可能输出轨迹正确译码。

与无反馈零错误容量不同，这里需要保留每个输出的相容输入集合

E_y=\{x:W(y\mid x)>0\}.

这些集合组成支持超图。定义分数打包数

A^*(W)=\max\left\{\sum_xw_x:w_x\ge0,\ \sum_{x\in E_y}w_x\le1\quad\forall y\right\}.

由有限维 LP 强对偶，其对偶是选择输出权重 $v_y\ge0$ ，使每个输入被至少一单位权重覆盖：

A^*(W)=\min\left\{\sum_yv_y:\sum_{y:x\in E_y}v_y\ge1\quad\forall x\right\}. \tag{1}

Shannon 反馈零错误定理为

C_{0F}(W)= \begin{cases} 0,&G_W\text{ 是完全图},\\ \log_2A^*(W),&G_W\text{ 不是完全图}. \end{cases} \tag{2}

第二种情况等价于无反馈零错误容量为正。这个例外不能删掉：完全图的支持超图仍可能有 $A^*>1$ 。[1,2]

本页使用固定最坏总块长，不把随机停止时间的期望长度当成分母。输出是否可出现由转移条件概率的正支持决定，正概率的具体大小不进入式 (2)。

直觉

没有反馈时，每条消息事先对应一整串输入。反馈让发送端也知道接收端目前看到了什么，因此双方能同步维护“仍有可能的消息集合”，在下一次使用前重新分配这些候选。

分数打包告诉我们怎样把候选消息按比例分配给输入，使任何可能输出都只留下至多约 $1/A^*$ 的候选。整数分配会留下一个常数级尾巴；如果存在一对完全可区分的输入，就能再用常数次信道使用把这小尾巴精确区分完。

收到输出后双方同步缩小候选集，再按同一分数权重重新分配；五边形例中候选规模按约五分之二收缩，最后用可区分输入对收尾。

例子与边界

五边形从√5提高到5/2

令输入 $i$ 可能输出 $i$ 或 $i+1$ ，下标模5。每个输出 $y$ 的相容输入为 $E_y=\{y-1,y\}$ 。取每个 $w_x=1/2$ ，每个约束恰好等于1，总权重 $5/2$ 。

反向把五个约束相加，每个 $w_x$ 被数两次，得 $2\sum_xw_x\le5$ ，所以 $A^*=5/2$ 。信道本来有两个支持不交的输入，因此

C_{0F}=\log_2(5/2)\approx1.321928,

高于无反馈的 $\log_2\sqrt5\approx1.160964$ 。

例如当前有25条候选消息，把它们均分到五个输入，每个5条。不论输出哪个 $y$ ，只留下对应两个输入下的10条候选。因为发送端得到反馈，下一轮可以把这10条重新均分，再缩到4条。没有反馈时，发送端不能根据实际输出重新安排这张候选分配表。

为什么完全图仍无法起步

取三个输入 $a,b,c$ ，输出分别标成 $ab,bc,ca$ ，一个输入可产生包含自己的两个输出。混淆图为 $K_3$ ，但三个权重都取 $1/2$ 可得到 $A^*=3/2$ 。

仍然不能用任何有限次数传两条零错误消息。给定一段共同输出历史，两个候选消息的下一输入无论是什么，都有共同可能输出；选择该输出，就让两条消息继续同时存活。如此递归到最后，它们仍不能区分。因此 $C_{0F}=0$ ，不是 $\log_2(3/2)$ 。

二元对称信道 $0<p<1$ 同样有完全混淆图，反馈不能创造第一对可区分消息。那里的每个输出超边都是全部输入，恰好 $A^*=1$ ；三角形例子则进一步说明式 (2) 的分支条件确实不可省。

推论与应用

对偶权重给任何反馈策略的上界

固定一份零错误反馈策略。某一输出历史之后，设还有 $M$ 条候选消息；它们按下一次输入分成各组，大小为 $M_x$ ，总和为 $M$ 。若下一输出为 $y$ ，剩余数量为

M_y=\sum_{x\in E_y}M_x.

用式 (1) 的最优对偶权重，

\sum_yv_yM_y =\sum_xM_x\sum_{y:x\in E_y}v_y \ge M.

因为 $\sum_yv_y=A^*$ ，至少存在一个实际可能输出，使 $M_y\ge M/A^*$ 。沿每一轮都选这样的输出， $n$ 次后至少还留 $M_0/(A^*)^n$ 个候选。零错误译码要求末尾至多一个，所以

M_0\le(A^*)^n, \qquad C_{0F}\le\log_2A^*.

这只是选择一条正概率输出轨迹来检验最坏情况，并不把原信道改成另一个随机模型。

分数比例、整数舍入与常数收尾

现在假设 $G_W$ 不完全，取最优打包 $w_x$ ，令 $A=A^*>1$ 、 $p_x=w_x/A$ 、 $d=|\mathcal X|$ 。于是对每个输出， $\sum_{x\in E_y}p_x\le1/A$ 。

当前候选数为 $M$ 时，双方按约定次序把候选分配给输入，令各组大小为 $\lfloor Mp_x\rfloor$ 或 $\lceil Mp_x\rceil$ ，且总和仍为 $M$ 。这种分配可由先取下整、再补剩余名额实现。于是任何下一输出保留的候选数满足

M'\le\frac MA+d.

反馈保证双方知道相同的候选集合，因此下一轮能重新使用这份分配。连续 $n$ 次后，

M_n\le A^{-n}M_0+d\sum_{j=0}^{n-1}A^{-j} \le A^{-n}M_0+\frac d{1-1/A}. \tag{3}

取 $M_0=\lfloor A^n\rfloor$ ，则剩余数至多常数

K=\left\lceil1+\frac d{1-1/A}\right\rceil.

由于图不完全，存在两个输出支持不交的输入，可以每次零错误传一位。双方已知道同一个候选列表，只需再发 $\lceil\log_2K\rceil$ 位确定其中哪条是真消息；这是独立于 $n$ 的最坏长度开销。总率趋于 $\log_2A$ ，证明可达性。

完全图的分数收缩也可能把大列表缩到常数，却没有这最后的零错误二元信道。这正是例外出现的机制。

支持超图不能只换成混淆图

考虑混淆图 $K_3\cup K_1$ 。若三角形由三个两点输出超边产生，另一个孤立输入有专属输出，则 $A^*=3/2+1=5/2$ 。若三角形改由一个包含全部三点的输出超边产生，仍是同一混淆图，但 $A^*=1+1=2$ 。

两图都有独立输入对，所以反馈容量分别为 $\log_2(5/2)$ 与1。只知道两两混淆关系无法区分它们。分数团覆盖用的是图的所有团，而式 (1) 只使用信道真实输出的超边；五边形中两者相同，是该支持结构的特性。

参考资料

[1] Claude E. Shannon, The Zero Error Capacity of a Noisy Channel, 1956，反馈零错误容量的原始结果。
[2] Runyao Duan, Simone Severini and Andreas Winter, On zero-error communication via quantum channels in the presence of noiseless feedback, 2016作者版，§I，式 (3)–(4) 明确重述经典信道的完全图例外与支持二部图分数打包。本页只使用经典部分，并完整展开计数上界和候选收缩构造。

形式陈述 ​

五边形从√5提高到5/2 ​

为什么完全图仍无法起步 ​

对偶权重给任何反馈策略的上界 ​

分数比例、整数舍入与常数收尾 ​

支持超图不能只换成混淆图 ​