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

第6章有噪信道编码,6.1噪声信道的编码问题,6.1.1错误概率和译码规则,二元对称信道,错误概率不仅与信道的统计特征有关，而且也与译码规则有关。,如上例,6.1.2译码规则,定义6.1.1设信道输入符号集为，输出符号集为，若对每一个输出符号都有一个确定的函数，使对应唯一的一个输入符号，则称这样的函数为译码规则，记为,显然，对于有r个输入、s个输出的信道而言，按上述定义得到的译码规则共有种。,(6.1),1、错误概率,在译码规则的情况下，得出条件正确概率和条件错误概率分别为,因为译码过程有统计平均作用，经过译码后的平均错误概率为,上式的含义是经过译码后，平均接收到一个符号所产生错误的大小。,(6.2),(6.3),2、译码规则,选择译码规则总的原则应是使平均错误概率最小。,由于错误概率为非负项之和，欲使最小，那么应使每一项为最小，又由于式(6.3)中与译码规则无关，故欲使最小，从式(6.2)看出，亦即为使为最大，于是引出最大后验概率准则。,定义6.1.2选择译码函数，使之满足条件,则称为最大后验概率译码规则(理想观测者规则)。该规则的意义是选择这样一种译码函数，对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道译码错误概率会最小。一般说来，后验概率是难以实现的，所以应用起来并不方便。,(6.4),定义6.1.3选择译码函数，使之满足条件,则称为极大似然译码规则。,当输入符号为等概分布时,则式(6.5)可改写成,当信道输入符号为等概分布时，应用极大似然译码规则是很方便的，式(6.7)中的条件概率为信道矩阵中的元素。从最大后验概率译码规则可以导出极大似然译码规则。,(6.7),(6.6),(6.5),3、平均错误概率,平均错误概率的推导过程：,(6.8),平均正确概率为,若用条件概率表示，式(6.8)又可表示为,若输入为等概分布，则,式(6.11)意味着，在输入为等概分布的条件下，译码错误概率可用信源矩阵中的元素来表示。这种求和是除去信道矩阵中每列中对应于的那一项后，求矩阵中其余元素之和。,(6.9),(6.10),(6.11),例：已知信道矩阵,设计如下两种译码规则：,当输入为等概分布时，译码规则A就是极大似然译码规则。两种译码规则所对应的平均错误概率分别为,引理6.1.1错误概率与信道疑义度满足以下关系,该不等式称为费诺不等式。,(6.12),上式的意义是：当作了一次译码判决后所保留的关于信源的不确定性可以分成两部分：第一部分是接收到Y后，判决是否发生错误的不确定性；第二部分是当判决是错误的，其错误概率为，确定由r-1个输入符号中哪一个引起错误的不确定性，它是(r-1)个符号不确定性的最大值与的乘积。,Fano不等式的几何意义,6.2错误概率与编码方法,6.2.1简单重复编码,信道矩阵为,选择最佳译码规则为,在输入分布为等概分布的条件下，总的平均错误概率为,简单重复编码就是规定当信源符号为“0”(或“1”)时，则重复发送若干个“0”(或“1”)。这样规则构成的信道实际上就是二元对称信道的三次扩展信道。输入符号和输出符号的关系为：,没有使用的码字,发送端用作消息的码字,输出端接收序列,二元对称信道的三次扩展信道,简单重复编码图,则这时的信道矩阵为,设输入符号为等概分布，采用极大似然译码规则，即取信道矩阵中每列数值最大的元素所对应的为，所以译码函数为,在输入为等概条件下，相应的平均错误概率为,该方法采用的是“择多译码”的译码规则。得到的平均错误与最大似然译码规则是一致的。,采用简单重复编码方法，如果进一步增大重复次数n，则会继续降低平均错误概率，,虽然随着提高重复编码次数n，平均错误概率得到下降，但同时信息传输率也在减小，也就是说简单重复编码减少平均错误概率是以降低信息传输率为代价的。这是由于,(无重复编码),6.2.2消息符号数,n次扩展信道的消息符号,在一个二元信道的n次无记忆扩展信道中，输入端共有个符号序列可能作为消息符号，仅选其中M个作为消息符号传递。则当M选取大些，也跟着增大，R也大；M选取小些，就降低些，而R也要降低。,6.2.3(5.2)线性码,(5.2)线性码，在适当增大n和M的情况下，得到比较低的平均错误概率和较好的信息传输率R。,设取M=4,n=5，这时信息传输率,而输入符号的4(M=4)个码字采用下列编码方法,其中，为中第k个分量，且码字中个分量满足方程,(6.13),(6.14)式可写成如下的形式,(6.14),(6.15),采用上述编码方法则得到如下一种(5.2)线性码。,输入端发送序列,输出端接收序列,译码规则,扩展信道,输入端发送序列,输出端接收序列,译码规则,扩展信道,续,仍采用极大似然译码规则，可计算得正确译码概率为,而平均错误译码概率为,从该编码方法上看，与从二元信道经过n次扩展的得到的消息符号数中取同样的M个符号传递相比，虽然信息传输率R略有降低，但平均错误概率都要好得多。,6.2.4汉明距离,定义6.2.1设为两个n长的二元码字，则码字X和Y之间的汉明距离定义为,其中，表示模二和运算,上式的含义是两个码字之间的汉明距离就是它们在相同位上不同码符号的数目的总和。,(6.16),汉明距离的性质,非负性,当且仅当X=Y时等号成立。,对称性,三角不等式,定义6.2.2在二元码C中，任意两个码字的汉明距离的最小值，称为码C的最小距离，即,(6.17),最小码间距离越大，则平均错误概率越小。在输入消息符号个数M相同的情况下，同样地越大，越小。概括地讲，码组中最小距离越大，受干扰后，越不容易把一个码字错误译成另一个码字，因而平均错误概率小。如果最小码间距离小，受干扰后很容易把一个码字错译成另一个码字，因而平均错误概率大。这意味着，在选择编码规则时，应使码字之间的距离越大越好。,汉明距离对极大似然译码规则的表示,极大似然译码规则为,式中信道输入端作为消息的码字，码长为n；信道输出端接收到的可能有的码字，码长亦为n;似然函数。,设码字与的距离为D，则表示在传输过程中有D的位置发生错误，n-D个位置没有发生错误。即,(6.18),当信道无记忆时，有,从式(6.19)看出，当时，D越大，则越小；D越小，则越大。因此，极大似然译码规则式(6.18)就变成了这样一个含义：当接收到码字后，在输入码字集中寻找一个，使之与的汉明距离为最短，即选取译码函数,使之满足,(6.19),(6.20),结论综上所述，在有噪信道中，传输的平均错误概率和各种熵、译码方法有关。编码方法：采用使码的最小距离尽可能增大的编码方法；译码方法：采用将接收序列译成与之距离最短的码字的译码方法；在上述的编码和译码方法准则下，只要n足够长时，适当选择输入符号个数M，就可以使平均错误概率很小，而信息传输率又能保持一定。,6.3有噪信道编码定理,定理6.3.1设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率，则存在一种编码，当输入序列长度n足够大，使译码错误概率任意小。该有噪信道编码定理称为Shannon第二定理，又称为信息论的基本定理。,Shannon第二定理的物理意义：设有一信道容量为C的信道。信道的输入符号数为r，输出符号数为s。由于输入符号序列长度为n，因此可构成个可供选择的输入消息符号。从个符号集中找到个码字(长度为n)组成的一组码。这样编码后，信道的信息传输率为,只要，就可以在有噪信道中以任意小的错误概率传输信息，而且当n足够大时，可以以任意接近信道容量C的信息传输率R传递信息。,定理6.3.2设有一离散无记忆平稳信道，其信道容量为C，对于任意，若选用码字总数，则无论n取多大，也找不到一种编码，使译码错误概率任意小。该定理称为有噪信道编码定理的逆定理，也称为Shannon第二定理的逆定理。,Shannon第二定理的逆定理的物理意义：当选择码字个数时，信息传输率为,显然，信息传输率R大于信道容量C，因此，要想使信息传输率大于信道容量而又无错误地传输消息是不可能。由Shannon第二定理和它的逆定理可见，在任何信道中，信道容量是进行可靠传输的最大信息传输率。,6.4错误概率的上界,错误概率上界的表示式：,对于离散无记忆信道(DMC)，平均错误概率为,(6.37),该式表明平均错误概率趋于零的速度是与n成指数关系的。,为随机编码指数，或称为可靠性函数或加拉格(Gallager)函数。一般可靠性函数与信息传输率R的关系曲线如下图所示。它是一条下凸函数