第五章 信道编码ppt课件.ppt

第五章 有噪信道编码,错误概率及相关因素 如何使信号经过传输后，错误概率最小,信道编码定理 在有噪信道中，无差错传输的最大信息量有多大,线性分组码 实用编码范例,有噪信道编码,有噪信道编码,信源编码：有效性信道编码：可靠性,可以编码成 有效性： 更好 可靠性： 更好，提供纠错功能,有噪信道编码,香农第二定理，在理论上很好的统一了有效性和可靠性，使信息传输率达到信道容量的情况下，还能够无失真的在有噪信道中传输。,有效性，可靠性很难兼顾。提高有效性，需要消除冗余；提高可靠性，需要适当增加冗余。,错误概率及相关因素,与以下三个因素有关：信道特性译码规则编码方法,信道统计特性,无噪无损信道：错误概率0P=0.5的二元对称信道：错误概率50%,译码规则,译码规则,“译码规则”：设计一个函数 ，对于每一个输出符号 ，确定唯一的输入符号 与之对应,译码规则,错误概率为1,错误概率为0,译码规则,二元对称信道,错误概率为0.99,错误概率下降为0.01,译码规则,对于一个 的传递矩阵，译码规则共有 种,在这么多种译码规则中，我们选择哪一种?,当然希望译码后的错误概率越小越好.,选择的标准是什么？,译码规则,对于确定 ，制定译码函数,译码错误的概率是,译码正确的概率是,称为条件错误概率,译码规则,正确概率,译码规则,技巧：一般都不直接求,等输入概率情况下,称为正确概率,，而是先算,然后用,译码规则例,计算各种译码规则对应的平均差错概率,译码规则例,先计算译码正确的概率,对于规则一(F1)：,同理,最小错误概率准则,平均错误概率定义后，一个很自然的准则就是使平均错误概率最小，即最小错误概率准则,平均错误概率是一个求和式，每一项都是非负的,如果每一项都为最小，则整个求和式最小.,最小错误概率准则,即选择函数：,并使之满足条件：,即这种译码函数，它对于每一个输出符号均译成最大后验概率的那个输入符号，则信道错误概率就能最小，这种译码规则称为“最大后验概率译码准则”或“最小错误概率译码准则”,最小错误概率准则,贝叶斯定律,最大后验概率准则的条件式可以写成,最大似然准则,输入符号等概率分布时，最大后验概率准则变成了,称为最大似然准则,所以，最大似然准则不是最佳译码规则,译码规则的选取,最大后验概率准则依赖最大似然准则仅依赖,先验概率等概率分布，使用最大后验概率准则和最大似然准则是一致的如果知道先验概率，应该使用最大后验概率准则如果不知道先验概率，则只能用最大似然准则,译码规则例,例：信道的传递概率矩阵求译码规则和平均错误概率1.输入等概率时2. 3. 用最大似然准则,译码规则例,1.等概率分布时，用最大似然准则，等效于最大后验概率准则。对于传递矩阵中的每一列，选一个最大的传递概率，对应的输入符号即为该输出符号的译码函数,译码规则例,2.已知输入概率分布，用最大后验概率准则，求联合概率,译码规则例,3.非等概率分布，但是规定要用最大似然准则,可见在输入非等概率分布时，最大似然准则并不一定是最佳译码规则,课堂练习,离散信道的传递概率矩阵为分别按照最小错误概率准则和最大似然准则确定译码规则，并计算相应的平均错误概率,课堂练习、作业,用最大后验概率准则，求联合概率,课堂练习、作业,用最大似然准则,编码方法,0.01的错误率在很多情况下难以容忍。一般来说，信息传输系统的平均差错率要求控制在10-6 以下，因此必须要进一步地降低错误概率：编码方法,编码方法增加扩展次数,二元信源进行编码方法1：0；1方法2：000；111,输入符号等概率分布，译码规则采用最大似然准则,编码方法增加扩展次数,方法1：0；1,方法2：000；111,编码方法增加扩展次数,用方法二，增加扩展次数可以降低错误概率,结论1：M不变时，n越大，PE 越小，R也越小。,编码方法减小输入符号数,令n=3，M变化，看看此时 和R的变化情况,M=8时的情况：,M=2时的情况：,编码方法减小输入符号数,M=8时的情况：,编码方法减小输入符号数,M=4时的情况，输入符号是：000、011、101、110,编码方法减小输入符号数,M=4时的情况，输入符号是：000、011、101、110,编码方法减小输入符号数,总结：当n=3不变，M变化时,结论2：n不变时，M越大，PE 越大，R也越大,编码方法调整输入符号,n一定，M也一定，选择不同的输入符号,输入符号是000、001、010、100,输入是000、011、101、110时,编码方法调整输入符号,第二种方式和第一种方式相比，信息传输率一样，平均错误概率更大,结论3：n、M一定，选择不同的输入符号， PE不同，R相等,编码方法增大最小距离,第一种：两两之间都有2个二元符号不同。一个二元符号出错，不会串扰到其它输入符号，因此可以判断出现了错误 。 第二种：000与其它输入符号之间只差一个二元符号，当000任何一个二元符号出现错误时，就会串扰到其它输入符号上，也就判断不出错误。,编码方法增大最小距离,为了描述符号序列之间的这种相差性，定义了汉明距离。,例如,对应位置上有3个码元不同,编码方法增大最小距离,相应位置上的码元是否相同，在C语言中就是异或运算（相异为1，相同为0），所以汉明距离可以表示为：,在码字集合中，共有M个码字，两两之间的汉明距离共有,编码方法增大最小距离,最小距离：任意两个码字的汉明距离的最小值，称为该码的最小距离,M、n相同的情况下， 越大， 就越小对于不同的M和n，也有这样的准则,编码方法增大最小距离,前面我们讲到的减小错误概率的方法，如M一定，增大n；n一定，减小M。本质上都是为了增大最小距离,结论4（本质结论）：增大 ，就可以减小,所以我们选择编码方法时，要使码字间的距离尽可能大,最小距离译码规则,定义了汉明距离之后，又引入了一种译码规则：最小距离译码规则,即选择译码函数：,最小距离译码规则,选择译码函数时不用计算传递概率，只用计算汉明距离,F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=111,最小距离译码规则,最小距离译码规则、最大似然准则都仅仅考虑了信道的统计特性，没有考虑输入序列的概率分布。两种译码规则有什么样的区别与联系呢？,我们可以证明，在正常的二元对称信道上，两者是一致的，而在其他信道上则不一定。所谓正常的二元对称信道，指正确概率大于错误概率的二元对称信道,最小距离译码规则,最小距离准则为：,因为二元对称信道是离散无记忆信道，输出分量只与当前时刻的输入分量相关,最大似然准则为：,最小距离译码规则,因此有：,最小距离译码规则,对于正常的信道，有 ，正确概率大于错误概率 的幂数越高， 则越大，也就是汉明距离D 越小， 越大最大似然准则和最小距离准则实现了统一,最小距离和纠错能力,要纠正1位错误，要求码的最小距离,一个码能够检测 位错误的充要条件为：,一个码能够纠正 位错误的充要条件为：,一个码能够纠正 个错误，同时又能检测出 位错误的充要条件为：,要检测1位错误，要求码的最小距离,课堂练习,设某二元码为C=11100, 01001, 10010, 001111、计算此码的最小距离2、计算此码的码率R，假设码字等概率分布3、采用最小距离译码准则，试问接收序列10000，01100和00100应译为什么码字4、此码能够纠正几位码元的错误？,练习、作业,解：设,练习、作业,有噪信道编码定理,信息传输的可靠性和有效性之间，仿佛总是存在着冲突，提高了可靠性的同时，往往都会牺牲了有效性 有没有一种解决方法，存在不存在一种编码方法，能够协调有效性和可靠性之间的冲突，在信息传输率R不降低的情况下，减小错误概率呢？ 香农第二定理，有噪信道编码定理很好的回答了这个问题,有噪信道编码定理,香农第二定理：设离散无记忆信道X、Y分别代表输入、输出信号， 是传递概率分布。当信息传输率 时，只要码长n足够大，就存在着一种码和对应的译码规则，使译码后的错误概率任意小,香农第二定理指出信道容量是保证无差错传输时，信息传输率的极限值,有噪信道编码逆定理,设离散无记忆信道 ，信道容量为C。当信息传输率 时，无论码长n有多长，总也找不到一种编码，使平均错误概率任意小,信道纠错编码的基本概念,尽管早在1948年，香农就提出了关于在有噪信道中传输信息的重要理论，但是却没有明确的给出具体的编解码算法。 之后无数的科学技术工作者在香农第二定理的指导下进行了很多积极的实践和探索，总结出许多行之有效的编解码算法，从而逐步形成了一门技术学科纠错编码 在差错控制系统中按照纠错能力的不同，分为检错码和纠错码两种,线性分组码,线性分组码的基本概念,线性分组码的基本概念,分组码：每k个信息码元为一组，以一定的规律再生成r个校验码元，共同组成一个n=k+r个码元的码字线性码：信息码元和校验码元之间的是线性的关系。即校验码元的产生，是由各信息码元以线性的关系产生的,(7,4)汉明码,汉明码是重要的线性分组码，以（7，4）汉明码为例阐述汉明码的基本思想 为什么叫（7，4）汉明码？因为汉明码是分组码，每组码中有4个信息码元，编码后码长为7，包括4个信息码元和3个校验码元,(7,4)汉明码,(7,4)汉明码有4个独立的码字，将这4个独立的码字组成如下47的矩阵，称为生成矩阵,可以用生成矩阵G，从信息码元序列，生成汉明码字,如,信道编码概念,