信息论与编码（伴随式译码）ppt课件

信息论与编码信息论与编码 曹雪虹曹雪虹 张宗橙张宗橙 编编 北京邮电大学出版社北京邮电大学出版社2024/5/61北京工商大学信息工程学院 信息论与编码信息论与编码 曹雪虹 本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2024/5/62本次课主要内容5.4.3 线性分组码的生成矩阵、校验矩阵、伴本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2024/5/63本次课主要内容5.4.3 线性分组码的生成矩阵、校验矩阵、伴5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：1.试由由该矩矩阵指出（指出（n,k）码的信息位的信息位k=?和和监督元位数督元位数 r=?及及码长n=?2.求求对应的校的校验矩矩阵H。3.若接收到一个若接收到一个7位位码，它是否码字？若不是它是否码字？若不是,4.判断所发的码字。判断所发的码字。4.问其伴随式有多少个？写出其伴随式有多少个？写出该分分组码对应一半伴随式数目的一半伴随式数目的译码表。表。5.该（n,k）码的的许用用码集中包含多少个集中包含多少个码字？用列表的方式写出字？用列表的方式写出这些些码 字。字。6.该（n,k）码的最小的最小汉明距离明距离 7.该（n,k）码的的纠错能力能力为多少位？多少位？该（n,k）码是不是极大最小距离是不是极大最小距离 码，为什么？什么？该（n,k）码是完是完备码?为什么什么?2024/5/645.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码解：解：1.信息位信息位k=3，监督元位数督元位数 r=n-k=4，码长n=7。2.例例1 若若线性分性分组码生成矩生成矩阵为：1.试由由该矩矩阵指出（指出（n,k）码的信息位的信息位k=?和和监督元位数督元位数 r=?及及码长n=?2.求求对应的校的校验矩矩阵H。3.若接收到一个若接收到一个7位位码，它是否码字？若不是它是否码字？若不是,4.判断所发的码字。判断所发的码字。2024/5/655.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码解：15.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码解：解：1.信息位信息位k=3，监督元位数督元位数 r=n-k=4，码长n=7。2.3.所以所以R1不是不是码字。字。判断所判断所发码字的方法？字的方法？例例1 若若线性分性分组码生成矩生成矩阵为：1.试由由该矩矩阵指出（指出（n,k）码的信息位的信息位k=?和和监督元位数督元位数 r=?及及码长n=?2.求求对应的校的校验矩矩阵H。3.若接收到一个若接收到一个7位位码，它是否码字？若不是它是否码字？若不是,4.判断所发的码字。判断所发的码字。2024/5/665.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码解：15.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：1.试由由该矩矩阵指出（指出（n,k）码的信息位的信息位k=?和和监督元位数督元位数 r=?及及码长n=?2.求求对应的校的校验矩矩阵H。3.若接收到一个若接收到一个7位位码，它是否码字？若不是它是否码字？若不是,4.判断所发的码字。判断所发的码字。4.问其伴随式有多少个？写出其伴随式有多少个？写出该分分组码对应一半伴随式数目的一半伴随式数目的译码表。表。5.该（n,k）码的的许用用码集中包含多少个集中包含多少个码字？用列表的方式写出字？用列表的方式写出这些些码 字。字。6.该（n,k）码的最小的最小汉明距离明距离 7.该（n,k）码的的纠错能力能力为多少位？多少位？该（n,k）码是不是极大最小距离是不是极大最小距离 码，为什么？什么？该（n,k）码是完是完备码?为什么什么?2024/5/675.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：4.伴随式有伴随式有 ，得到得到8个伴随式的个伴随式的译码表表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4）错误图案案Ei=（e1 e2 e3 e4 e5 e6 e7）2024/5/685.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：4.伴随式有伴随式有 ，得到得到8个伴随式的个伴随式的译码表表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4）错误图案案Ei=（e1 e2 e3 e4 e5 e6 e7）E1=0000000E2=0000001E3=0000010E4=0000100E5=0001000E6=0010000E7=0100000E8=10000002024/5/695.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：4.伴随式有伴随式有 ，得到得到8个伴随式的个伴随式的译码表表为：2r=16个个由由伴随式伴随式Si=（s1 s2 s3 s4）错误图案案Ei=（e1 e2 e3 e4 e5 e6 e7）E1=0000000E2=0000001E3=0000010E4=0000100E5=0001000E6=0010000E7=0100000E8=10000002024/5/6105.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：4.伴随式有伴随式有 ，得到得到8个伴随式的个伴随式的译码表表为：伴随式伴随式Si=（s1 s2 s3 s4）错误图案案Ei=（e1 e2 e3 e4 e5 e6 e7）S1=0000E1=0000000S2=0001E2=0000001S3=0010E3=0000010S4=0100E4=0000100S5=1000E5=0001000S6=1101E6=0010000S7=0111E7=0100000S8=1110E8=10000002r=16个个由由R1=(0 1 0 0 1 1 0)C1=(0 1 0 0 1 1 1)2024/5/6115.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：5.该（n,k）码的的许用用码集中包含集中包含 个个码字，由字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3)码字字C=(c1 c2 c3 c4 c5 c6 c7)82024/5/6125.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：5.该（n,k）码的的许用用码集中包含集中包含 个个码字，由字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3)码字字C=(c1 c2 c3 c4 c5 c6 c7)00000101010001110111011182024/5/6135.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：5.该（n,k）码的的许用用码集中包含集中包含8个个码字，由字，由C=M*G得到，如下表。得到，如下表。信息序列信息序列M=(m1 m2 m3)码字字C=(c1 c2 c3 c4 c5 c6 c7)00000000000010011101010010011110010011100110111010101101001111011010011111110100R1=(0 1 0 0 1 1 0)C1=(0 1 0 0 1 1 1)2024/5/6145.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 5.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码线性分组码的生成矩阵、校验矩阵、伴随式译码例例1 若若线性分性分组码生成矩生成矩阵为：6、6.，该（n,k）码的的纠错能力能力（n,k）码是极大最小距离是极大最小距离码的条件的条件为:7.（n,k）码是完是完备码的条件的条件为：此此题中中：该（n,k）码不是完不是完备码。该（n,k）码不是极大最小距离不是极大最小距离码。此此题中中：2024/5/6155.4.3 线性分组码的生成矩阵、校验矩阵、伴随式译码例1 本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n期中考试卷分析期中考试卷分析n通知实验课时间安排通知实验课时间安排2024/5/616本次课主要内容5.4.3 线性分组码的生成矩阵、校验矩阵、伴举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 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)码等。码等。2024/5/617举例说明信道编译码在实际应用中的实现方法 1.汉明码举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 2.(7,4)汉明码的构造汉明码的构造I3I42024/5/618举例说明信道编译码在实际应用中的实现方法 2.(7,4)举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 3.(7,4)汉明码编码电路汉明码编码电路图1 汉明明编码器器电路原理路原理图信息位（信息位（a6 a5 a4 a3),编码后先编码后先送出的是送出的是a6，依次是，依次是a5a0 2024/5/619举例说明信道编译码在实际应用中的实现方法 3.(7举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 4.(7,4)汉明码译码电路汉明码译码电路图2 汉明明译码器器电路原理路原理图 s1s2s3S=RHTR1=(1 0 0 1 1 0 1)注注s是小写是小写 4.(7,4)汉明码译码电路汉明码译码电路2024/5/620举例说明信道编译码在实际应用中的实现方法 4.(7,举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 4.(7,4)汉明码译码电路汉明码译码电路图2 汉明明译码器器电路原理路原理图 s1s2s3S=RHTR2=(0 1 1 0 1 1 1)4.(7,4)汉明码译码电路汉明码译码电路CBA2024/5/621举例说明信道编译码在实际应用中的实现方法 4.(7,举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 5.(7,4)汉明码系统编码前后结果汉明码系统编码前后结果01011000101f=16KHz输出时钟输出时钟=输出数据速率输出数据速率=编码后编码后56Kbps56KHz输入时钟输入时钟=输入数据速率输入数据速率=编码前编码前32Kbps32KHz2024/5/622举例说明信道编译码在实际应用中的实现方法 5.(7举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 6.(7,4)汉明码系统译码前后结果汉明码系统译码前后结果001110100112024/5/623举例说明信道编译码在实际应用中的实现方法 6.(7举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 7.(7,4)汉明编码模块电路功能组成框图汉明编码模块电路功能组成框图2024/5/624举例说明信道编译码在实际应用中的实现方法 7.(7举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 8.(7,4)汉明译码模块电路功能组成框图汉明译码模块电路功能组成框图2024/5/625举例说明信道编译码在实际应用中的实现方法 8.(7举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法 9.(7,4)汉明纠错编码综合通信综合系统汉明纠错编码综合通信综合系统2024/5/626举例说明信道编译码在实际应用中的实现方法 9.(7本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2024/5/627本次课主要内容5.4.3 线性分组码的生成矩阵、校验矩阵、伴第五章（信道编码）总结第五章（信道编码）总结n信道模型与信道容量信道模型与信道容量n错误概率与编码方法错误概率与编码方法n错误概率与译码准则错误概率与译码准则n有扰离散信道的编码定理有扰离散信道的编码定理n差错控制与信道编译码的基本原理差错控制与信道编译码的基本原理n线性分组码线性分组码n卷积码卷积码 最大后验概率译码准则最大后验概率译码准则最佳似然译码准则最佳似然译码准则差错控制的途径差错控制的途径2024/5/628第五章（信道编码）总结信道模型与信道容量最大后验概率译码准则第五章（信道编码）总结第五章（信道编码）总结-回顾通信系统的模型回顾通信系统的模型n完整的通信系统模型在信源编码器输出（或加密后）的代码组上在信源编码器输出（或加密后）的代码组上有目的地增加一些监督码元，使之具有检错有目的地增加一些监督码元，使之具有检错或纠错的能力或纠错的能力增加系统的可靠性增加系统的可靠性把信源发出的消息变换成由二进制码把信源发出的消息变换成由二进制码元组成的代码组以提高通信系统传输元组成的代码组以提高通信系统传输消息的效率消息的效率增加系统的有效性增加系统的有效性2024/5/629第五章（信道编码）总结-回顾通信系统的模型在信源编码器输出（第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例2 设信源输出两种消息，分别用设信源输出两种消息，分别用0、1表示，将其直接接表示，将其直接接入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则入有噪信道，问有噪信道具有抗干扰能力吗？如没有，则采取何种措施可增加通信系统的可靠性。采取何种措施可增加通信系统的可靠性。解：解：信息序列信息序列 码字码字 （m1）(c1)0 0 1 1结论结论：有噪信道不具有抗干扰能力，可在信息序列后加一有噪信道不具有抗干扰能力，可在信息序列后加一些冗余位以增加系统可靠性。些冗余位以增加系统可靠性。二进制对称信道二进制对称信道2024/5/630第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例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 01 1 1 2024/5/631第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则例例3为（为（3，1）重复码，其检错和纠错能力分析：）重复码，其检错和纠错能力分析：二进制对称信道二进制对称信道,简称为简称为BSC信道信道2024/5/632第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则三次扩展信道矩阵为（三次扩展信道矩阵为（p=0.1,1-p=0.9）：）：根据最大似然译码准则，得译码规则：根据最大似然译码准则，得译码规则：F(000)=F(001)=F(010)=F(100)=000F(111)=F(011)=F(101)=F(110)=1112024/5/633第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准xyz第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与错误概率与编码方法、错误概率与译码准则译码准则总结：总结：本题为（本题为（3，1）重复码，）重复码，检错能力检错能力2位；纠错能位；纠错能力力1位。位。N越大，抗扰能力越强，但越大，抗扰能力越强，但码率码率R=K/N越低。越低。110000010100101001011111z000010100101001011111000010100101001011111000010100101001011111110000010100101001011111000010100101001011111000010100101001011111xyzxyzxyzxyz2024/5/634xyz第五章（信道编码）总结-错误概率与编码方法、错误概率与第五章（信道编码）总结第五章（信道编码）总结-错误概率与编码方法、错误概率与译错误概率与编码方法、错误概率与译码准则码准则问题思考：问题思考：本例中本例中(3,1)重复码经重复码经BSC信道后采用最信道后采用最大似然译码原则译码时平均错译概率是多少？通信可大似然译码原则译码时平均错译概率是多少？通信可靠性较不编码有无提高？靠性较不编码有无提高？2024/5/635第五章（信道编码）总结-错误概率与编码方法、错误概率与译码准本次课主要内容本次课主要内容n5.4.3 线性分组码的生成矩阵、校验矩阵、伴线性分组码的生成矩阵、校验矩阵、伴随式译码随式译码n举例说明信道编译码在实际应用中的实现方法举例说明信道编译码在实际应用中的实现方法n第五章内容总结第五章内容总结n通知实验课时间安排通知实验课时间安排2024/5/636本次课主要内容5.4.3 线性分组码的生成矩阵、校验矩阵、伴