动机
二元对称信道具有足够的对称性,使得汉明(Hamming)距离与汉明球计数成为自然的工具。一般的信道则可能擦除某些符号,可能对某些符号对的混淆多于其他符号对,也可能有多个输入产生相同的输出分布。此时,单靠距离阈值已无法描述一个接收字作为某个候选输入之证据的说服力。
信息密度通过比较两个概率来度量这种证据:一是在某个候选输入下该输出的概率,二是在整体输入分布下该输出的概率。对于真实发送的符号对,其平均值趋近于互信息。对于不相关的竞争输入,一个简单的期望界使得大的取值不太可能出现。这两个事实合起来,就给出了每个有限无记忆信道的存在性编码定理。
证明随机地选取码本,以说明存在一个好的确定性码本。它并不提供快速编码器、实用译码器或强逆定理。我们还将证明必要的码率界,且不假设实际码字的各坐标相互独立;这一区别对几乎所有有结构的码都很重要。
定义
定义 3.4.1
(有限无记忆信道)
设 为非空有限输入字母表与输出字母表。信道是一个随机矩阵 ,且对每个输入 有 。其无记忆扩张的条件分布为
这表示在给定整个输入字的条件下各输出相互条件独立;它并不要求输入分布本身具有任何独立性。
定义 3.4.2
(信息密度)
对选定的输入分布 ,令 。所有对数均以二为底。在联合概率为正的符号对上,定义信息密度
对于满足 但 的候选符号对,规定其信息密度为负无穷。满足 的输出在基于 的随机试验中从不出现,译码器可以对其一律拒绝。在概率为正的真实发送符号对上,信息密度总是有限的。
定义 3.4.3
(码、错误准则与容量)
一个 次使用的码含有 个带编号的消息,一个把消息映到 的确定性编码器,以及一个输出消息编号的译码器(也可以报告失败)。平均错误概率是对均匀分布的消息与信道噪声取平均。最大错误概率是各消息条件错误概率中的最大值。码率为 。定义
该最大值存在: 在紧致的有限维概率单纯形上连续,其中约定 。熵、条件熵、散度、数据处理不等式与 Fano 不等式已在前面各单元中证明,此处按有限字母表的约定使用。
定理/命题
定理 3.4.4
(每个更小的码率都可达)
对每个 ,存在一列确定性码,其码率趋近于 ,且最大错误概率趋于零。只含一个消息的零码率码总是存在的,包括 的情形。我们不断言这些码的构造或译码具有任何效率保证。
定理 3.4.5
(不要求输入独立的弱逆定理)
对任意 、平均错误概率为 的 次使用码,有
因此,每个错误概率趋于零的码序列,其码率的上极限至多为 。这一界并不证明在每个更大的码率下错误概率都趋于一。
证明思路或证明
真实发送的符号对具有典型的信息密度
证明
(真实符号对的集中性)
选取 使 ,并选取 使 。从 中独立地生成 个码字,并保留其消息编号。当 足够大时至少有两个码字。这个临时的随机列表允许出现重复;重复的情形会被纳入错误分析,而不是被悄悄假定不存在。
当一个带编号的码字经 传输时,对随机列表取平均,其各坐标上的符号对相互独立,联合分布为 。分组信息密度是 个单坐标密度之和。这些加项的均值为 ,且方差 有限,因为它们在正概率下的支撑集是有限的。Chebyshev 不等式给出
这里利用码字的随机性是为了证明存在性。最终选定的固定码本,在均匀选取消息时,并不一定使其各坐标相互独立。
竞争字很少通过阈值
证明
(竞争字的似然比界)
译码时,取分组信息密度大于 的那个唯一编号;若没有这样的编号或有多个,则报告失败。对于与信道输出独立的竞争字 ,其分布为 ,而在对发送的随机字取平均后,输出的边缘分布为 。在输出的支撑集上定义非负似然比 。由独立性,
对每个概率为正的 ,条件概率为正的输出也具有正的 概率,这就说明了尽管信道矩阵可能有零元素,最后一个等号仍然成立。由 Markov 不等式得 。
固定一个被发送的消息编号。只有当其真实符号对未通过阈值,或某个竞争编号通过阈值时,才可能出错。并集界不要求各竞争事件相互独立。再对消息编号取平均,得到平均错误概率的期望至多为
它趋于零。若两个带编号的码字恰好相同,它们之间的冲突已包含在这些事件之中。
固定码本并剔除高错误概率的消息
证明
(剔除至最大错误)
随机系综是有限的,因此至少有一个确定性码本,其平均错误概率至多为 。在该码本中,至少有一半的消息其个别错误概率至多为 ;否则平均值将超过 。保留这些消息,舍弃其余的。当译码器原先的答案指向某个保留的消息时予以保留,指向其他任何消息时则改为失败。这不会把原先对保留消息的正确回答变成错误。
保留下来的码最大错误概率至多为 ,且至少含有 个消息。其码率与 至多相差 ,而 趋于 。因此最大错误概率趋于零,而渐近码率没有损失。当 足够大时,这一错误概率小于二分之一,这也排除了保留码字中出现重复:两个相同的发送字具有相同的输出分布,所以它们被正确识别的两个概率不可能都超过二分之一。
证明透视
三个概率空间与连接它们的阈值
三个概率空间各司其职,每个假设都只在其中一处起作用。真实符号对的估计是对随机码字与信道噪声取平均。此时各坐标对相互独立,分布为 ,所以无记忆性与乘积输入分布使分组信息密度成为 个独立项之和;Chebyshev 不等式只需要有限方差,而有限字母表正好提供这一点。
竞争字的界使用另一个与输出独立的随机字。关键的一步是:这种独立性使 恰好成立,所以 Markov 不等式给出 ,无须再知道信道的任何结构。阈值 是平衡两个估计的唯一参数:它低于真实符号对的典型密度,又高到使约 个竞争字仍然不能通过,这之所以可能,是因为 。只有在这些平均之后才选定一个确定性码本,剔除步骤再只对信道噪声界定错误。论证中没有任何地方声称最终码本的各坐标相互独立。
约束任意固定码所能携带的信息
证明
(弱逆定理)
现在考虑任意固定的编码器及其可能相关的输入字 。无记忆条件分布给出
第一个等式来自对每个输入字上乘积条件分布的熵取平均。不等式来自熵的链式法则以及条件不会增加熵这一事实。两式相减得 ,因为每个坐标都有某个输入分布,属于容量最大值所允许的范围。
令均匀分布的消息为 ,译码器的输出为 。马尔可夫(Markov)链 给出 。Fano 不等式给出 ,其中包括可能的失败输出。由于 ,把两个陈述合并便得到所述的逆定理。最大错误概率的保证同时也界住了平均错误概率,所以它无法规避这一限制。
例题详解
例题 3.4.6
(擦除信道与一个明确的存在性估计)
一个二元擦除信道以概率 显示输入,否则返回一个不同于输入符号的擦除符号,且每次使用相互独立。对任意输入分布,,所以 ,容量为每次使用 比特,在公平输入下达到。
对该公平输入,信息密度在被显示的符号上为一,在擦除上为零,故其方差为 。取目标码率 与 。证明给出,存在某个固定码本,其平均错误概率至多为 ,剔除后至多为其两倍。这一估计在小分组长度下较为粗糙,但它明确地趋于零。它并没有给出所承诺的码本,也没有建立高效的实现。
例题 3.4.7
(均匀输入不一定使容量最大)
设输入为 ,其中 总是产生输出零, 总是产生输出一。该信道是确定性的,所以互信息等于输出熵。均匀输入给出输出概率 ,互信息为 。改为以各二分之一的概率选取 ,且从不使用 。此时输出是公平的,互信息为一;因输出字母表是二元的,这就是容量。一个与另一输入行为完全相同的额外输入标签,并不会自动提供另一个可区分的消息符号。
例题 3.4.8
(无记忆的输出并不迫使输入独立)
取无噪声二元信道,其容量为一。选取一个公平比特 ,令每个输入坐标都等于 。每个输出坐标是公平的,所以 ,但整个输出字的熵仅为一,因为它要么全为零,要么全为一。因此 ,而不是 。逆定理正确地使用了不等式,并适用于这个重复编码器。若以未经论证的输入独立性假设替代这个不等式,就会夸大实际码所携带的信息。
常见错误
反例模式
单坐标噪声分布相同并不能证明信道无记忆
假设把同一个公平比特 加到所传输二元分组的每一位上。单独看每个坐标,它都像一个完全有噪声的二元信道。然而接收者看到的要么是整个字,要么是它的补。选取第一位为零的码字,用其余 位表示消息。接收到的第一位揭示了 ,所以所有位都可以被纠正,错误概率为零,码率为 。噪声在分组内是相关的,所以乘积条件分布不成立;若由单坐标边缘分布得出容量为零的结论,就是错误的。
常见错误
(证明不是一种构造)
该定理同样没有断言均匀输入是最优的,确定性信道的例子已说明这一点。其指数规模的随机列表也不构成实用的编码算法。译码器可以把接收字与每个带编号的码字比较;证明的目标是在某一码率下的存在性,高效的构造则需要另外的工作。
反例模式
平均错误概率小并不约束每个消息
断言:若一列码的平均错误概率趋于零,则其最大错误概率也趋于零。取无噪二元信道与 个消息,每个消息以它自己的 位字发送;译码器除了把输出 映到 的消息以外都正确。于是消息 总被译错,其他消息全被译对,平均错误概率为 ,最大错误概率却对每个 都是 。修正方法是剔除:舍弃错误概率超过平均值两倍的消息(这里只有 ),剩下的码最大错误概率为零,码率损失至多 。
总结
对有限无记忆信道,容量是输入与输出之间互信息的最大值。信息密度的集中性与似然比的界证明所有更小的正码率都是可达的。固定码本并剔除高错误概率的消息,得到最大错误概率意义下的可靠性。Fano 不等式与无记忆熵恒等式证明了弱逆定理,即使编码后的输入是相关的亦然。
练习
快速检查
(证明:容量为零当且仅当每个输入符号都诱导出相同的输出分布。)
把容量写成相对于输出混合分布的散度的平均。
解答
若各行都相同,则对任意输入分布,输入与输出都独立,所以互信息为零。反之,若有两行不同,让它们对应的输入取相等概率。互信息是这两个分布各自相对于输出混合分布的散度的平均值。散度非负,且仅当分布相同时为零,所以至少有一个为正,互信息为正。因此容量的最大值为正。
快速检查
(为什么在系综论证中,竞争的随机码字与输出独立,而被发送的随机码字则不独立?)
想一想输出由哪些随机变量产生。
解答
在给定被发送的编号的条件下,输出由该编号的随机字与新的信道噪声产生。每个不同编号的字都与这两者独立地抽取。被发送的字与输出由信道联系在一起,联合分布为 ;若把这个联合分布换成独立的乘积分布,就会破坏真实符号对的集中性论证。
快速检查
(若目标码率是固定的 ,已证明的逆定理给出平均错误概率怎样的渐近下界?它是否迫使错误概率趋于一?)
以 整理逆定理。
解答
重排得 ,其中 。若 ,则下极限至少为 。除了容量为零的特殊情形外,这一般小于一。强逆定理的证明需要这一不等式之外的进一步推理。
快速检查
(解释为什么保留至少一半的消息在渐近意义下不损失码率,尽管它可能在绝对数量上去掉很多消息。)
比较 与 。
解答
把 换成不小于 的数,至多使 减少一,因此至多使码率减少 。这一损失随分组长度趋于零。直接计算被去掉的消息数,忽略了码率使用的是消息数的对数。