第五章-信道编码课件

第五章有噪信道编码错误概率及相关因素如何使信号经过传输后，错误概率最小信道编码定理在有噪信道中，无差错传输的最大信息量有多大线性分组码实用编码范例第五章有噪信道编码错误概率及相关因素信道编码定理1有噪信道编码有噪信道编码2有噪信道编码信源编码：有效性信道编码：可靠性可以编码成有效性：更好可靠性：更好，提供纠错功能有噪信道编码信源编码：有效性可以编码成3有噪信道编码香农第二定理，在理论上很好的统一了有效性和可靠性，使信息传输率达到信道容量的情况下，还能够无失真的在有噪信道中传输。有效性，可靠性很难兼顾。提高有效性，需要消除冗余；提高可靠性，需要适当增加冗余。有噪信道编码香农第二定理，在理论上很好的统一了有效性4错误概率及相关因素与以下三个因素有关：信道特性译码规则编码方法错误概率及相关因素与以下三个因素有关：5信道统计特性无噪无损信道：错误概率0P=0.5的二元对称信道：错误概率50%信道统计特性无噪无损信道：错误概率06译码规则译码规则7译码规则“译码规则”：设计一个函数，对于每一个输出符号，确定唯一的输入符号与之对应

译码规则“译码规则”：设计一个函数，对于每一8译码规则错误概率为1错误概率为0译码规则错误概率为1错误概率为09译码规则二元对称信道错误概率为0.99错误概率下降为0.01译码规则二元对称信道错误概率为0.99错误概率下降为0.0110译码规则对于一个的传递矩阵，译码规则共有种在这么多种译码规则中，我们选择哪一种?当然希望译码后的错误概率越小越好.选择的标准是什么？译码规则对于一个的传递矩阵，译码规则共有11译码规则对于确定，制定译码函数译码错误的概率是译码正确的概率是称为条件错误概率

因为输出信号是个随机变量，只是其中一个符号定义平均错误概率译码规则对于确定，制定译码函数译码错误的概率是译码12译码规则

正确概率译码规则正确概率13译码规则技巧：一般都不直接求等输入概率情况下称为正确概率，而是先算然后用译码规则技巧：一般都不直接求等输入概率情况下称为正确概率，而14译码规则－例计算各种译码规则对应的平均差错概率

译码规则－例计算各种译码规则对应的平均差错概率15译码规则－例先计算译码正确的概率

对于规则一(F1)：

同理译码规则－例先计算译码正确的概率对于规则一(F1)：16最小错误概率准则平均错误概率定义后，一个很自然的准则就是使平均错误概率最小，即最小错误概率准则

平均错误概率是一个求和式，每一项都是非负的,如果每一项都为最小，则整个求和式最小.求和式的每一项,其中与译码规则无关使最小就是要使最大最小错误概率准则平均错误概率定义后，一个很自然的准则就是17最小错误概率准则即选择函数：并使之满足条件：即这种译码函数，它对于每一个输出符号均译成最大后验概率的那个输入符号，则信道错误概率就能最小，这种译码规则称为“最大后验概率译码准则”或“最小错误概率译码准则”最小错误概率准则即选择函数：并使之满足条件：即这种译码函18最小错误概率准则贝叶斯定律最大后验概率准则的条件式可以写成最小错误概率准则贝叶斯定律最大后验概率准则的条件式可以写成19最大似然准则输入符号等概率分布时，最大后验概率准则变成了最大似然准则不再依赖于输入符号的先验概率。在先验概率等概率分布时，最大似然准则与最大后验概率准则一致；在输入非等概率分布时，最大似然准则并不一定能使最小称为最大似然准则所以，最大似然准则不是最佳译码规则最大似然准则输入符号等概率分布时，最大后验概率准最大似20译码规则的选取最大后验概率准则依赖最大似然准则仅依赖先验概率等概率分布，使用最大后验概率准则和最大似然准则是一致的如果知道先验概率，应该使用最大后验概率准则如果不知道先验概率，则只能用最大似然准则译码规则的选取最大后验概率准则依赖21译码规则－例例：信道的传递概率矩阵求译码规则和平均错误概率1.输入等概率时2.3.用最大似然准则译码规则－例例：信道的传递概率矩阵22译码规则－例1.等概率分布时，用最大似然准则，等效于最大后验概率准则。对于传递矩阵中的每一列，选一个最大的传递概率，对应的输入符号即为该输出符号的译码函数译码规则－例1.等概率分布时，用最大似然准则，等效于23译码规则－例2.已知输入概率分布，用最大后验概率准则，求联合概率译码规则－例2.已知输入概率分布，用最大后验概率准24译码规则－例3.非等概率分布，但是规定要用最大似然准则可见在输入非等概率分布时，最大似然准则并不一定是最佳译码规则译码规则－例3.非等概率分布，但是规定要用最大似然准则可见在25课堂练习离散信道的传递概率矩阵为分别按照最小错误概率准则和最大似然准则确定译码规则，并计算相应的平均错误概率课堂练习离散信道的传递概率矩阵为26课堂练习、作业用最大后验概率准则，求联合概率课堂练习、作业用最大后验概率准则，求联合概率27课堂练习、作业用最大似然准则课堂练习、作业用最大似然准则28编码方法0.01的错误率在很多情况下难以容忍。一般来说，信息传输系统的平均差错率要求控制在10-6

以下，因此必须要进一步地降低错误概率：编码方法编码方法0.01的错误率在很多情况下难以容忍。一般29编码方法－增加扩展次数二元信源进行编码方法1：0；1方法2：000；111输入符号等概率分布，译码规则采用最大似然准则编码方法－增加扩展次数二元信源进行编码输入符号等概率分布，译30编码方法－增加扩展次数方法1：0；1方法2：000；111编码方法－增加扩展次数方法1：0；1方法2：000；11131编码方法－增加扩展次数用方法二，增加扩展次数可以降低错误概率结论1：M不变时，n越大，PE

越小，R也越小。编码方法－增加扩展次数用方法二，增加扩展次数可以降低错误概率32编码方法－减小输入符号数令n=3，M变化，看看此时和R的变化情况M=8时的情况：M=2时的情况：编码方法－减小输入符号数令n=3，M变化，看看此时和R的33编码方法－减小输入符号数M=8时的情况：编码方法－减小输入符号数M=8时的情况：34编码方法－减小输入符号数M=4时的情况，输入符号是：000、011、101、110编码方法－减小输入符号数M=4时的情况，输入符号是：35编码方法－减小输入符号数M=4时的情况，输入符号是：000、011、101、110编码方法－减小输入符号数M=4时的情况，输入符号是：36编码方法－减小输入符号数总结：当n=3不变，M变化时结论2：n不变时，M越大，PE越大，R也越大编码方法－减小输入符号数总结：当n=3不变，M变化时结论2：37编码方法－调整输入符号n一定，M也一定，选择不同的输入符号输入符号是000、001、010、100输入是000、011、101、110时编码方法－调整输入符号n一定，M也一定，选择不同的输入符号输38编码方法－调整输入符号第二种方式和第一种方式相比，信息传输率一样，平均错误概率更大结论3：n、M一定，选择不同的输入符号，

PE不同，R相等编码方法－调整输入符号第二种方式和第一种方式相比，信息传输率39编码方法－增大最小距离第一种：两两之间都有2个二元符号不同。一个二元符号出错，不会串扰到其它输入符号，因此可以判断出现了错误。第二种：000与其它输入符号之间只差一个二元符号，当000任何一个二元符号出现错误时，就会串扰到其它输入符号上，也就判断不出错误。编码方法－增大最小距离第一种：两两之间都有2个二元符号不40编码方法－增大最小距离为了描述符号序列之间的这种相差性，定义了汉明距离。长度为n的两个符号序列间的汉明距离是指两符号序列对应位置上不同码元的个数。用符号表示，简写为例如对应位置上有3个码元不同编码方法－增大最小距离为了描述符号序列之间的这种相差性，41编码方法－增大最小距离相应位置上的码元是否相同，在C语言中就是异或运算（相异为1，相同为0），所以汉明距离可以表示为：在码字集合中，共有M个码字，两两之间的汉明距离共有编码方法－增大最小距离相应位置上的码元是否相同，在C语言中就42编码方法－增大最小距离最小距离：任意两个码字的汉明距离的最小值，称为该码的最小距离M、n相同的情况下，越大，就越小对于不同的M和n，也有这样的准则编码方法－增大最小距离最小距离：任意两个码字的汉明距离的最小43编码方法－增大最小距离前面我们讲到的减小错误概率的方法，如M一定，增大n；n一定，减小M。本质上都是为了增大最小距离结论4（本质结论）：增大，就可以减小所以我们选择编码方法时，要使码字间的距离尽可能大编码方法－增大最小距离前面我们讲到的减小错误概率的方法，如44最小距离译码规则定义了汉明距离之后，又引入了一种译码规则：最小距离译码规则即选择译码函数：最小距离译码规则定义了汉明距离之后，又引入了一种译码规即选择45最小距离译码规则选择译码函数时不用计算传递概率，只用计算汉明距离F(000)=000 F(001)=000 F(010)=000F(011)=111 F(100)=000 F(101)=111F(110)=111 F(111)=111最小距离译码规则选择译码函数时不用计算传递概率，只用计F(046最小距离译码规则最小距离译码规则、最大似然准则都仅仅考虑了信道的统计特性，没有考虑输入序列的概率分布。两种译码规则有什么样的区别与联系呢？我们可以证明，在正常的二元对称信道上，两者是一致的，而在其他信道上则不一定。所谓正常的二元对称信道，指正确概率大于错误概率的二元对称信道最小距离译码规则最小距离译码规则、最大似然准则都仅仅考我们可47最小距离译码规则最小距离准则为：因为二元对称信道是离散无记忆信道，输出分量只与当前时刻的输入分量相关最大似然准则为：最小距离译码规则最小距离准则为：因为二元对称信道是离散无记忆48最小距离译码规则因此有：最小距离译码规则49最小距离译码规则对于正常的信道，有，正确概率大于错误概率

的幂数越高，则越大，也就是汉明距离D越小，越大最大似然准则和最小距离准则实现了统一最小距离译码规则50最小距离和纠错能力要纠正1位错误，要求码的最小距离一个码能够检测位错误的充要条件为：一个码能够纠正

位错误的充要条件为：一个码能够纠正个错误，同时又能检测出

位错误的充要条件为：要检测1位错误，要求码的最小距离最小距离和纠错能力要纠正1位错误，要求码的最小距离51课堂练习设某二元码为C={11100,01001,10010,00111}1、计算此码的最小距离2、计算此码的码率R，假设码字等概率分布3、采用最小距离译码准则，试问接收序列10000，01100和00100应译为什么码字4、此码能够纠正几位码元的错误？课堂练习设某二元码为C={11100,01001,10052练习、作业解：设练习、作业解：设53练习、作业练习、作业54有噪信道编码定理信息传输的可靠性和有效性之间，仿佛总是存在着冲突，提高了可靠性的同时，往往都会牺牲了有效性有没有一种解决方法，存在不存在一种编码方法，能够协调有效性和可靠性之间的冲突，在信息传输率R不降低的情况下，减小错误概率呢？香农第二定理，有噪信道编码定理很好的回答了这个问题有噪信道编码定理信息传输的可靠性和有效性之间，仿佛总55有噪信道编码定理香农第二定理：设离散无记忆信道X、Y分别代表输入、输出信号，是传递概率分布。当信息传输率时，只要码长n足够大，就存在着一种码和对应的译码规则，使译码后的错误概率任意小香农第二定理指出信道容量是保证无差错传输时，信息传输率的极限值有噪信道编码定理香农第二定理：设离散无记忆信道香农第二定理56有噪信道编码逆定理设离散无记忆信道，信道容量为C。当信息传输率时，无论码长n有多长，总也找不到一种编码，使平均错误概率任意小有噪信道编码逆定理设离散无记忆信道，57信道纠错编码的基本概念尽管早在1948年，香农就提出了关于在有噪信道中传输信息的重要理论，但是却没有明确的给出具体的编解码算法。之后