《信息论与编码（伴随式译码）ppt课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码（伴随式译码）ppt课件.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022年8月7日北京工商大学信息工程学院 信息论与编码1信息论与编码信息论与编码 曹雪虹曹雪虹 张宗橙张宗橙 编编 北京邮电大学出版社北京邮电大学出版社2022年8月7日2本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2022年8月7日3本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举
2、例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2022年8月7日45.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G)0110010(1R?mind例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：1.试由该矩阵指出（试由该矩阵指出（n,k）码的信息位）码的信息位k=?和监督元位数和监督元位数 r=?及码长及码长n=?2.求对应的校验矩阵求对应的校验矩阵H。3.若接收到一个若接收到一个7位码位码 ，
3、它是否码字？若不是它是否码字？若不是, 判断所发的码字。判断所发的码字。 4.问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。 5.该（该（n,k）码的许用码集中包含多少个码字？用列表的方式写出这些码）码的许用码集中包含多少个码字？用列表的方式写出这些码 字。字。 6.该（该（n,k）码的最小汉明距离）码的最小汉明距离 7.该（该（n,k）码的纠错能力为多少位？该（）码的纠错能力为多少位？该（n,k）码是不是极大最小距离）码是不是极大最小距离 码，为什么？该（码，为什么？该（n,k）码是完备码）码是完备码?为什么为什么?
4、2022年8月7日55.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码1000010000100001H解：解：1. 信息位信息位k=3，监督元位数，监督元位数 r=n-k=4，码长，码长n=7。 2. 101110011100100111001G)0110010(1R例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：1.试由该矩阵指出（试由该矩阵指出（n,k）码的信息位）码的信息位k=?和监督元位数和监督元位数 r=?及码长及码长n=?2.求对应的校验矩阵求对应的校验矩阵H。3.若接收到一个若接收到一个7位码位码 ， 它是否码字？若不是它是
5、否码字？若不是, 判断所发的码字。判断所发的码字。2022年8月7日65.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码1000110010001100101110001101H)0000() 1000(1THR解：解：1. 信息位信息位k=3，监督元位数，监督元位数 r=n-k=4，码长，码长n=7。 2. 3.所以所以R1不是码字。不是码字。 判断所发码字的方法？判断所发码字的方法？101110011100100111001G)0110010(1R例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：1.试由该矩阵指出（试由该矩阵指出（n,k
6、）码的信息位）码的信息位k=?和监督元位数和监督元位数 r=?及码长及码长n=?2.求对应的校验矩阵求对应的校验矩阵H。3.若接收到一个若接收到一个7位码位码 ， 它是否码字？若不是它是否码字？若不是, 判断所发的码字。判断所发的码字。2022年8月7日75.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G)0110010(1R?mind例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：1.试由该矩阵指出（试由该矩阵指出（n,k）码的信息位）码的信息位k=?和监督元位数和监督元位数 r=?及码长及码长
7、n=?2.求对应的校验矩阵求对应的校验矩阵H。3.若接收到一个若接收到一个7位码位码 ， 它是否码字？若不是它是否码字？若不是, 判断所发的码字。判断所发的码字。 4.问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。 5.该（该（n,k）码的许用码集中包含多少个码字？用列表的方式写出这些码）码的许用码集中包含多少个码字？用列表的方式写出这些码 字。字。 6.该（该（n,k）码的最小汉明距离）码的最小汉明距离 7.该（该（n,k）码的纠错能力为多少位？该（）码的纠错能力为多少位？该（n,k）码是不是极大最小距离）码是不是极大
8、最小距离 码，为什么？该（码，为什么？该（n,k）码是完备码）码是完备码?为什么为什么? 2022年8月7日85.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4. 伴随式有伴随式有 ，THES 得到得到8个伴随式的译码表为：个伴随式的译码表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4 ）错误图案错误图案Ei=（ e1 e2 e3 e4 e5 e6 e7 ）1000110010001100101110001101H2022年8月7
9、日95.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4. 伴随式有伴随式有 ，THES 得到得到8个伴随式的译码表为：个伴随式的译码表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4 ）错误图案错误图案Ei=（ e1 e2 e3 e4 e5 e6 e7 ）E1=0000000E2=0000001E3=0000010E4=0000100E5=0001000E6=0010000E7=0100000E8=10000001000110010
10、001100101110001101H2022年8月7日105.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4. 伴随式有伴随式有 ，THES 得到得到8个伴随式的译码表为：个伴随式的译码表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4 ）错误图案错误图案Ei=（ e1 e2 e3 e4 e5 e6 e7 ）E1=0000000E2=0000001E3=0000010E4=0000100E5=0001000E6=0010000E7
11、=0100000E8=10000001000110010001100101110001101H2022年8月7日115.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4. 伴随式有伴随式有 ，THES 得到得到8个伴随式的译码表为：个伴随式的译码表为：伴随式伴随式Si=（s1 s2 s3 s4 ）错误图案错误图案Ei=（ e1 e2 e3 e4 e5 e6 e7 ）S1=0000E1=0000000S2=0001E2=0000001S3=0010E3
12、=0000010S4=0100E4=0000100S5=1000E5=0001000S6=1101E6=0010000S7=0111E7=0100000S8=1110E8=10000002r=16个个由由1000110010001100101110001101HR1=(0 1 0 0 1 1 0)C1=(0 1 0 0 1 1 1)2022年8月7日125.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为： 5.该（该（n,k）码的许用码集中包含）码的许
13、用码集中包含 个码字，由个码字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3) 码字码字C=(c1 c2 c3 c4 c5 c6 c7)82022年8月7日135.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为： 5.该（该（n,k）码的许用码集中包含）码的许用码集中包含 个码字，由个码字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3) 码字码字C=(c1 c2 c3 c4 c5 c6
14、 c7)00000101010001110111011182022年8月7日145.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为： 5.该（该（n,k）码的许用码集中包含）码的许用码集中包含8个码字，由个码字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3) 码字码字C=(c1 c2 c3 c4 c5 c6 c7)00000000000010011101010010011110010011100110111010101
15、101001111011010011111110100R1=(0 1 0 0 1 1 0)C1=(0 1 0 0 1 1 1)2022年8月7日155.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4mind121intmindetc51minkndtiinknC02162kn80tiinC6、6. ，该（，该（n,k）码的纠错能力）码的纠错能力（n,k）码是极大最小距离码的条件为）码是极大最小距离码的条件为:7.（n,k）码是完备码的条件为：）码是
16、完备码的条件为：此题中此题中：该（该（n,k）码不是完备码。）码不是完备码。该（该（n,k）码不是极大最小距离码。）码不是极大最小距离码。1minknd此题中此题中：2022年8月7日16本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n期中考试卷分析期中考试卷分析n通知实验课时间安排通知实验课时间安排2022年8月7日17举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 1
17、. 汉明码概念汉明码概念汉明码是能纠正汉明码是能纠正单个错误单个错误的线性分组的线性分组码。如码。如(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)码等。码等。2022年8月7日18举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 2. (7,4) 汉明码的构造汉明码的构造1 1 1 0 1 0 0H=0 1 1 1 0 1 0
18、1 1 0 1 0 0 1I31 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1G=I42022年8月7日19举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 3. (7,4) 汉明码编码电路汉明码编码电路a6a5a4a3a2a1a0a6a5a4a3图图1 汉明编码器电路原理图汉明编码器电路原理图1 0 0 0 1 0 10 1 0 0 1110 0 1 0 11 00 0 0 1 0 11G=信息位（信息位（a6 a5 a4 a3),编码后先编码后先送出的是送出的是a6，依次是，依次是a5a0 2022年8
19、月7日20举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 4.(7,4) 汉明码译码电路汉明码译码电路1 1 1 0 1 0 0H=0 1 1 1 0 1 01 1 0 1 0 0 1图图2 汉明译码器电路原理图汉明译码器电路原理图 a a6 a a5 a a4 a a3 a a6 a a5 a a4 a a3 a a2 a a1 a a0 3-8 译译码码器器 校校正正子子生生成成 错错码码 指指示示 7654321 s1s2s3S=RHTR1=(1 0 0 1 1 0 1) 注注s是小写是小写1 0 0 0 1 0 10 1 0 0 1 1 10 0 1
20、0 1 1 00 0 0 1 0 1 1G=1 1 1 0 1 0 0H=0 1 1 1 0 1 01 1 0 1 0 0 1 4. (7,4) 汉明码译码电路汉明码译码电路2022年8月7日21举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 4.(7,4) 汉明码译码电路汉明码译码电路1 1 1 0 1 0 0H=0 1 1 1 0 1 01 1 0 1 0 0 1图图2 汉明译码器电路原理图汉明译码器电路原理图 a a6 a a5 a a4 a a3 a a6 a a5 a a4 a a3 a a2 a a1 a a0 3-8 译译码码器器 校校正正子子生
21、生成成 错错码码 指指示示 7654321 s1s2s3S=RHTR2=(0 1 1 0 1 1 1)1 0 0 0 1 0 10 1 0 0 11 10 0 1 0 11 00 0 0 1 0 11G=1 1 1 0 1 0 0H=0 1 1 1 0 1 01 1 0 1 0 0 1 4. (7,4) 汉明码译码电路汉明码译码电路CBA2022年8月7日22举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 5. (7,4) 汉明码系统编码前后结果汉明码系统编码前后结果010110001011 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1
22、1 00 0 0 1 0 1 1G=f=16KHz输出时钟输出时钟=输出数据速率输出数据速率=编码后编码后56Kbps56KHz输入时钟输入时钟=输入数据速率输入数据速率=编码前编码前32Kbps32KHz2022年8月7日23举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 6. (7,4) 汉明码系统译码前后结果汉明码系统译码前后结果001110100111 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1G=2022年8月7日24举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现
23、方法 7. (7,4) 汉明编码模块电路功能组成框图汉明编码模块电路功能组成框图2022年8月7日25举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 8. (7,4) 汉明译码模块电路功能组成框图汉明译码模块电路功能组成框图2022年8月7日26举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 9. (7,4) 汉明纠错编码综合通信综合系统汉明纠错编码综合通信综合系统 交交换换处处理理模模块块 DTMF检检测测1 DTMF检检测测2 电电话话接接口口 1 话话音音 编编解解码码1 话话音音 编编解解码码2 电电话话接接口口 2
24、传传输输信信道道 汉汉明明 编编码码 汉汉明明 译译码码 2# 1# 2022年8月7日27本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2022年8月7日28第五章（信道编码）总结第五章（信道编码）总结n信道模型与信道容量信道模型与信道容量n错误概率与编码方法错误概率与编码方法n错误概率与译码准则错误概率与译码准则n有扰离散信道的编码定理有扰离散信道的编码定理n差错
25、控制与信道编译码的基本原理差错控制与信道编译码的基本原理n线性分组码线性分组码n卷积码卷积码 最大后验概率译码准则最大后验概率译码准则最佳似然译码准则最佳似然译码准则差错控制的途径差错控制的途径2022年8月7日29第五章（信道编码）总结第五章（信道编码）总结-回顾通信系统的模型回顾通信系统的模型n完整的通信系统模型在信源编码器输出（或加密后）的代码组上在信源编码器输出（或加密后）的代码组上有目的地增加一些监督码元，使之具有检错有目的地增加一些监督码元，使之具有检错或纠错的能力或纠错的能力增加系统的可靠性增加系统的可靠性把信源发出的消息变换成由二进制码把信源发出的消息变换成由二进制码元组成的代
26、码组以提高通信系统传输元组成的代码组以提高通信系统传输消息的效率消息的效率增加系统的有效性增加系统的有效性2022年8月7日30第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例2 设信源输出两种消息，分别用设信源输出两种消息，分别用0、1表示，将其直接接表示，将其直接接入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则采取何种措施可增加通信系统的可靠性。采取何种措施可增加通信系统的可靠性。 解：解： 信息序列信息序列 码字码字 （m1） (c1) 0 0 1 1结论结
27、论：有噪信道不具有抗干扰能力，可在信息序列后加一有噪信道不具有抗干扰能力，可在信息序列后加一些冗余位以增加系统可靠性。些冗余位以增加系统可靠性。 二进制对称信道二进制对称信道2022年8月7日31第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例3 设设(N,K)分组码信息序列长度分组码信息序列长度k=1,编码后码长编码后码长N=3，冗余位冗余位r=2.ci与与mi的函数关系为的函数关系为 c1=m1， c2=m1， c3=m1问有噪信道具有抗干扰能力吗？问有噪信道具有抗干扰能力吗？ 解：解： 信息序列信息序列 码字码
28、字 （m1） (c1 c2 c3) 0 1 0 0 01 1 1 2022年8月7日32第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例3为（为（3，1）重复码，其检错和纠错能力分析：）重复码，其检错和纠错能力分析：二进制对称信道二进制对称信道,简称为简称为BSC信道信道(0/1)(1/0)(1/1)(0/0)1p YXp YXpp YXp YXp 2022年8月7日33第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则三次扩展信道矩阵为（三次扩
29、展信道矩阵为（p=0.1,1-p=0.9）：）：3121212212121332121211212123900.1*900.1*900.1*900.1*900.1*900.1*900.10.10.1*900.1*900.1*900.1*900.1*900.1*9090111000111 110 101 011 100 010 001 000 .根据最大似然译码准则，得译码规则：根据最大似然译码准则，得译码规则：F(000)= F(001)= F(010)= F(100)=000F(111)= F(011)= F(101)= F(110)=1112022年8月7日34xyz第五章（信道编码）总结
30、第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则总结：总结：本题为（本题为（3，1）重复码，）重复码， 检错能力检错能力2位；纠错能位；纠错能力力1位。位。N越大，抗扰能力越强，但越大，抗扰能力越强，但码率码率R=K/N越低。越低。110000010100101001011111z000010100101001011111000010100101001011111000010100101001011111110000010100101001011111000010100101001011111000010100101001011111xyzx
31、yzxyzxyz2022年8月7日35第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与译错误概率与编码方法、错误概率与译码准则码准则问题思考：问题思考：本例中本例中(3,1)重复码经重复码经BSC信道后采用最信道后采用最大似然译码原则译码时平均错译概率是多少？通信可大似然译码原则译码时平均错译概率是多少？通信可靠性较不编码有无提高？靠性较不编码有无提高？2022年8月7日36本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排