(信息论)第6章有噪信道编码

1、第 6 章 有噪信道编码,6.1 噪声信道的编码问题,6.1.1 错误概率和译码规则,二元对称信道,错误概率不仅与信道的统计特征有关，而且也与译码规则有关。,如上例,6.1.2 译码规则,定义 6.1.1 设信道输入符号集为 ，输出符号集为 ，若对每一个输出符号 都有一个确定的函数 ，使 对应唯一的一个输入符号 ，则称这样的函数为译码规则，记为,显然，对于有 r 个输入、s 个输出的信道而言，按上述定义得到的译码规则共有 种。,(6.1),1、错误概率,在译码规则 的情况下，得出条件正确概率和条件错误概率分别为,因为译码过程有统计平均作用，经过译码后的平均错误概率 为,上式的含义是经过译码后，

2、平均接收到一个符号所产生错误的大小。,(6.2),(6.3),2、译码规则,选择译码规则总的原则应是使平均错误概率 最小。,由于错误概率 为非负项之和，欲使 最小，那么应使每一项为最小，又由于式(6.3)中 与译码规则无关，故欲使 最小，从式(6.2)看出，亦即为使 为最大，于是引出最大后验概率准则。,定义 6.1.2 选择译码函数 ，使之满足条件,则称为最大后验概率译码规则(理想观测者规则)。该规则的意义是选择这样一种译码函数，对于每一个输出符号 均译成具有最大后验概率的那个输入符号 ，则信道译码错误概率会最小。一般说来，后验概率是难以实现的，所以应用起来并不方便。,(6.4),定义 6.1

3、.3 选择译码函数 ，使之满足条件,则称为极大似然译码规则。,当输入符号为等概分布时,则式(6.5)可改写成,当信道输入符号为等概分布时，应用极大似然译码规则是很方便的，式(6.7)中的条件概率为信道矩阵中的元素。从最大后验概率译码规则可以导出极大似然译码规则。,(6.7),(6.6),(6.5),3、平均错误概率,平均错误概率的 推导过程：,(6.8),平均正确概率为,若用条件概率表示，式(6.8)又可表示为,若输入为等概分布，则,式(6.11)意味着，在输入为等概分布的条件下，译码错误概率 可用信源矩阵中的元素来表示。这种求和是除去信道矩阵中每列中对应于 的那一项后，求矩阵中其余元素之和。

4、,(6.9),(6.10),(6.11),例： 已知信道矩阵,设计如下两种译码规则：,当输入为等概分布时，译码规则 A 就是极大似然译码规则。两种译码规则所对应的平均错误概率分别为,引理 6.1.1 错误概率 与信道疑义度 满足以下关系,该不等式称为费诺不等式。,(6.12),上式的意义是：当作了一次译码判决后所保留的关于信源的不确定性可以分成两部分：第一部分是接收到Y 后，判决是否发生错误的不确定性 ；第二部分是当判决是错误的，其错误概率为 ，确定由 r-1 个输入符号中哪一个引起错误的不确定性，它是 (r-1) 个符号不确定性的最大值 与 的乘积。,Fano 不等式的几何意义,6.2 错误

5、概率与编码方法,6.2.1 简单重复编码,信道矩阵为,选择最佳译码规则为,在输入分布为等概分布的条件下，总的平均错误概率为,简单重复编码就是规定当信源符号为“0”(或“1”)时，则重复发送若干个“0”(或“1”)。这样规则构成的信道实际上就是二元对称信道的三次扩展信道 。输入符号和输出符号的关系为：,没有使用 的码字,发送端用作 消息的码字,输出端 接收序列,二元对称 信道的三次 扩展信道,简单重复编码图,则这时的信道矩阵为,设输入符号为等概分布，采用极大似然译码规则，即取信道矩阵中每列数值最大的元素所对应的 为 ，所以译码函数为,在输入为等概条件下，相应的平均错误概率为,该方法采用的是“择多

6、译码”的译码规则。得到的平均错误与最大似然译码规则是一致的。,采用简单重复编码方法，如果进一步增大重复次数 n ，则会继续降低平均错误概率 ，,虽然随着提高重复编码次数 n ，平均错误概率 得到下降，但同时信息传输率也在减小，也就是说简单重复编码减少平均错误概率是以降低信息传输率为代价的。这是由于,(无重复编码),6.2.2 消息符号数,n 次扩展信道的消息符号,在一个二元信道的 n 次无记忆扩展信道中，输入端共有 个符号序列可能作为消息符号，仅选其中M个作为消息符号传递。则当M选取大些， 也跟着增大，R 也大；M选取小些， 就降低些，而 R 也要降低。,6.2.3 (5.2) 线性码,(5.

7、2)线性码，在适当增大 n 和 M 的情况下，得到比较低的平均错误概率和较好的信息传输率 R 。,设取 M=4, n=5，这时信息传输率,而输入符号的 4 ( M = 4 )个码字采用下列编码方法,其中， 为 中第 k 个分量， ，且码字 中个分量满足方程,(6.13),(6.14)式可写成如下的形式,(6.14),(6.15),采用上述编码方法则得到如下一种(5.2)线性码。,输入端发送序列,输出端接收序列,译码规则,扩展信道,输入端发送序列,输出端接收序列,译码规则,扩展信道,续,仍采用极大似然译码规则，可计算得正确译码概率为,而平均错误译码概率为,从该编码方法上看，与从二元信道经过 n

8、次扩展的得到的消息符号数中取同样的M个符号传递相比，虽然信息传输率 R 略有降低，但平均错误概率都要好得多。,6.2.4 汉明距离,定义 6.2.1 设 为两个 n 长的二元码字，则码字 X 和 Y 之间的汉明距离定义为,其中， 表示模二和运算,上式的含义是两个码字之间的汉明距离就是它们在相同位上不同码符号的数目的总和。,(6.16),汉明距离的性质,非负性,当且仅当 X=Y 时等号成立。,对称性,三角不等式,定义 6.2.2 在二元码 C 中，任意两个码字的汉明距离的最小值，称为码 C 的最小距离，即,(6.17),最小码间距离 越大，则平均错误概率 越小。在输入消息符号个数 M 相同的情况

9、下，同样地 越大， 越小。概括地讲，码组中最小距离越大，受干扰后，越不容易把一个码字错误译成另一个码字，因而平均错误概率 小。如果最小码间距离 小，受干扰后很容易把一个码字错译成另一个码字，因而平均错误概率大。这意味着，在选择编码规则时，应使码字之间的距离越大越好。,汉明距离对极大似然译码规则的表示,极大似然译码规则为,式中 信道输入端作为消息的码字，码长为 n； 信道输出端接收到的可能有的码字，码长亦为 n ; 似然函数。,设码字 与 的距离为 D，则表示在传输过程中有 D 的位置发生错误， n-D 个位置没有发生错误。即,(6.18),当信道无记忆时，有,从式(6.19)看出，当 时，D

10、越大，则 越小；D 越小，则 越大。因此，极大似然译码规则式 (6.18) 就变成了这样一个含义：当接收到码字 后，在输入码字集 中寻找一个 ，使之与 的汉明距离为最短，即选取译码函数,使之满足,(6.19),(6.20),结 论 综上所述，在有噪信道中，传输的平均错误概率 和各种熵、译码方法有关。 编码方法：采用使码的最小距离尽可能增大的编码方法； 译码方法：采用将接收序列 译成与之距离最短的码字 的译码方法； 在上述的编码和译码方法准则下，只要 n 足够长时，适当选择输入符号个数 M，就可以使平均错误概率很小，而信息传输率又能保持一定。,6.3 有噪信道编码定理,定理 6.3.1 设有一离

11、散无记忆平稳信道，其信道容量为 C，只要待传送的信息传输率 ，则存在一种编码，当输入序列长度 n 足够大，使译码错误概率任意小。 该有噪信道编码定理称为 Shannon第二定理，又称为信息论的基本定理。,Shannon 第二定理的物理意义：设有一信道容量为 C 的信道。信道的输入符号数为 r，输出符号数为 s 。由于输入符号序列长度为 n，因此可构成 个可供选择的输入消息符号。从 个符号集中找到 个码字(长度为 n )组成的一组码。这样编码后，信道的信息传输率为,只要 ，就可以在有噪信道中以任意小的错误概率 传输信息，而且当 n 足够大时，可以以任意接近信道容量 C 的信息传输率 R 传递信息

12、。,定理 6.3.2 设有一离散无记忆平稳信道，其信道容量为 C，对于任意 ，若选用码字总数 ，则无论 n 取多大，也找不到一种编码，使译码错误概率 任意小。 该定理称为有噪信道编码定理的逆定理 ，也称为Shannon 第二定理的逆定理。,Shannon 第二定理的逆定理的物理意义：当选择码字个数 时，信息传输率为,显然，信息传输率 R 大于信道容量 C，因此，要想使信息传输率大于信道容量而又无错误地 传输消息是不可能。 由Shannon第二定理和它的逆定理可见，在任何信道中，信道容量是进行可靠传输的最大信息传输率。,6.4 错误概率的上界,错误概率上界的表示式：,对于离散无记忆信道(DMC)，平均错误概率为,(6.37),该式表明平均错误概率 趋于零的速度是与 n 成指数关系的。,为随机编码指数，或称为可靠性函数或加拉格(Gallager)函数。一般可靠性函数 与信息传输率 R 的关系曲线如下图所示。它是一条下凸函数曲线。在 的