信息论进阶 II · 信道编码、有限译码与随机码本

1. 一个码需要五项定义

设有限输入字母表为 \(\mathcal X\)、输出字母表为 \(\mathcal Y\)，离散无记忆信道由转移概率 \(W(y\mid x)\) 给出。独立使用 \(n\) 次意味着

消息 \(J\) 在 \(\{0,\ldots,M-1\}\) 上均匀。编码器为 \(f(j)=x^n(j)\)；码本是一列按消息标签编号的词。不同标签偶尔对应同一个词，仍然是两个需要区分的消息，不能在计算前把重复词去重。

译码器观察 \(Y^n\) 后输出 \(\widehat J\)，也可以输出擦除标记。码率定义为

当 \(M\) 不是 2 的整数幂时，这仍是合法的数学码率；它不表示每次恰好承载整数个二元位。

令 \(e_j=P(\widehat J\ne j\mid J=j)\)。需要区分

前者是平均块错误率，后者要求保护最难传的消息。若 \(M=2^k\) 并已固定每个标签的 \(k\) 位二元表示，还可定义平均比特错误率

一次块错误可能只错一位，也可能错多位，因此 \(P_b\) 不等于 \(P_e\)。本实验仅在标签确有固定二元表示且 \(k>0\) 时报告 \(P_b\)。这些指标与随机化译码的定义可参阅 MIT 6.441 第 14 章。

2. 最大似然：先看信道，再决定“距离近”好不好

固定收到 \(y^n\)，最大后验译码选择使 \(P(J=j\mid Y^n=y^n)\) 最大的标签。均匀消息先验下，由 Bayes 公式，它等价于最大化

这就是最大似然（ML）译码。并列最优标签可以按固定规则选择，也可以均匀随机选择；对当前均匀先验，两者给出相同的最优平均正确率，但逐消息错误和最大错误可能不同。

二元对称信道 BSC\((p)\) 的每位以概率 \(p\) 翻转，完整参数域为 \(0\leq p\leq1\)。若接收词与码字相距 \(d\) 位，

当 \(0\lt p\lt 1/2\) 时，似然随距离递减，ML 是最近邻；当 \(1/2\lt p\lt 1\) 时，似然随距离递增，ML 是最远邻。后一种信道也可以先把每个接收位翻转，再按 BSC\((1-p)\) 译码。

\(p=0\) 是无噪声，\(p=1\) 是确定性翻转，二者都能保留全部输入信息。\(p=1/2\) 时所有接收词与输入独立，任何译码器的最优平均正确率都是 \(1/M\)，即 \(P_e=1-1/M\)。这与消息是否用了重复码无关。

本实验同时提供“ML”“最近邻”和“总猜标签 0”。它不会把 \(p>1/2\) 偷改成 \(1/2\)，也不会把低于容量自动当作译码正确的理由。

3. 完整枚举：平局和混淆矩阵都不能省

用 \(D(j\mid y)\) 表示收到词 \(y\) 后输出标签 \(j\) 的概率。它可以是确定的 0 或 1，也可以是平局均分得到的分数。于是完整混淆矩阵是

每行总和为 1，且

实验直接累加错误项，不先计算一个接近 1 的成功概率再做相减，避免把微小但非零的错误消掉。对每个接收词，它保存全部似然、并列赢家、实际分配和消息后验。

两个相反的重复码字 \(0^n,1^n\)，在最近邻及均匀平局下有

偶数长度不能靠把 \(n\) 自动加一来处理。固定优先某个标签的平局规则会改变两个消息各自的错误；平均值仍可与上式核对。若使用 ML 且 \(p>1/2\)，上式应使用 \(1-p\)。

码本的最小 Hamming 距离 \(d_{\min}\) 可以给几何保证：不同码字、最近邻译码时，少于 \(d_{\min}/2\) 位翻转不可能把接收词送进另一码字更近的区域。证明只需三角不等式

距离保证只覆盖指定错误数，不等于完整误码率。重复码字导致 \(d_{\min}=0\)；单消息码本则没有“码字对的最小距离”，实验记为不适用。

4. 联合典型性：约束的是三项自信息

选择输入分布 \(P_X\)，与信道共同诱导 \(P_{XY}(x,y)=P_X(x)W(y\mid x)\) 及输出边缘 \(P_Y\)。定义弱联合典型集，要求正概率序列对同时满足

这些是相对于真实分布的负对数似然平均，不是把经验分布的熵算出来后只比较三个数字。经验分布接近真实分布是另一种常用典型性定义，需要另外写出条件。

对真实 IID 配对，三项分别由 AEP 收敛；再用并集界，真配对不在集合中的概率 \(\delta_n\) 趋零。集合基数由每个成员的联合概率下界给出

现在改抽相互独立且边缘正确的 \(\widetilde X^n\) 和 \(Y^n\)。在集合内，两边缘概率各有上界，所以

这里的互信息描述真配对与独立假配对的可区分程度。三个松弛量来自三个明确的不等式，不能在有限数值例子里凭空删除。

5. 随机编码：平均对谁取，存在什么码

固定输入分布，记 \(I=I(X;Y)\)。选 \(R\lt I\)，并取 \(\varepsilon>0\) 使 \(R\lt I-3\varepsilon\)。令整数消息位数 \(k_n=\lfloor nR\rfloor\)、消息数 \(M_n=2^{k_n}\)。

独立生成每个码字 \(X^n(j)\sim P_X^n\)。收到 \(y^n\) 后，若恰有一个消息的码字与之联合典型，就输出它；没有或有多个则报告错误。随机码本中出现重复词并不被排除，它们造成的标签歧义也必须计入错误。

对消息 0，若真配对在集合内，且没有其他码字与输出形成典型配对，则译码成功。因此

对随机码本取期望时，未发送码字独立于本次输出，故

每个标签的生成方式相同，所以同样的上界适用于对均匀消息求平均后的码本错误率 \(\mathbb E_{\mathcal C}P_e(\mathcal C)\)。于是至少存在一个具体码本，其平均错误不超过这个平均上界。

并集界不要求错误事件独立。独立性用于识别一个未发送码字与输出的分布；把多个事件概率相加，是另一件事。证明也没有承诺每个随机抽到的码本都达到上界。

对有限字母表，互信息关于输入分布连续，输入概率单纯形紧，故

可取得。任取 \(R\lt C\)，选择使 \(I>R\) 的输入分布，上面的构造就证明可达性。阈值式随机编码的另一种完整推导见 MIT 6.441 第 15.2 节。

6. 删去坏消息：平均小怎样变成最大也小

假设已找到一个 \(M\) 消息码本，平均错误不超过 \(\eta\)。错误大于 \(2\eta\) 的消息不能超过一半；否则所有消息错误的平均会超过 \(\eta\)。

保留至少 \(M/2\) 个好消息。对保留标签继续使用原译码规则；如果原译码器输出已删除标签，就改指向某个保留标签。原本正确的保留消息不会因此变错，所以新码的

因此，当 \(\eta_n\to0\)，最大错误也趋零，码率损失至多 \(1/n\)。这一步说明“平均错误版本”和“最大错误版本”的容量一致；它不是说一个未经删选的有限码本本来就均匀保护每个消息。

如果目标码率恰为给定 \(R\lt C\)，可以先以严格介于 \(R\) 与 \(C\) 的码率构造，再做删选，让最后码率仍不少于 \(R\)。这样处理量词，才能把整数取整和删半损失放进同一个证明。

7. 有限真假配对账本：别让小指数遮住大尾项

对 BSC\((p)\) 使用均匀输入，则 \(H(X)=H(Y)=1\)、\(H(X,Y)=1+H_2(p)\)、\(C=1-H_2(p)\)。两边缘的每符号自信息恒等于 1，联合典型条件只剩

真实配对的距离 \(D\) 服从 Binomial\((n,p)\)；独立均匀假配对的距离服从 Binomial\((n,1/2)\)。因此，对当前接受的距离集合 \(S\)，可以完整计算

这两个概率具有不同的采样分布，不能把一张直方图当作两者。随机编码的有限平均错误上界是

实验同时显示原始和以及截到 1 的概率上界；原始和大于 1 时，只说明这份上界无用。它不会把截断后的 1 仍标成未经截断的指数表达式。

例如 \(n=500,p=0.1,M=2^{200},\varepsilon=0.02\)，真配对尾概率约为 \(0.601976557804\)。只写假配对的指数项很小，不能推出总错误很小。这个结果也不意味着所有该码率的码都错六成：当前典型带和译码分析可能过于保守，ML 译码可以更好。

均匀 BSC 还可以得到比一般三松弛量更紧的指数：因为两边缘自信息没有偏差，集合内的信息密度至少为 \(n(C-\varepsilon)\)，所以 \(\alpha\leq2^{-n(C-\varepsilon)}\)。这是该对称设置的专门界，不能无说明地替换一般证明中的 \(3\varepsilon\)。

为免把浮点对数判界冒充严格区间证书，实验另给出一个完全有理数的核对。对已选集合中每个正概率距离，定义

于是

这是针对实际已选集合的精确分数界。空接受集时，假接受率与这个上界均为零，但真配对尾概率为 1。

8. 逆定理：无记忆给不等式，不自动给等号

消息均匀时 \(H(J)=\log_2M\)。设 \(E=\mathbf1_{\{J\ne\widehat J\}}\)。给定估计与是否出错，错误情况下原消息最多有 \(M-1\) 个可能值，因而

这是 Fano 不等式的一种用法。数据处理链

给出 \(I(J;\widehat J)\leq I(X^n;Y^n)\)。即使码字坐标相互相关，无记忆性仍然保证

第一项用熵的次可加性，第二项的等号来自给定完整输入后的条件独立。不能把有相关输入的一般情形写成互信息自动逐次相加。

将这些式子合并，对于 \(M>1\)，

有限 \(n\) 时右端可能为负；它是一个无用的下界，不是负错误率。若码率趋于严格大于 \(C\) 的 \(R\)，则错误率不能趋零。这是弱逆定理。它尚未证明错误率趋于 1；后者需要强逆定理的额外论证。

实验还用实际码本的 \(I(J;Y^n)\) 给 Fano 下界，再与用 \(nC\) 得到的下界并列。这样可以看出：具体码本损失的信息，与信道本身允许的最大信息量，也不是同一个数。

9. 枚举随机码本：平均之下确实有具体成员

现在只生成两个码字，每位独立以概率 \(q\) 取 1，两个码字也独立。长度至多 4 时，可以列出全部 \(2^{2n}\) 个有序码本，并按其生成概率加权，而不依赖随机模拟。

若两码字相距 \(d\) 位，相同的位置不提供区分信息。不同的 \(d\) 位构成一个重复判别问题。在 ML 译码下，其平均错误恰好是使用翻转率 \(\min(p,1-p)\) 的长度 \(d\) 重复码误差，偶数 \(d\) 包括平局；\(d=0\) 时两消息完全重合，误差为 \(1/2\)。

两个独立 Bernoulli\((q)\) 位不同的概率是 \(2q(1-q)\)，所以码字距离服从

由此得到第二种独立核对：

例如 \(n=3,p=0.1,q=1/2\)，四种距离的概率为 \((1,3,3,1)/8\)，相应错误为 \(0.5,0.1,0.1,0.028\)，平均得到

相反码字的错误为 0.028，重复码字的错误为 0.5；平均值既不等于最好，也不等于每个成员。若信道完全无噪声，错误仍可能来自随机码字碰撞：在此均匀例子中，碰撞概率 \(1/8\)，平均错误为 \(1/16\)。

一般碰撞概率是

\(q=0\) 或 1 时只会抽到一种词，容量虽可能很大，这个随机造码方案却只能产生无法区分的两个消息。因此实验报告的是“有正生成概率的码本中，最好和最坏分别怎样”，不把零概率抽到的成员当作存在性结论的见证。

10. 高斯信道：单位和功率约束必须跟着公式

实值 AWGN 信道为 \(Y=X+Z\)，其中 \(Z\sim N(0,N)\)、\(N>0\)，且噪声独立于输入。以比特计的微分熵满足

在 \(\mathbb E X^2\leq P\) 下，\(\operatorname{Var}(Y)\leq P+N\)。给定方差，高斯分布最大化微分熵，所以

零均值高斯输入 \(X\sim N(0,P)\) 达到这个单次信息上界。要把它升级为满足逐码字功率限制的编码定理，还需处理生成码字的功率集中与筛选，不能仅凭“选高斯输入”一句话就跳过编码可达性。

通常的实值容量为

若一次使用是一个复值符号，且 \(P=\mathbb E|X|^2\)、\(N=\mathbb E|Z|^2\)，相应圆对称复高斯模型给 \(C_{\mathbb C}=\log_2(1+P/N)\)。两者统计的是不同维数，不能把前因子当作相互冲突的结论。

自然对数得到 nat，转换成比特需要除以 \(\ln2\)。以每秒计还需明确带宽、实/复自由度和噪声功率的约定。峰值幅度约束也不是平均平方功率约束，不能沿用同一个高斯最优输入。定义与证明范围见 MIT 6.441 第 17.1 与 17.3.1 节。

11. 四道完整练习：把容易混用的结论拆开

练习一：多重复一位，平均错误为什么没变？

对码本 0000、1111 经过 BSC\((0.1)\)，分别采用均匀平局和总优先标签 0 的最近邻规则。求平均错误及最大消息错误，并与三位重复码比较。

练习二：一个有限并集上界，为什么不等于ML误码？

取 \(n=3,p=0.1\)、均匀输入、两个随机码字、联合典型带宽 \(\varepsilon=0.5\)。求接受的距离、真尾概率、假接受概率和并集上界。

练习三：Fano给的是下界，还是精确错误？

八个消息均匀，某观测 \(Y\) 满足 \(H(J\mid Y)=2\) 比特。对任意基于 \(Y\) 的估计，给出一个直接可算的错误下界。

练习四：功率翻倍为何不总多半比特？

实值 AWGN 当前信噪比为 \(s>0\)。求功率翻倍后的容量增量及高信噪比极限，写明单位。

12. 从存在性走向构造：哪些问题还在后面

随机编码证明回答“存在什么”，完整枚举回答“这个有限对象怎样”，高效算法回答“能否在预算内实现”。三者可以互相指引，但不能用其中一项替代另外两项。

有限块长分析需要保留目标错误、整数消息数以及信息密度的波动；强逆定理研究高于容量时错误是否趋于 1；有输入成本、反馈或记忆的信道还要重新核对模型条件。本课的类型与短码实验提供可复核的起点，没有实现一般信道的容量最优编码器。

构造性方向中，Arıkan 的极化码原始结果给出二元输入离散无记忆信道的对称容量可达码族，以及逐次消除编解码的 \(O(N\log N)\) 复杂度。对称容量指均匀输入的互信息；在对称信道上它等于容量，在一般非对称信道上不能直接画等号。准确范围见 Channel polarization 原始论文。

学习下一讲率失真之前，可以用一张账本自检：消息数和码率是否一致，译码平局是否明确，概率总和是否为 1，图上的错误是平均还是最大，显示的是实际值还是上界，渐近证明有没有保留尾项。能逐一回答，才算把容量公式接回了一个可运行的通信问题。