二用户多址信道容量区域

第一条约束可以理解为：即使先告诉接收者用户 2 的整条消息，输出关于用户 1 的信息仍然有限。第二条作对称检查。第三条则同时检查两条消息能否塞进共同输出；分别不超速，并不保证它们加起来不拥挤。

例如两个用户各发送一位 $0$ 或 $1$，接收端只看到整数和 $Y=X_1+X_2$。输出 $0$ 确定来自 $(0,0)$，输出 $2$ 确定来自 $(1,1)$，输出 $1$ 却可能来自 $(0,1)$ 或 $(1,0)$。给出另一人的输入后，自己的输入又可以唯一恢复。这正是单用户条件界较宽、联合总率界更紧的原因。

时间共享是一份大家都知道的日程。例如前一部分位置采用方案 A，后一部分采用方案 B，两人的消息分别拆成两段。总速率是两段速率的加权平均，整块错误至多是两段错误之和。日程帮助分配信道资源，却没有把一个发送者的私有消息交给另一个发送者。

整数二元加法信道的精确区域 ​

令 ${\mathcal{X}}_1={\mathcal{X}}_2=\{0,1\}$，$Y=X_1+X_2\in \{0,1,2\}$，这里不是模二相加。公平独立输入给出

给定 $X_2$，相加只是把 $X_1$ 的两个值平移，所以 $H(Y\mid X_2)=H(X_1)=1$。信道又是确定的，故

因此所有满足 $R_1\le 1$、$R_2\le 1$、$R_1+R_2\le 3/2$ 的非负速率对都在容量闭包内。要称它为精确区域，还要证明其他产品输入不能做得更好。

写 $p=\text{Pr}[X_1=1]$、$q=\text{Pr}[X_2=1]$，输出三概率为

令 $F(p,q)=H(a,b,c)$。正方形边界上有一位输入固定，输出至多取两个值，所以 $F\le 1$。内部有 $a,b,c>0$，直接求偏导并相减得到

由于 $b=p(1-q)+(1-p)q$，有 $b^2\ge 4ac$，对数严格为负。内部驻点因而必须满足 $p=q=t$。在这条对角线上，输入对的熵为 $2h_2(t)$；只有输出 $1$ 丢失一个公平的输入次序，其概率为 $2t(1-t)$，所以

其一阶导数在 $t=1/2$ 为零，二阶导数为

故唯一内部最大值在 $t=1/2$，值为 $3/2$，也超过边界最大值。任意产品输入的条件单用户互信息至多一个 bit，总互信息至多 $3/2$ bit。对每个 $Q=q$ 都有这些界，取平均仍成立，于是完整容量区域恰为

$(0.7,0.7)$ 位于内部；$(0.8,0.8)$ 虽逐用户未超一 bit，却被总率排除。两个斜边端点是 $(1,1/2)$ 与 $(1/2,1)$，中点是 $(3/4,3/4)$。它们属于渐近容量闭包，不表示存在一个固定块长的零错误码恰好达到这些速率。

改一个建模条件，计算就会变 ​

若输出改为 $Y=X_1\oplus X_2$，公平输入仍给出两个条件互信息各为 $1$，总输出熵却只有 $1$，因此总率上界变为 $R_1+R_2\le 1$。整数和留下三个结果，异或只留下两个结果，不能共用前一张容量图。

也不能先随意规定一个相关输入分布，再套容量公式。例如令 $(X_1,X_2)$ 仅在 $(0,0),(1,0),(1,1)$ 上各取概率 $1/3$，整数和就均匀分布于三个输出，熵为 ${\log }_{2}3>3/2$。这个分布不是产品分布。若用预先共享的 $Q$ 选择这三个确定输入对，输出虽无条件均匀，给定已知日程后却完全确定，故 $I(X_1,X_2;Y\mid Q)=0$；日程本身的随机性不能冒充两条独立消息的信息。

平均错误与最大错误 ​

这里控制的是对独立均匀消息对平均的块错误。若改为对每一对 $(m_1,m_2)$ 都要求错误小，便得到最大错误准则；一般多址信道的两个容量区域可能不同。

单用户证明会删掉错误率高的消息，留下一个大的好消息集合。多用户坏点位于消息对的矩形表中：删掉一小部分坏点后，剩余好点未必包含两组足够大的消息集合的笛卡尔积。分离编码器需要的正是这种乘积结构，因此不能直接移植单用户删码论证。上面的整数加法算例仅计算本页的平均错误容量，并未用来证明两类容量严格不同。

可达性：三种错误候选分别付账 ​

沿用单用户编码定理的阈值方法公理库有噪信道编码定理Noisy-channel coding theorem · Channel coding theorem低于离散无记忆信道容量的速率可实现任意小错误概率，而高于容量的速率不能可靠传输。。先固定产品输入 $P_1{P}_2$，按真实联合分布定义三种信息密度：

分母由固定输入分布和信道求和得到，例如 $P_{Y\mid X_2}(y\mid x_2)=\sum _{x_1}{P}_1(x_1)W(y\mid x_1,x_2)$。真实正概率三元组上分母与分子都正。码本支持内的候选若遇到零分母，分子也必为零；凡分子为零，都把该项信息密度记为 $-\mathrm{\infty }$。真实不可能出现的输出可任意规定译码。

分别独立抽取 $N_1$ 条第一用户码字和 $N_2$ 条第二用户码字，各坐标也独立。对每个消息对，块信息密度是相应单次量的和。收到 $y^n$ 后，只接受同时通过以下三道检验的唯一消息对：

没有唯一候选时输出固定消息对。只要真实对通过且没有错误对通过，就一定译对；这个充分条件给出错误事件的上界，未要求默认判决每次都错。

发送固定真实消息对后，将错误候选分成三个互不遗漏的类别：

第一行为什么成立？错误的第一用户码字独立于真实第二用户码字和输出。固定后两者，对任意正分母有

只对比值超过 $2^{{\log }_2{N}_1+\tau }$ 的项求和，其总概率至多 $2^{-{\log }_2{N}_1-\tau }$。再乘 $N_1-1$ 得第一行。第二行对称。第三行中两条错误码字相互独立且都独立于真实输出；对 $P_1^n{P}_2^n$ 求和、以 $P_Y^n$ 作分母，同样得到候选概率至多 $2^{-{\log }_2(N_1{N}_2)-\tau }$。不同错误候选之间不必独立，并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。仍可直接相加。

对随机码本和均匀消息平均，便得到有限块存在界

三种真实信息密度的均值正是区域中的三个互信息。若速率严格满足全部相关约束，取 $N_j=\lfloor 2^{n{R}_j}\rfloor$、$\tau =n\delta$，其中正数 $\delta$ 小于三种速率余量，由大数定律公理库强大数定律Law of large numbers · Strong law of large numbers · SLLN独立同分布且可积时，样本均值沿几乎每条无限样本路径收敛到共同期望。，每个未过阈值的概率都趋零。有限码本空间中必有一个确定码本不超过平均错误界，选出并固定它即可。

零速率用户只需一条消息；删除涉及该用户错误的空类别及相应不需要的检验。若两人均为零速率，直接输出唯一消息对。区域边界由速率内部逼近及闭包取得。

时间共享如何进入同一证明 ​

对于一般 $P_Q{P}_1(\cdot \mid Q)P_2(\cdot \mid Q)$，先按 $P_Q^n$ 抽一个日程 $q^n$，再给定它独立抽两份条件产品码本。三种信息密度的分母分别加入 $q_t$；上面的求和等式逐日程仍成立。

在日程和码本的总体随机试验中，真实 $(Q_t,X_{1t},X_{2t},Y_t)$ 独立同分布，均值就是带 $Q$ 的三个条件互信息。因此同一个大数定律论证仍成立。最后把日程与两份码本一起固定：两个编码器和接收者事先知道它，实际通信时无需共享随机币，也不传递 $Q$。这证明了定理所列整个条件产品区域的可达性。

逆定理：从整块消息回到单次使用 ​

任取一组确定分离编码器。由联合Fano 不等式公理库Fano 不等式Fano's inequality用估计错误概率上界条件熵，从而把信息不足转化为推断下界。，令

便有 $H(M_1,M_2\mid Y^n)\le n{ϵ}_n$。消息独立，所以

最后一个等号不要求编码器单射。给定 $M_2$ 后，输出分布只通过 $X_2^n=f_2(M_2)$ 依赖它，因为独立的 $M_1$ 仍按原分布产生 $X_1^n$；给定两条消息后，输出熵又只由两条码字决定。对这两个条件熵分别替换即可得到等号。

利用链式法则、去条件使熵不减及无记忆性，

相减得

交换两用户得到第二条；用 $H(Y^n)\le \sum _{t}H(Y_t)$ 得到总率约束

取与全部变量独立、在 $[n]$ 均匀的时间索引 $T$，令 $Q=T$、$X_j=X_{jT}$、$Y=Y_T$。每个固定时刻的两个输入是两条独立消息的确定函数，故 $X_1\perp X_2\mid Q$。于是上述三个平均恰好变成容量公式中的同一组三个条件互信息。

还需验证 ${ϵ}_n\to 0$，不能预先假定速率有界。总率 Fano 界先给出

当错误趋零时，总率因而有界，${ϵ}_n=1/n+P_e^{(n)}(R_{1n}+R_{2n})\to 0$。将每个速率分别降低 ${ϵ}_n$ 并截断于零，所得非负对满足两条单用户约束。若两个速率均超过 ${ϵ}_n$，总率减少两份余项，也满足总率约束；若只有第一条超过，新的总率就是第一条速率，而 $I(X_1;Y\mid X_2,Q)\le I(X_1,X_2;Y\mid Q)$，仍满足总率约束。另一情形对称，两条均不超过时得到零速率对。这样原速率到所列区域的距离趋零，闭包给出逆定理。

终点自测：复现三类候选的数目与各自分母；说明任意相关输入为何不合法；最后算出整数加法与异或的两个总率界。能把这三步连起来，就能区分独立编码、共同译码和资源共享各自承担的作用。