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

1、信息论与编码信息论与编码 曹雪虹曹雪虹 张宗橙张宗橙 编编 北京邮电大学出版社北京邮电大学出版社2022年7月3日北京工商大学信息工程学院 信息论与编码1本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2022年7月3日 http:/ http:/ 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现

2、方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2022年7月3日35.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）码是完备码）码是完备码?为什么为什么? 2022年7月3日45.4.3 线

4、性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码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年7月3日55.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）码的信息位）码的信息位k=?和监

6、督元位数和监督元位数 r=?及码长及码长n=?2.求对应的校验矩阵求对应的校验矩阵H。3.若接收到一个若接收到一个7位码位码 ， 它是否码字？若不是它是否码字？若不是, 判断所发的码字。判断所发的码字。2022年7月3日65.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G)0110010(1R?mind例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：1.试由该矩阵指出（试由该矩阵指出（n,k）码的信息位）码的信息位k=?和监督元位数和监督元位数 r=?及码长及码长n=?2.求对应的校验矩阵求对应的

7、校验矩阵H。3.若接收到一个若接收到一个7位码位码 ， 它是否码字？若不是它是否码字？若不是, 判断所发的码字。判断所发的码字。 4.问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。 5.该（该（n,k）码的许用码集中包含多少个码字？用列表的方式写出这些码）码的许用码集中包含多少个码字？用列表的方式写出这些码 字。字。 6.该（该（n,k）码的最小汉明距离）码的最小汉明距离 7.该（该（n,k）码的纠错能力为多少位？该（）码的纠错能力为多少位？该（n,k）码是不是极大最小距离）码是不是极大最小距离 码，为什么？该（码，为什

8、么？该（n,k）码是完备码）码是完备码?为什么为什么? 2022年7月3日75.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4. 伴随式有伴随式有 ，THES 得到得到8个伴随式的译码表为：个伴随式的译码表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4 ）错误图案错误图案Ei=（ e1 e2 e3 e4 e5 e6 e7 ）1000110010001100101110001101H2022年7月3日85.4.3 线性分组码的生成矩

9、阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码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=1000000100011001000110010111000110

10、1H2022年7月3日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=1000000

11、1000110010001100101110001101H2022年7月3日105.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=0000010S4=0100E4=

12、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年7月3日115.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为： 5.该（该（n,k）码的许用码集中包含）码的许用码集中包含 个码字，由个码字，由C

13、=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3) 码字码字C=(c1 c2 c3 c4 c5 c6 c7)82022年7月3日125.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为： 5.该（该（n,k）码的许用码集中包含）码的许用码集中包含 个码字，由个码字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3) 码字码字C=(c1 c2 c3 c4 c5 c6 c7)00000101010001

14、110111011182022年7月3日135.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为： 5.该（该（n,k）码的许用码集中包含）码的许用码集中包含8个码字，由个码字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3) 码字码字C=(c1 c2 c3 c4 c5 c6 c7)00000000000010011101010010011110010011100110111010101101001111011010011

15、111110100R1=(0 1 0 0 1 1 0)C1=(0 1 0 0 1 1 1)2022年7月3日145.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例例1 若线性分组码生成矩阵为：若线性分组码生成矩阵为：4mind121intmindetc51minkndtiinknC02162kn80tiinC6、6. ，该（，该（n,k）码的纠错能力）码的纠错能力（n,k）码是极大最小距离码的条件为）码是极大最小距离码的条件为:7.（n,k）码是完备码的条件为：）码是完备码的条件为：此题中此题中：该（该

16、（n,k）码不是完备码。）码不是完备码。该（该（n,k）码不是极大最小距离码。）码不是极大最小距离码。1minknd此题中此题中：2022年7月3日15本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n期中考试卷分析期中考试卷分析n通知实验课时间安排通知实验课时间安排2022年7月3日16举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 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年7月3日17举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 2. (7,4) 汉明码的构造汉明码的构造1 1 1 0 1 0 0H=0 1 1 1 0 1 01 1 0 1 0 0 1I31 0

18、 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1G=I42022年7月3日18举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 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年7月3日19举例说明信道编译码在实际应

19、用中的实现方法举例说明信道编译码在实际应用中的实现方法 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 0 1 1 00 0 0 1 0 1

20、 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年7月3日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 译译码码器器 校校正正子子生生成成 错错码码 指指示示 7654

21、321 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年7月3日21举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 5. (7,4) 汉明码系统编码前后结果汉明码系统编码前后结果010110001011 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1G=

22、f=16KHz输出时钟输出时钟=输出数据速率输出数据速率=编码后编码后56Kbps56KHz输入时钟输入时钟=输入数据速率输入数据速率=编码前编码前32Kbps32KHz2022年7月3日22举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 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年7月3日23举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 7. (7,4) 汉明编码模块

23、电路功能组成框图汉明编码模块电路功能组成框图2022年7月3日24举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 8. (7,4) 汉明译码模块电路功能组成框图汉明译码模块电路功能组成框图2022年7月3日25举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 9. (7,4) 汉明纠错编码综合通信综合系统汉明纠错编码综合通信综合系统 交交换换处处理理模模块块 DTMF检检测测1 DTMF检检测测2 电电话话接接口口 1 话话音音 编编解解码码1 话话音音 编编解解码码2 电电话话接接口口 2 传传输输信信道道 汉汉明明 编编码码

24、 汉汉明明 译译码码 2# 1# 2022年7月3日26本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2022年7月3日27第五章（信道编码）总结第五章（信道编码）总结n信道模型与信道容量信道模型与信道容量n错误概率与编码方法错误概率与编码方法n错误概率与译码准则错误概率与译码准则n有扰离散信道的编码定理有扰离散信道的编码定理n差错控制与信道编译码的基本原理差错控制与

25、信道编译码的基本原理n线性分组码线性分组码n卷积码卷积码 最大后验概率译码准则最大后验概率译码准则最佳似然译码准则最佳似然译码准则差错控制的途径差错控制的途径2022年7月3日28第五章（信道编码）总结第五章（信道编码）总结-回顾通信系统的模型回顾通信系统的模型n完整的通信系统模型在信源编码器输出（或加密后）的代码组上在信源编码器输出（或加密后）的代码组上有目的地增加一些监督码元，使之具有检错有目的地增加一些监督码元，使之具有检错或纠错的能力或纠错的能力增加系统的可靠性增加系统的可靠性把信源发出的消息变换成由二进制码把信源发出的消息变换成由二进制码元组成的代码组以提高通信系统传输元组成的代码组

26、以提高通信系统传输消息的效率消息的效率增加系统的有效性增加系统的有效性2022年7月3日29第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例2 设信源输出两种消息，分别用设信源输出两种消息，分别用0、1表示，将其直接接表示，将其直接接入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则采取何种措施可增加通信系统的可靠性。采取何种措施可增加通信系统的可靠性。 解：解： 信息序列信息序列 码字码字 （m1） (c1) 0 0 1 1结论结论：有噪信道不具有抗干扰能力，可在信

27、息序列后加一有噪信道不具有抗干扰能力，可在信息序列后加一些冗余位以增加系统可靠性。些冗余位以增加系统可靠性。 二进制对称信道二进制对称信道2022年7月3日30第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例3 设设(N,K)分组码信息序列长度分组码信息序列长度k=1,编码后码长编码后码长N=3，冗余位冗余位r=2.ci与与mi的函数关系为的函数关系为 c1=m1， c2=m1， c3=m1问有噪信道具有抗干扰能力吗？问有噪信道具有抗干扰能力吗？ 解：解： 信息序列信息序列 码字码字 （m1） (c1 c2 c3)

28、0 1 0 0 01 1 1 2022年7月3日31第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例3为（为（3，1）重复码，其检错和纠错能力分析：）重复码，其检错和纠错能力分析：二进制对称信道二进制对称信道,简称为简称为BSC信道信道(0/1)(1/0)(1/1)(0/0)1p YXp YXpp YXp YXp 2022年7月3日32第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则三次扩展信道矩阵为（三次扩展信道矩阵为（p=0.1,1-p=0.