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

《第五章-信道编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《第五章-信道编码ppt课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、信息论基础 李富年 武汉科技大学第五章 有噪信道编码q 错误概率及相关因素 如何使信号经过传输后，错误概率最小q 信道编码定理 在有噪信道中，无差错传输的最大信息量有多大 q 线性分组码 实用编码范例信息论基础 李富年 武汉科技大学有噪信道编码信息论基础 李富年 武汉科技大学有噪信道编码n信源编码：有效性n信道编码：可靠性 10否是11100010111000 可以编码成 有效性： 更好 可靠性： 更好，提供纠错功能信息论基础 李富年 武汉科技大学有噪信道编码信息论基础 李富年 武汉科技大学错误概率及相关因素与以下三个因素有关：p 信道特性p 译码规则p 编码方法信息论基础 李富年 武汉科技大

2、学信道统计特性n 无噪无损信道：错误概率0n P=0.5的二元对称信道：错误概率50%1a2a2b1b111a2a2b1b0.50.50.50.5信息论基础 李富年 武汉科技大学译码规则)|()|()|()|()|()|()|()|()|(212222111211rsrrssabpabpabpabpabpabpabpabpabpraaa211b2bsb信息论基础 李富年 武汉科技大学译码规则“译码规则”：设计一个函数 ，对于每一个输出符号 ，确定唯一的输入符号 与之对应 )(jbFjb()1, 2jiFbajsia)|()|()|()|()|()|()|()|()|(212222111211r

3、srrssabpabpabpabpabpabpabpabpabpraaa211b2bsb信息论基础 李富年 武汉科技大学译码规则2211)()(abFabF1221)()(abFabF错误概率为1信息论基础 李富年 武汉科技大学译码规则二元对称信道1a2a2b1b0.010.010.990.992211)()(abFabF错误概率为0.991221)()(abFabF错误概率下降为0.01信息论基础 李富年 武汉科技大学译码规则对于一个 的传递矩阵，译码规则共有 种srsr在这么多种译码规则中，我们选择哪一种?当然希望译码后的错误概率越小越好.选择的标准是什么？)|()|()|()|()|()

4、|()|()|()|(212222111211rsrrssabpabpabpabpabpabpabpabpabpraaa211b2bsb信息论基础 李富年 武汉科技大学译码规则对于确定 ，制定译码函数jbijabF)(| )(1)|(1)|(jjjijbbFpbapbep| )()|(jjjibbFpbap jb1( )( | ( |)sjEjjjPp bE p ep e bb因为输出信号是个随机变量， 只是其中一个符号信息论基础 李富年 武汉科技大学译码规则 sjjjsjjjjsjjjjsjjsjjjjjsjjEbFbpbbFpbpbbFpbpbpbbFpbpbepbpP111111)(1|

5、 )()(1| )()()(| )(1)()|()(正确概率信息论基础 李富年 武汉科技大学译码规则技巧：一般都不直接求等输入概率情况下sjjjEbFbprP1)(|1EPEPEEPP 111()() |() sEjjjjsjjjPpbpFbbpbFb称为正确概率，而是先算然后用信息论基础 李富年 武汉科技大学译码规则例12()0.40.6XaaP X11322( ):( )FbaFFba12421( ):( )FbaFFba11121( ):( )F baFF ba12222( ):( )FbaFFba 计算各种译码规则对应的平均差错概率 信息论基础 李富年 武汉科技大学译码规则例2()0.

6、4EPF4()0.86EP F11()1()0.6EEP FP F 1121( )( )F baF ba 先计算译码正确的概率 11,11,21111121()()()()()(|)()(|)0.4 * 0.80.4 * 0.20.4sEjjjPFp b F bp a bp a bp ap bap ap ba 对于规则一(F1)： 3()0.14EP F 同理信息论基础 李富年 武汉科技大学最小错误概率准则 平均错误概率定义后，一个很自然的准则就是使平均错误概率最小，即最小错误概率准则 )|()()|(1jsjjjEbepbpbepEP 平均错误概率是一个求和式，每一项都是非负的,如果每一项都

7、为最小，则整个求和式最小.)|()(jjbepbp)(jbp| )(1)|(jjjbbFpbep)|(jbep| )(jjbbFp 求和式的每一项 ,其中 与译码规则无关使 最小就是要使 最大信息论基础 李富年 武汉科技大学最小错误概率准则 即选择函数：*()jFba并使之满足条件：*(|)(|)jijp abp ab 即这种译码函数，它对于每一个输出符号均译成最大后验概率的那个输入符号，则信道错误概率就能最小，这种译码规则称为“最大后验概率译码准则”或“最小错误概率译码准则”信息论基础 李富年 武汉科技大学最小错误概率准则贝叶斯定律)()|()()|(jijijibpabpapbap( *)

8、( | *)( )( | )( *)( |( * )*)( )( | )( )()jijijijijji jjp apb ap apb ap ap a bp abpb ap apb apbpb信息论基础 李富年 武汉科技大学最大似然准则 输入符号等概率分布时，最大后验概率准则变成了 )|(*)|(ijjabpabpEP 最大似然准则不再依赖于输入符号的先验概率。在先验概率等概率分布时，最大似然准则与最大后验概率准则一致；在输入非等概率分布时，最大似然准则并不一定能使 最小 信息论基础 李富年 武汉科技大学译码规则的选取最大后验概率准则依赖最大似然准则仅依赖)(XP)|(XYP)|(XYPn 先

9、验概率等概率分布，使用最大后验概率准则和最大似然准则是一致的n 如果知道先验概率，应该使用最大后验概率准则n 如果不知道先验概率，则只能用最大似然准则信息论基础 李富年 武汉科技大学译码规则例例：信道的传递概率矩阵求译码规则和平均错误概率1.输入等概率时2. 3. 用最大似然准则4 . 03 . 03 . 05 . 03 . 02 . 02 . 03 . 05 . 01a2a3a1b2b3b21)(41)(41)(321apapap21)(41)(41)(321apapap信息论基础 李富年 武汉科技大学译码规则例1.等概率分布时，用最大似然准则，等效于最大后验概率准则。对于传递矩阵中的每一列

10、，选一个最大的传递概率，对应的输入符号即为该输出符号的译码函数567. 01433. 0) 5 . 03 . 05 . 0 (31)|()|()|(31)()()()()()(233211322311233211EEEPPabpabpabpbapbapbapPabFabFabF信息论基础 李富年 武汉科技大学译码规则例2.已知输入概率分布，用最大后验概率准则，求联合概率)|()()(ijijiabpapbap333332313322322212311312111)(51)(81)(203)()(203)(403)(403)()(203)(201)(81)(abFbapbapbapbabFbap

11、bapbapbabFbapbapbapb对于对于对于5 . 015 . 051203203)()()(332313EEEPPbapbapbapP信息论基础 李富年 武汉科技大学译码规则例3.非等概率分布，但是规定要用最大似然准则6 . 014 . 08120381)()()()()()(322311233211EEEPPbapbapbapPabFabFabF信息论基础 李富年 武汉科技大学课堂练习离散信道的传递概率矩阵为分别按照最小错误概率准则和最大似然准则确定译码规则，并计算相应的平均错误概率41)(41)(21)(321xpxpxp信息论基础 李富年 武汉科技大学课堂练习、作业用最大后验概

12、率准则，求联合概率)|()()(ijijixypxpyxp333332313122322212111312111)(81)(121)(121)()(241)(81)(61)()(121)(241)(41)(xyFyxpyxpyxpyxyFyxpyxpyxpyxyFyxpyxpyxpy对于对于对于241112413816141)()()(332111EEEPPyxpyxpyxpP信息论基础 李富年 武汉科技大学课堂练习、作业用最大似然准则5 . 015 . 0818141)()()()()()(332211332211EEEPPyxpyxpyxpPxyFxyFxyF信息论基础 李富年 武汉科技大

13、学编码方法 0.01的错误率在很多情况下难以容忍。一般来说，信息传输系统的平均差错率要求控制在10-6 以下，因此必须要进一步地降低错误概率：编码方法信息论基础 李富年 武汉科技大学编码方法增加扩展次数二元信源进行编码n 方法1：0；1n 方法2：000；1110.99 0.010.010.990.01 0.99pp输入符号等概率分布，译码规则采用最大似然准则信息论基础 李富年 武汉科技大学编码方法增加扩展次数n 方法1：0；1210101. 0 pPE3222222332222223pppppppppppppppppppppppppppp000111000001010011100101110

14、111111011101110111000100010001000FF42231033)62(21pppppPEn 方法2：000；111信息论基础 李富年 武汉科技大学编码方法增加扩展次数用方法二，增加扩展次数可以降低错误概率0n10511109104710510875续变小，直到趋近于还会继，连续增大EEEEEPPnPnPnPnMlognMRn信道的传输速率（码率）（等概率分布）为输入消息（许用码字）的个数， 为编码后码字的长度91971751531311RnRnRnRnRn结论1：M不变时，n越大，PE 越小，R也越小。信息论基础 李富年 武汉科技大学编码方法减小输入符号数令n=3，M变

15、化，看看此时 和R的变化情况EP3332323232323232222223pppppppppppppppppppppppppppppppppp0001110000010100111001011101110010100111001011103/ 11034RPE信息论基础 李富年 武汉科技大学编码方法减小输入符号数M=8时的情况：3)(|81pbFbpPYjjE21031EEPP138loglognMR信息论基础 李富年 武汉科技大学编码方法减小输入符号数M=4时的情况，输入符号是：000、011、101、110ppppppppppppppppppppppppppppppppppppppppp

16、ppppppppppppppp23222232223223222223322232222223000000001010011100101110111011101110信息论基础 李富年 武汉科技大学编码方法减小输入符号数M=4时的情况，输入符号是：000、011、101、110)44(41)(|4123pppbFbpPYjjE21021EEPP3234loglognMR信息论基础 李富年 武汉科技大学编码方法减小输入符号数总结：当n=3不变，M变化时11038321024311032224RPMRPMRPMEEE结论2：n不变时，M越大，PE 越大，R也越大信息论基础 李富年 武汉科技大学编码

17、方法调整输入符号n一定，M也一定，选择不同的输入符号22233222223223222322223232222223pppppppppppppppppppppppppppppppppppppppppppppppppppppppp0000000010100111001011101110010101002102EP32R信息论基础 李富年 武汉科技大学编码方法调整输入符号第二种方式和第一种方式相比，信息传输率一样，平均错误概率更大)34(41)(|41223pppppbFbpPYjjE21023. 21EEPP3234loglognMR结论3：n、M一定，选择不同的输入符号， PE不同，R相等信息

18、论基础 李富年 武汉科技大学编码方法增大最小距离 第一种：两两之间都有2个二元符号不同。一个二元符号出错，不会串扰到其它输入符号，因此可以判断出现了错误 。 第二种：000与其它输入符号之间只差一个二元符号，当000任何一个二元符号出现错误时，就会串扰到其它输入符号上，也就判断不出错误。000011101110000001010100信息论基础 李富年 武汉科技大学编码方法增大最小距离 为了描述符号序列之间的这种相差性，定义了汉明距离。)()(2121jnjjjiniii)(jiDijD长度为n的两个符号序列 间的汉明距离是指两符号序列对应位置上不同码元的个数。用符号 表示，简写为111100

19、101111ji例如3)(jiD信息论基础 李富年 武汉科技大学编码方法增大最小距离相应位置上的码元是否相同，在C语言中就是异或运算（相异为1，相同为0），所以汉明距离可以表示为：nkjkikjiD1)(2) 1(2MMCM信息论基础 李富年 武汉科技大学编码方法增大最小距离最小距离：任意两个码字的汉明距离的最小值，称为该码的最小距离)(minminjiDdmindEPM、n相同的情况下， 越大， 就越小对于不同的M和n，也有这样的准则信息论基础 李富年 武汉科技大学编码方法增大最小距离 前面我们讲到的减小错误概率的方法，如M一定，增大n；n一定，减小M。本质上都是为了增大最小距离mindEP

20、结论4（本质结论）：增大 ，就可以减小 信息论基础 李富年 武汉科技大学最小距离译码规则定义了汉明距离之后，又引入了一种译码规则：最小距离译码规则),()*,(*)(jijjDDF满足信息论基础 李富年 武汉科技大学最小距离译码规则选择译码函数时不用计算传递概率，只用计算汉明距离0112122332212110000111000 001 010 011 100 101 110 111F(000)=000F(001)=000F(010)=000F(011)=111F(100)=000F(101)=111F(110)=111F(111)=111信息论基础 李富年 武汉科技大学最小距离译码规则最小距

21、离译码规则、最大似然准则都仅仅考虑了信道的统计特性，没有考虑输入序列的概率分布。两种译码规则有什么样的区别与联系呢？信息论基础 李富年 武汉科技大学最小距离译码规则最小距离准则为：),()*,(jijDD为二元符号序列、)|(*)|(ijjpp)|()|(2121nnijaaabbbpp)|()|()|()|(2211nnijabpabpabpp因为二元对称信道是离散无记忆信道，输出分量只与当前时刻的输入分量相关信息论基础 李富年 武汉科技大学最小距离译码规则因此有：pabpabpabpabkkkkkkkk)|()|(如果离即为两序列间的汉明距相同元素数目为，目为对应位置上不同元素数和序列DD

22、nDDnDijppp)|(信息论基础 李富年 武汉科技大学最小距离译码规则对于正常的信道，有 ，正确概率大于错误概率 的幂数越高， 则越大，也就是汉明距离D 越小， 越大最大似然准则和最小距离准则实现了统一 pp p)|(ijp)|(ijp信息论基础 李富年 武汉科技大学最小距离和纠错能力3mindn 要纠正1位错误，要求码的最小距离min1ddtn 一个码能够检测 位错误的充要条件为：dtmin21cdtn 一个码能够纠正 位错误的充要条件为：ctdtminmin211ccddtdtt和n 一个码能够纠正 个错误，同时又能检测出 位错误的充要条件为：ctn 要检测1位错误，要求码的最小距离2

23、mind信息论基础 李富年 武汉科技大学课堂练习设某二元码为C=11100, 01001, 10010, 001111、计算此码的最小距离2、计算此码的码率R，假设码字等概率分布3、采用最小距离译码准则，试问接收序列10000，01100和00100应译为什么码字4、此码能够纠正几位码元的错误？信息论基础 李富年 武汉科技大学练习、作业解：设00111 10010, 01001, 11100,432133);(3);(4);(4);(3);(3);(min434232413121dDDDDDD4 . 054loglognMR信息论基础 李富年 武汉科技大学练习、作业10010)10000(4)

24、10000;(1)10000;(3)10000;(2)10000;(4321FDDDD11100)01100(3)01100;(4)01100;(2)01100;(1)01100;(4321FDDDD001112)00100;(3)00100;(11100)00100(3)00100;(2)00100;(4321或DDFDD信息论基础 李富年 武汉科技大学有噪信道编码定理 信息传输的可靠性和有效性之间，仿佛总是存在着冲突，提高了可靠性的同时，往往都会牺牲了有效性 有没有一种解决方法，存在不存在一种编码方法，能够协调有效性和可靠性之间的冲突，在信息传输率R不降低的情况下，减小错误概率呢？ 香农第

25、二定理，有噪信道编码定理很好的回答了这个问题信息论基础 李富年 武汉科技大学有噪信道编码定理香农第二定理：设离散无记忆信道X、Y分别代表输入、输出信号， 是传递概率分布。当信息传输率 时，只要码长n足够大，就存在着一种码和对应的译码规则，使译码后的错误概率任意小 YxyPX),|(,)|(xyPCR 信息论基础 李富年 武汉科技大学有噪信道编码逆定理设离散无记忆信道 ，信道容量为C。当信息传输率 时，无论码长n有多长，总也找不到一种编码，使平均错误概率任意小YxyPX),|(,CR 信息论基础 李富年 武汉科技大学信道纠错编码的基本概念 尽管早在1948年，香农就提出了关于在有噪信道中传输信息

26、的重要理论，但是却没有明确的给出具体的编解码算法。 之后无数的科学技术工作者在香农第二定理的指导下进行了很多积极的实践和探索，总结出许多行之有效的编解码算法，从而逐步形成了一门技术学科纠错编码 在差错控制系统中按照纠错能力的不同，分为检错码和纠错码两种信息论基础 李富年 武汉科技大学线性分组码线性分组码的基本概念信息论基础 李富年 武汉科技大学线性分组码的基本概念分组码：每k个信息码元为一组，以一定的规律再生成r个校验码元，共同组成一个n=k+r个码元的码字线性码：信息码元和校验码元之间的是线性的关系。即校验码元的产生，是由各信息码元以线性的关系产生的信息论基础 李富年 武汉科技大学(7,4)

27、汉明码汉明码是重要的线性分组码，以（7，4）汉明码为例阐述汉明码的基本思想 为什么叫（7，4）汉明码？因为汉明码是分组码，每组码中有4个信息码元，编码后码长为7，包括4个信息码元和3个校验码元信息论基础 李富年 武汉科技大学(7,4)汉明码(7,4)汉明码有4个独立的码字，将这4个独立的码字组成如下47的矩阵，称为生成矩阵65431 0 0 0 0 1 10 1 0 0 1 0 10 0 1 0 1 1 00 0 0 1 1 1 1CCGCC)0011001(0011 G01234563456cccccccGcccc可以用生成矩阵G，从信息码元序列，生成汉明码字信道编码概念错误概率译码规则编码方法信道特性线性分组码最大后验概率准则最大似然准则