信息论与编码(伴随式译码).ppt

2020年7月6日,北京工商大学信息工程学院 信息论与编码,1,信息论与编码,曹雪虹 张宗橙 编 北京邮电大学出版社,2020年7月6日,2,本次课主要内容,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码 举例说明信道编译码在实际应用中的实现方法 第五章内容总结 通知实验课时间安排,2020年7月6日,3,本次课主要内容,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码 举例说明信道编译码在实际应用中的实现方法 第五章内容总结 通知实验课时间安排,2020年7月6日,4,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,试由该矩阵指出（n,k）码的信息位k=?和监督元位数 r=?及码长n=? 求对应的校验矩阵H。 若接收到一个7位码 ， 它是否码字？若不是, 判断所发的码字。,4.问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。 5.该（n,k）码的许用码集中包含多少个码字？用列表的方式写出这些码 字。 6.该（n,k）码的最小汉明距离,7.该（n,k）码的纠错能力为多少位？该（n,k）码是不是极大最小距离 码，为什么？该（n,k）码是完备码?为什么?,2020年7月6日,5,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,解：1. 信息位k=3，监督元位数 r=n-k=4，码长n=7。 2.,例1 若线性分组码生成矩阵为：,试由该矩阵指出（n,k）码的信息位k=?和监督元位数 r=?及码长n=? 求对应的校验矩阵H。 若接收到一个7位码 ， 它是否码字？若不是, 判断所发的码字。,2020年7月6日,6,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,解：1. 信息位k=3，监督元位数 r=n-k=4，码长n=7。 2.,3.,所以R1不是码字。 判断所发码字的方法？,例1 若线性分组码生成矩阵为：,试由该矩阵指出（n,k）码的信息位k=?和监督元位数 r=?及码长n=? 求对应的校验矩阵H。 若接收到一个7位码 ， 它是否码字？若不是, 判断所发的码字。,2020年7月6日,7,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,试由该矩阵指出（n,k）码的信息位k=?和监督元位数 r=?及码长n=? 求对应的校验矩阵H。 若接收到一个7位码 ， 它是否码字？若不是, 判断所发的码字。,4.问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。 5.该（n,k）码的许用码集中包含多少个码字？用列表的方式写出这些码 字。 6.该（n,k）码的最小汉明距离,7.该（n,k）码的纠错能力为多少位？该（n,k）码是不是极大最小距离 码，为什么？该（n,k）码是完备码?为什么?,2020年7月6日,8,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,4. 伴随式有 ，,得到8个伴随式的译码表为：,2r=16个,由,2020年7月6日,9,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,4. 伴随式有 ，,得到8个伴随式的译码表为：,2r=16个,由,2020年7月6日,10,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,4. 伴随式有 ，,得到8个伴随式的译码表为：,2r=16个,由,2020年7月6日,11,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,4. 伴随式有 ，,得到8个伴随式的译码表为：,2r=16个,由,R1=(0 1 0 0 1 1 0),C1=(0 1 0 0 1 1 1),2020年7月6日,12,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,5.该（n,k）码的许用码集中包含 个码字，由C=M*G得到，如下表。,8,2020年7月6日,13,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,5.该（n,k）码的许用码集中包含 个码字，由C=M*G得到，如下表。,8,2020年7月6日,14,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,5.该（n,k）码的许用码集中包含8个码字，由C=M*G得到，如下表。,R1=(0 1 0 0 1 1 0),C1=(0 1 0 0 1 1 1),2020年7月6日,15,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码,例1 若线性分组码生成矩阵为：,6、,6. ，该（n,k）码的纠错能力,（n,k）码是极大最小距离码的条件为:,7.（n,k）码是完备码的条件为：,此题中：,该（n,k）码不是完备码。,该（n,k）码不是极大最小距离码。,此题中：,2020年7月6日,16,本次课主要内容,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码 举例说明信道编译码在实际应用中的实现方法 第五章内容总结 期中考试卷分析 通知实验课时间安排,2020年7月6日,17,举例说明信道编译码在实际应用中的实现方法,1. 汉明码概念汉明码是能纠正单个错误的线性分组码。如(n,k)码，它有以下特点： 码长 n=2m-1 信息码位 k=2m-m-1 监督码位 r=m=n-k 最小码距 d=3 纠错能力 t=1 这里m是正整数，m2。如(3,1)码、(7,4)码、(15,11)码等。,2020年7月6日,18,举例说明信道编译码在实际应用中的实现方法,2. (7,4) 汉明码的构造,I3,I4,2020年7月6日,19,举例说明信道编译码在实际应用中的实现方法,3. (7,4) 汉明码编码电路,图1 汉明编码器电路原理图,信息位（a6 a5 a4 a3),编码后先送出的是a6，依次是a5a0,2020年7月6日,20,举例说明信道编译码在实际应用中的实现方法,4.(7,4) 汉明码译码电路,图2 汉明译码器电路原理图,s1,s2,s3,S=RHT,R1=(1 0 0 1 1 0 1),注s是小写,4. (7,4) 汉明码译码电路,2020年7月6日,21,举例说明信道编译码在实际应用中的实现方法,4.(7,4) 汉明码译码电路,图2 汉明译码器电路原理图,s1,s2,s3,S=RHT,R2=(0 1 1 0 1 1 1),4. (7,4) 汉明码译码电路,C B A,2020年7月6日,22,举例说明信道编译码在实际应用中的实现方法,5. (7,4) 汉明码系统编码前后结果,0101100,0101,f=16KHz,输出时钟=,输出数据速率=,编码后,56Kbps,56KHz,输入时钟=,输入数据速率=,编码前,32Kbps,32KHz,2020年7月6日,23,举例说明信道编译码在实际应用中的实现方法,6. (7,4) 汉明码系统译码前后结果,0011101,0011,2020年7月6日,24,举例说明信道编译码在实际应用中的实现方法,7. (7,4) 汉明编码模块电路功能组成框图,2020年7月6日,25,举例说明信道编译码在实际应用中的实现方法,8. (7,4) 汉明译码模块电路功能组成框图,2020年7月6日,26,举例说明信道编译码在实际应用中的实现方法,9. (7,4) 汉明纠错编码综合通信综合系统,2020年7月6日,27,本次课主要内容,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码 举例说明信道编译码在实际应用中的实现方法 第五章内容总结 通知实验课时间安排,2020年7月6日,28,第五章（信道编码）总结,信道模型与信道容量 错误概率与编码方法 错误概率与译码准则 有扰离散信道的编码定理 差错控制与信道编译码的基本原理 线性分组码 卷积码,最大后验概率译码准则 最佳似然译码准则,差错控制的途径,2020年7月6日,29,第五章（信道编码）总结-回顾通信系统的模型,完整的通信系统模型,在信源编码器输出（或加密后）的代码组上有目的地增加一些监督码元，使之具有检错或纠错的能力增加系统的可靠性,把信源发出的消息变换成由二进制码元组成的代码组以提高通信系统传输消息的效率增加系统的有效性,2020年7月6日,30,第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准则,例2 设信源输出两种消息，分别用0、1表示，将其直接接入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则采取何种措施可增加通信系统的可靠性。,解： 信息序列 码字 （m1） (c1) 0 0 1 1 结论：有噪信道不具有抗干扰能力，可在信息序列后加一些冗余位以增加系统可靠性。,二进制对称信道,2020年7月6日,31,第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准则,例3 设(N,K)分组码信息序列长度k=1,编码后码长N=3，冗余位r=2.ci与mi的函数关系为 c1=m1， c2=m1， c3=m1问有噪信道具有抗干扰能力吗？,解： 信息序列 码字 （m1） (c1 c2 c3) 0 1,0 0 0 1 1 1,2020年7月6日,32,第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准则,例3为（3，1）重复码，其检错和纠错能力分析：,二进制对称信道,简称为BSC信道,2020年7月6日,33,第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准则,三次扩展信道矩阵为（p=0.1,1-p=0.9）：,根据最大似然译码准则，得译码规则：,F(000)= F(001)= F(010)= F(100)=000 F(111)= F(011)= F(101)= F(110)=111,2020年7月6日,34,第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准则,总结：本题为（3，1）重复码， 检错能力2位；纠错能力1位。N越大，抗扰能力越强，但码率R=K/N越低。,110,z,110,2020年7月6日,35,第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准则,问题思考：本例中(3,1)重复码经BSC信道后采用最大似然译码原则译码时平均错译概率是多少？通信可靠性较不编码有无提高？,2020年7月6日,36,本次课主要内容,5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码 举例说明信道编译码在实际应用中的实现方法 第五章内容总结 通知实验课时间安排,