二元对称信道 | Codeboy's Blog

形式陈述

二元对称信道是输入、输出字母表均为 $\{0,1\}$ 的离散无记忆信道； $\operatorname{BSC}(p)$ 的参数为 $0\le p\le1$ 。它每次接收一个输入比特 $X$ ，以概率 $p$ 将它翻转，以概率 $1-p$ 保持，输出比特 $Y$ 。等价表示为

Y=X\oplus Z, \qquad Z\sim\operatorname{Bernoulli}(p),\quad Z\perp X,

其中 $\oplus$ 是异或， $Z$ 是决定是否翻转的Bernoulli 随机变量。单次转移概率是

输入	输出 0	输出 1
0	$1-p$	$p$
1	$p$	$1-p$

“对称”指两个方向 $0\to1$ 和 $1\to0$ 的翻转概率相同，不要求实际发送的 $0$ 、 $1$ 一样多。

在本页的无反馈编码模型中，多次使用无记忆 BSC 时，噪声 $Z_1,\ldots,Z_n$ 相互独立，并独立于整个输入向量。因而

\Pr(Y^n=y^n\mid X^n=x^n) =\prod_{i=1}^n\Pr(Y_i=y_i\mid X_i=x_i).

这里是给定输入后的转移概率分解。编码器生成的输入比特可能相关，不能据此断言不加条件的输出比特也相互独立。若允许反馈，每个新的 $Z_i$ 仍独立于过去历史和当前输入，但后续输入可以依赖它经 $Y_i$ 暴露的信息；此时不再要求 $Z^n$ 独立于整个 $X^n$ ，应使用 DMC 页的因果转移律。下文重复码与乘积似然均按无反馈模型计算。

直觉

发送 0 时，接收端见到 1，无法直接知道这是原本发送了 1，还是 0 被噪声翻转。纠错编码让不同合法消息对应相距较远的比特串；接收端利用整串结构，而不是仅凭单个比特，判断最可能发送了哪个码字。

噪声的关键不只是翻转频率，还包括翻转是否可预测。 $p=1$ 表示每一位都确定翻转，接收端反转一次即可恢复； $p=1/2$ 才使输出完全不提供输入信息。

例子与边界

三重重复码：用码率交换可靠性

将一个信息比特 $0$ 编成 000， $1$ 编成 111，接收后取多数。比如 000 变为 010，虽然一位出错，多数仍为 $0$ 。当且仅当至少两位翻转时，译码会出错，所以

P_{\mathrm{err}}=3p^2(1-p)+p^3.

取 $p=0.1$ ，恰好一位翻转的概率为 $3(0.1)(0.9)^2=0.243$ ，这些情况都能纠正；译码错误概率则为 $0.028$ ，小于直接发送一个信息比特时的 $0.1$ 。代价是每三个信道使用只传递一个信息比特，码率为 $1/3$ 。

把发送消息固定为 $U=0$ ，八种噪声串也就是八种接收串。逐项列出可见，错误事件由多数判决决定，并不是“出现过噪声”：

噪声串 / 接收串	概率（ $p=1/10$ ）	多数输出	消息是否错误
000	$729/1000$	0	否
001	$81/1000$	0	否
010	$81/1000$	0	否
100	$81/1000$	0	否
011	$9/1000$	1	是
101	$9/1000$	1	是
110	$9/1000$	1	是
111	$1/1000$	1	是

发送 $U=1$ 时接收串逐位取补，错误概率完全相同。因此按信道码的定义，平均错误与最大错误都等于 $(3\cdot9+1)/1000=0.028$ 。这里只有一个消息比特，所以消息块错误也就是该比特的译码错误。恰好一位翻转的概率是 $243/1000$ ，至少一位翻转的概率是 $1-0.9^3=271/1000$ ，两者都不等于译码错误。

增长重复次数究竟保证什么

把同一个比特重复奇数 $n$ 次，多数译码错误为

P_e^{(n)}=\sum_{j=(n+1)/2}^{n}\binom njp^j(1-p)^{n-j}.

若 $p<1/2$ ，大数定律使翻转比例趋于 $p$ ，越过 $1/2$ 的概率趋零。不过消息数始终只有 $2$ ，码率 $R_n=1/n$ 也趋零。它没有证明固定正码率下的可靠通信。反过来，把固定三重码反复用于很多消息比特，虽然码率保持 $1/3$ ，至少一个消息比特译错的概率却会增长；完整块错误计算见编码定理。

小错误与零错误的区别

对 $0<p<1$ ，任何输入块到任何输出块的转移概率均为正。若至少有两条消息，对同一个接收串，译码器至多判对其中一条；另一条消息在这个正概率事件上必错。因此有限块平均错误和最大错误都不能严格为零，要求绝不出错时的渐近容量也为零。BSC $(0.1)$ 的 Shannon 容量却为正，因为它允许错误随块长趋零。 $p=0$ 或 $1$ 是可逆确定信道，这时零错误容量与 Shannon 容量均为 $1$ 。

哪些码字更可能

若发送码字 $x$ 、收到 $y$ ，二者的 Hamming 距离为 $d$ ，则

\Pr(y\mid x)=p^d(1-p)^{n-d}.

当 $0<p<1/2$ 时，距离越小，这个似然越大。因此最大似然译码等价于寻找与接收串 Hamming 距离最近的合法码字。若要做后验概率最大的判决，非均匀消息先验还需要计入，不能仅比较似然。

擦除信道会明确标记“这一位不知道”，BSC 则给出一个可能错误但不带错误标记的比特。成串爆发的相关错误也不满足独立噪声假设；把接收信号硬判决为 $0/1$ 还可能丢失原来的置信度。这些都是建模对象的区别。

推论与应用

容量为什么是 $1-h_2(p)$

定义二元熵

h_2(p)=-p\log_2p-(1-p)\log_2(1-p),

并按连续延拓令 $0\log_2 0=0$ 。对任意输入分布，互信息满足

I(X;Y)=H(Y)-H(Y\mid X)=H(Y)-h_2(p)\le1-h_2(p).

条件熵等于 $h_2(p)$ ，因为给定输入后，只剩“翻转还是不翻转”的随机性。输出只有两种值，其熵至多为 $1$ 比特。再令输入均匀，即 $\Pr(X=0)=\Pr(X=1)=1/2$ ，对称性使输出也均匀，上界便能取到。因此信道容量为

C=\max_{P_X}I(X;Y)=1-h_2(p) \quad\text{比特/次信道使用}.

$p=0$ 或 $p=1$ 时容量都是 $1$ ； $p=1/2$ 时容量为 $0$ 。若 $p>1/2$ ，把输出再翻转一次就得到 $\operatorname{BSC}(1-p)$ ，容量不变。不能仅凭“错误率超过一半”断言信息无法恢复。

当 $p=0.1$ 时，容量约为 $0.5310$ 比特/次，比三重重复码的码率 $1/3$ 更高。容量定理说明：对任何严格低于 $C$ 的固定码率，都能通过适当增长块长的编码，使整块消息的译码错误概率趋于零。它不是说某个有限长度编码从此绝不出错，也不是说每个原始比特天然只剩 $h_2(p)$ 位可删掉。

BSC 因而把离散无记忆信道、熵、互信息和纠错极限连在一起：转移概率描述单次噪声，码字结构处理多次噪声，容量刻画长块编码能达到的渐近边界。

参考资料

MIT 6.02, Coping with Bit Errors Using Error Correction Codes, 2011, §6.2，重复码与多数译码；上面的八事件表为直接枚举。
Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006，Chapter 7 “Channel Capacity”，二元对称信道与编码定理。
Claude E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, 1948, pp. 379–423, 623–656，无噪声与有噪声通信的基础理论。
Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning，作者公开预出版稿（2024-08-16），§17.2（二元对称信道编码）、§19.3（容量推导）。

形式陈述 ​

三重重复码：用码率交换可靠性 ​

增长重复次数究竟保证什么 ​

小错误与零错误的区别 ​

哪些码字更可能 ​

容量为什么是 1−h2(p) ​

反向链接