信息论与编码纠错第5章

信息论与编码,第5章,有噪信道编码,内容提要,本章介绍了信道编码和译码的基本概念，介绍了两种常用的译码准则：最大后验概率译码准则和极大似然译码准则,还介绍了在这两种译码准则下错误概率的计算方法。,本章还介绍了信道编码定理及信道编码逆定理，以及信息论中的一个重要不等式Fnao不等式。,5.1信道编码的基本概念,我们要尽可能的提高信息传输率，并控制传输误差。信源编码以提高传输效率作为主要考虑因素，信道编码以提高传输可靠性作为主要考虑因素。,信道有多种形式，如电视、广播、微波、电话、计算机局域网和宽带网等，对于所有的信道可用下图所示的模型来表示：,衡量信道传输快慢的指标是信息传输率，而衡量信息传输可靠性的指标是平均错误概率，平均错误概率与信道的统计特性有关。,要改变信道统计特性成本太大，所以可事先对信源编码器输出的符号序列按照某种规则进行编码，一般的方法是给信源序列加上一定的冗余度，这种编码称为,信道编码,，编好的代码称为,码字,，将码字送入信道传输，在信道的输出端，信道译码器根据编码规则对信道输出符号进行估值，尽量使这种估值接近输入码字。,信源输出序列 ，经信道编码器编成码字 并输入信道，由于干扰，信道输出 ，信道译码器对估值得 。,【例】给定二元对称信道，信道固有错误概率为,p,（,p,0.5）,编码规则：为提高可靠性，每个信道符号重复三次发送。,译码规则：择多译码，即信宿方收到的三个符号中有两个或三个为1，就将此次接收符号判决为1；若三个符号中有两个或三个为0，就将此次接收符号判决为0。,下面为重复编码传输示意图，计算错误概率,p,e。,信源输出序列为：,信道输入序列为：,由于p的存在，使得传输出错，故信道输出为：,根据译码规则，信道估值输出：,信道错误概率：假设信道离散无记忆，即,错误概率为：,重复编码的结果使错误概率下降。,【,例】逆重复码,离散无记忆二进制对称信道，固有误码率为p(p0.5)，信源输出序列为三位二进制数字。,编码规则：为提高传输效率，仅向信道发送一位，预先将信源输出序列进行择多编码：信源输出的三位符号中有两位或3位是1，信源序列编码为1，若三位符号中有两位或3位是0，就将此信源序列编码为0。,译码规则：将接收的一位符号重复三次译出，即若接收到1就译码为111，即若接收到0就译码为000。,下面为重复编码传输示意图，计算错误概率,p,e。,（1）先设,p,=0，计算这种编码方法带 来的固有错误,p,1,。,信道输入符号集,X,=000，001，010，011，100，101，110，111,判决输出符号集,Y,=000，111,译码规则：,因为后验概率：,则出错概率：,假设8组输入序列是等概发送的，由于信道的对称性，两个估值序列也是等概分布的，则每个序列的平均错误概率为:,误比特率,（2）再设,p,0，计算由于信道噪声引起的错误概率,p,2,。,因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率为p，故序列差错概率为p，误比特率,（3）总差错概率（误比特率）：,【,例】奇偶校验码,在信息序列后面加上一位校验位，使之模2和等于1，这样的编码称为奇校验码；若使模2和等于0，这样的编码就称为偶校验码，即每个码矢中1的个数固定为奇数或偶数。,奇偶校验码能检测出奇数位错误，但无法判断错的是哪一位，故没有纠错能力。这种编码方式可用在反馈信道场合，如计算机通信串口通信。,5.2 译码规则及错误概率,信道总不可避免会搀杂噪声，所以信息在信道传输过程中，差错是不可避免的。选择合适的译码规则可以弥补信道的不足。,【例】BSC信道的转移概率如下,时，这是一种强噪声信道，在这种情况下，若按常规译码，肯定出错，但可将判决取反，收到0判为1，收到1判为0，反而正确。,可见译码规则对传输系统错误概率的影响是很大的。,一最大后验概率译码准则,设信源有M个消息，信道编码器已用M个码矢,对它进行了最佳编码。,编码后发送码矢量 ，其发送概率为 ，通过信道转移概率为,的信道传输，接收矢量为 ，信道译码器输出 。,通信过程框图如下：,当估值 时，就产生了误码，用 表示后验概率，则收到 估错的错误概率为：,通信总希望错误概率最小，由上式可看出错误概率 最小等同于后验概率 最大，这就是,最大后验概率译码准则,。,根据概率关系式,根据最大后验概率译码准则，收到矢量,后，在所有,中，,选一个后验概率,最大的,值，作为对,的估值,，那么对这M个,说，概率 是同一值，根据上式后验概率,值来,就意味着全概率 最大，因此最大后验概率译码准则也称为,最大联合概率译码准则,。,最大,【例】信源分布,信道转移概率矩阵,信道输出符号,Y,=,y,1,，,y,2,，,y,3,，按最大后验概率准则译码。,(1)根据,p,(,xy,)=,p,(,y,/,x,),p,(,x,)算出全概率，用矩阵表示,(2)根据,，算出,p,(,y,),=,0.38 0.34 0.28,(3)再由,算出后验概率，用矩阵表示,(4)按最大后验概率准则译码，在后验概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为,(5)若按最大联合概率译码准则译码，在全概率矩阵 p(xy)中每列选一最大值（矩阵中带下划线的值），也可译出,二极大似然译码准则,前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码准则是最好的。,在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。,在这种情况下，一般采用最大信道转移概率来确定估值，即在收到矢量,后，在所有的,中，选一个转移概率,最大的,值，作为对,的估值,译码规则。,，,这一译码规则称为,极大似然,实际上，在信道输入等概率条件下，极大似然译码规则也是最佳的。,输入等概率时，有,，故,则有,三平均错误概率,对信道译码器估错概率关于输出求统计平均值：,【例】信源分布,信道转移概率矩阵,，信道输出符号,Y,=,y,1,，,y,2,，,y,3,。,（1）计算按最大后验概率准则译码的平均错误概率；,（2）若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率。,【解】（1）最大后验概率准则译码,平均错误概率：,（2）当信源等概分布，按最大似然函数译码准则译码，已给出信道转移概率矩阵为,在矩阵的每列中选一最大值(矩阵中带下划线的值)，译码为,平均错误概率：,【,例】考虑重复码，信源等概率分布，采用极大似然译码规则进行译码，并计算平均错误概率。,根据编码规则：,重复3次编码，即,原信道的固有错误概率为p（p 0.5）的二进制对称信道，其信道转移概率矩阵为：,经编码后得到的码字是码长为3的码矢量，送入3次扩展信道传输，信道离散无记忆，扩展信道的信道转移概率矩阵为：,按极大似然译码准则译码，在矩阵的每列中选一最大值（带下划线的值），译码为：,计算平均错误概率，信源等概率分布,5.3 信道编码定理及逆定理,由于信道在传输过程中不可避免地拾取干扰，以致产生错误，选择合适的编译规则可以使错误概率尽可能小，信道编码定理（香农第二定理）指出：信道容量C是在满足错误概率pe0时，信道所能容纳的信息传输率的极限值。,【定理】有噪信道编码定理（香农第二定理）,对于任何离散无记忆信道DMC，存在信息传输率为RC，长为n的码，当n 时，平均差错概率 pe exp-nE(R)0。式中E(R)为可靠性函数，E(R)在0 R C的范围内为正。,说明：,1设离散信道的信道容量为C，只要信息传输率RC，总可以找到一种编码方法，使得当代码组长度n足够长时，接收端恢复消息的误码率pe0；即若RC，有扰离散信道存在可靠性编码。,2,p,e,exp-,nE,(,R,)，当n增大，则,p,e,急剧减小；n，,pe,0；,3可靠性函数,E,(,R,)：只要R 0。,【定理】信道编码逆定理,信道容量C是可靠通信系统信息传输率的上界，当R C，不可能存在任何方法使差错概率任意小。也就是说，当R C时，误码率有一固定下界值，即使增加代码组长度n，也不能使误码率任意小，即，R C，不存在可靠性编码。,信道译码器,