噪声信道能传递什么?
精简的信源编码可以减少传送前的平均比特数,却不能自行阻止信道改变比特。本节先计算一次使用信道时输出透露多少输入信息,再研究一个小型纠错码。
定义 7.1.1
(二元对称信道)
设输入 ,噪声比特 与 独立,输出为 ,其中 是模二加法。假设 ,。这是二元对称信道:无论输入为何,比特都以概率 翻转。令 ;输入分布是与信道参数 分开选择的。
我们要计算的量都是有限随机变量的熵。
定义 7.1.2
(二元熵与互信息)
对 ,定义二元熵
并按连续性约定 。对有限随机变量,,而 。本节对数都以二为底,单位为比特。概率为零的输入值对条件熵之和没有贡献。
一次使用的计算
定理 7.1.3
(一次使用的最大互信息)
对上述信道,
对每个 ,取 可达到上界。
证明
(输出分布、条件熵与 的峰值)
输出为一恰好发生于 或 。由独立性,
因此 是公式中的第一项熵。给定任一输入后,输出分布只是 的可能重新标记,所以 。对 ,, 先增至 再递减。由端点的连续值可知 。取 使输出均匀,于是达到上界。
证明透视
信道和输入各司其职
与 的独立性用了两次:一次计算输出分布,一次说明给定 时的条件输出分布就是(可能重新标记的)噪声分布。关键一步是 与 无关,所以对输入最大化 就化为只最大化 。论证之所以能闭合,是因为无论 为何, 时 都等于 ;当 ,每个 都给出 ,上界 自然达到。输出均匀本身不代表它透露输入;还必须减去条件不确定性。
这是一次使用的互信息最大值。要把它与长分组的可靠传输速率联系起来,需要另行证明带有相应假设的编码定理;本节没有证明该定理。互信息是联合分布的平均性质,并不表示单个观察到的比特有小数个可能取值。
端点与数值例子
时 ; 时 。两者每次使用的最大互信息都是一比特,因为已知的确定翻转可逆。 时,输出与输入独立,任何 都有 。因此 的图像关于 对称,并非在整个 上单调递减。
例题 7.1.4
(四分之一的比特翻转)
若 且输入均匀,输出也均匀, 比特,因为 。若 ,输入为常数,而 ,故互信息为零。输出的随机性本身并不是关于常数输入的信息。
例题 7.1.5
(端点 :每个比特都翻转)
此时 ,故 ,。给定 后输出完全确定,所以 。因此 ,在 时为一比特,与 一致。接收者只需把每个比特取反。
常见错误
(互信息并非随翻转概率单调变化)
人们容易把 当作信道有多差的度量。但 ,所以 的最大值 比特与 相同。最差的情形是 ,而不是 。
三次使用的重复码
把消息比特 发送三次,即 ,并按多数表决译码。
命题 7.1.6
(多数表决译码的错误概率)
假设三个噪声比特相互独立,它们组成的向量与 独立,且各自翻转概率为 。则三次重复码的多数表决译码出错的概率为
证明
(计数重量为二或三的噪声图样)
恰好至少两位翻转时译码出错。由独立性,无论 为何,每个重量为 的噪声图样的概率都是 。三种两位翻转和一种三位翻转给出 。
时错误概率为 ,低于单次发送的 。当 时严格更小,因为 ; 时两者都是 。当 ,原来的多数表决可能更差;若信道参数已知,先把收到的比特取反,便可把有效翻转概率变为 。
常见错误
(在不同传输率下比较错误概率)
重复码每个消息比特使用信道三次。它较低的错误概率因此并不是与每比特只发一次在相同传输率下的比较,本身也不说明编码能多接近一次使用的值 。
例题 7.1.7
( 时的多数表决译码)
若不利用已知参数,错误概率为 ,比单次发送的错误 更差。若先把每个收到的比特取反,便得到翻转概率为 的信道,多数表决译码的错误概率变成 。
反例模式
边缘概率相同不代表错误独立
假设三个噪声比特都等于同一个翻转概率为 的伯努利(Bernoulli)变量。每个比特仍以概率 翻转,但只会全部翻转或全部不翻转。多数表决的错误概率因此是 ,可能与 不同:例如 时前者为 ,后者为 。上面的乘积计算用到了各次使用之间的独立性。
习题
快速检查
(对 和任意 ,计算 及 。)
解答 · 答案
输出均匀:。 和 都是一比特,所以 。
快速检查
(对 、,写出 的精确表达式。)
解答 · 答案
输出为一的概率是 ,故 。
快速检查
(计算 时三次重复码的错误概率,并与 比较。)
解答 · 答案
错误概率为 。
快速检查
(为什么 时每个比特都翻转,互信息仍可以是正数?)
解答 · 答案
接收者可以把这个已知的确定翻转反过来。均匀输入与其取反后的输出互相确定,每次使用有一比特互信息。
延伸阅读
麻省理工开放课程,信息论第八讲 讨论二元对称信道及互信息与信道编码的关系;后者超出本节的一次使用证明。