第11章差错控制编码电信课件.ppt

1、 电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉 通信原理通信原理第第11章章 差错控制编码差错控制编码本章知识点本章知识点:1、了解差错控制技术种类、了解差错控制技术种类 2、掌握纠错编码原理、最小码距和检错、纠错、掌握纠错编码原理、最小码距和检错、纠错之间关系；了解奇偶监督码、恒比码编码方法。之间关系；了解奇偶监督码、恒比码编码方法。3、掌握线性分组码编码和译码方法、掌握线性分组码编码和译码方法 4、掌握循环码编码和译码方法、掌握循环码编码和译码方法 电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉 通信原理通信原理11.111.1 概述概

2、述11.211.2 纠错编码的基本原理纠错编码的基本原理11.311.3 纠错编码的性能纠错编码的性能11.411.4 简单的实用编码简单的实用编码11.511.5 线性分组码线性分组码11.611.6 循环码循环码11.711.7 卷积码卷积码11.811.8 Turbo Turbo码码11.911.9 低密度奇偶校验码低密度奇偶校验码11.1011.10 网格编码调制网格编码调制11.1111.11 小结小结第第11章章 差错控制编码差错控制编码电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2

3、月月7日日3 为保证运送途中不出现打碎灯泡的情况有效性 可靠性 11.1 概述概述电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4n 通信中的情况：针对乘性针对加性合理选择调制/解调方法，增大发射功率采用等措施11.1 概述概述电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日511.1 概述概述n 差错控制编码电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会

4、玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日611.1 概述概述信道分类信道分类(从差错控制角度看从差错控制角度看)：随机信道：错码的出现是随机的。随机信道：错码的出现是随机的。突发信道：错码是成串集中出现的。突发信道：错码是成串集中出现的。混合信道：既存在随机错码又存在突发错码。混合信道：既存在随机错码又存在突发错码。差错控制技术的种类：差错控制技术的种类：检错重发检错重发前向纠错前向纠错反馈校验反馈校验检错删除检错删除信道编码分类：信道编码分类：线性码和非线性码线性码和非线性码分组码和卷积码分组码和卷积码系统码和非系统码系统码和非系统码电子与信息工

5、程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日711.1 概述概述不同的编码方法，有不同的不同的编码方法，有不同的检错检错或或纠错纠错能力。能力。多余度多余度：就是指增加的监督码元多少。例如，若编码序列中平：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余均每两个信息码元就添加一个监督码元，则这种编码的多余度为度为1/3。编码效率编码效率(简称简称码率码率)：设编码序列中信息码元数量为：设编码序列中信息码元数量为k，总码，总码元数量为元数量为n，则

6、比值，则比值k/n 就是码率。就是码率。冗余度冗余度：监督码元数监督码元数(n-k)和信息码元数和信息码元数 k 之比。之比。理论上，差错控制以降低信息传输速率为代价换取理论上，差错控制以降低信息传输速率为代价换取提高传输可提高传输可靠性靠性。监督码元监督码元：在在4种种差错控制差错控制技术中除第技术中除第3种外，都是在接收端识种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。差错控制码元，它们称为监督码元。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通

7、信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日811.2 纠错编码的基本原理纠错编码的基本原理1、分组码基本原理、分组码基本原理 将信息码分组，为每组信息码附加若干监督码的编码称将信息码分组，为每组信息码附加若干监督码的编码称为为分组码分组码。在分组码中，监督码元仅监督本码组中的信息。在分组码中，监督码元仅监督本码组中的信息码元。码元。卷积码卷积码又称连环码。卷积码编码器把又称连环码。卷积码编码器把k比特信息段编成比特信息段编成n比特的码组，但所编的比特的码组，但所编的n长码组不仅同当前的长码组不仅同当前的k比特信息段比特信息段有关，而且还同前面的有关，而且还同前面

8、的(N-1)个个(N1,整数整数)信息段有关联。信息段有关联。分组码分组码卷积码卷积码电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日911.2 纠错编码的基本原理纠错编码的基本原理1、分组码基本原理、分组码基本原理n情形1 1：没有冗余 不能发现错误2：加入冗余 可以发现错误另外4个码组码组码组电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1011.2 纠错编码的基本原理纠错编

9、码的基本原理1、分组码基本原理、分组码基本原理n情形1 1：没有冗余 不能发现错误2：加入冗余 可以发现错误另外4个码组码组码组 只能检出一个码组中只能检出一个码组中1个个和和3个个(奇数奇数)错码的情况，错码的情况，不能发现不能发现2个个(偶数偶数)错码的情况，也不能错码的情况，也不能纠正纠正错误。错误。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1111.2 纠错编码的基本原理纠错编码的基本原理1、分组码基本原理、分组码基本原理n情形1 1：没有冗余 不能发现错误2：加入冗余 可

10、以发现错误许用禁用电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1211.2 纠错编码的基本原理纠错编码的基本原理1、分组码基本原理、分组码基本原理电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1311.2 纠错编码的基本原理纠错编码的基本原理1、分组码基本原理、分组码基本原理，检错 或 纠错 能力也不同。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉

11、通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1411.2 纠错编码的基本原理纠错编码的基本原理1、分组码基本原理、分组码基本原理分组码的一般结构：分组码的一般结构：分组码的符号：分组码的符号：(n,k)n 码组的总位数，又称为码组的长度码组的总位数，又称为码组的长度(码长码长);k 码组中信息码元的数目码组中信息码元的数目;n k r 码组中的监督码元数目，或称监督位数目。码组中的监督码元数目，或称监督位数目。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2

12、月月7日日1511.2 纠错编码的基本原理纠错编码的基本原理2、码重和码组、码重和码组码重码重(w)：码距码距(d)：把码组中把码组中“1”的个数目，简称的个数目，简称码重码重。把两个码组中对应位上数字不同的位数，即两个把两个码组中对应位上数字不同的位数，即两个码组对应位模码组对应位模2和的重量，称为码组的距离，简和的重量，称为码组的距离，简称称码距码距。码距又称。码距又称汉明距离汉明距离。码长码长(n)：码组码组(码字码字)中的码元个数。中的码元个数。“0 1 1 0 1 1”的距离 码重为 3电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第11

13、11章章 差错控制编码差错控制编码2023年年2月月7日日1611.2 纠错编码的基本原理纠错编码的基本原理2、码重和码组、码重和码组码重码重(w)：码距码距(d)：最小码距最小码距(d0)：把码组中把码组中“1”的个数目，简称的个数目，简称码重码重。把两个码组中对应位上数字不同的位数，即两个把两个码组中对应位上数字不同的位数，即两个码组对应位模码组对应位模2和的重量，称为码组的距离，简和的重量，称为码组的距离，简称称码距码距。码距又称。码距又称汉明距离汉明距离。把某种编码中各个码组之间距离的最小值称为把某种编码中各个码组之间距离的最小值称为最小码距最小码距(d0)。若是线性码，若是线性码，d

14、0就等于就等于(非全零非全零)码组的最小重量。码组的最小重量。一种编一种编码的检错和纠错能力决定于最小码距码的检错和纠错能力决定于最小码距d0。码长码长(n)：码组码组(码字码字)中的码元个数。中的码元个数。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1711.2 纠错编码的基本原理纠错编码的基本原理3、最小码距与纠检错能力、最小码距与纠检错能力(n,k)分组码，纠分组码，纠(检检)错能力为：错能力为：(1)为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e+1(2)为

15、了纠正为了纠正t个错码，要求最小码距个错码，要求最小码距d0 2t+1(3)为纠正为纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距)(10teted电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1811.2 纠错编码的基本原理纠错编码的基本原理3、最小码距与纠检错能力、最小码距与纠检错能力(n,k)分组码，纠分组码，纠(检检)错能力为：错能力为：(1)为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e+1(2)为了纠正为了纠正t个错码，要

16、求最小码距个错码，要求最小码距d0 2t+1(3)为纠正为纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距)(10teted电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日1911.2 纠错编码的基本原理纠错编码的基本原理4、编码效率和编码增益、编码效率和编码增益编码效率简称码率编码效率简称码率：冗余度冗余度：编码增益编码增益：监督码元数监督码元数(n-k)和信息码元数和信息码元数k的比值，即的比值，即(n-k)/k。信息码元数信息码元数k与编码组的总与编

17、码组的总码元数码元数(即码长即码长)n的比值。的比值。在保持误码率恒定条件下，采用纠错编码所节省的信在保持误码率恒定条件下，采用纠错编码所节省的信噪比称为编码增益。噪比称为编码增益。ckRn电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2011.4 简单的实用编码简单的实用编码11.4.1 奇偶监督码奇偶监督码 奇偶监督码是最简单的检错码，监督位只有奇偶监督码是最简单的检错码，监督位只有1位，因此码位，因此码率率Rc=(n-1)/n很高。设编码组为很高。设编码组为 ，其中前，其中前n-

18、1位为位为信息码，第信息码，第n位为监督码位为监督码a0。),(021aaann 若若a0的加入使码组中的的加入使码组中的“1”的数目为偶数，即满足条件：的数目为偶数，即满足条件：0021aaann，则称为偶数监督码。，则称为偶数监督码。若若a0的加入使码组中的的加入使码组中的“1”的数目为奇数，即满足条件：的数目为奇数，即满足条件：，则称为奇数监督码。，则称为奇数监督码。1021aaann 这种编码能够检测奇数个错码。但对突发差错的漏检率接这种编码能够检测奇数个错码。但对突发差错的漏检率接近于近于1/2。监督关系式监督关系式校正子校正子电子与信息工程学院电子与信息工程学院 通信工程系通信工程

19、系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2111.4 简单的实用编码简单的实用编码11.4.1 奇偶监督码奇偶监督码 奇偶监督码是最简单的检错码，监督位只有奇偶监督码是最简单的检错码，监督位只有1位，因此码位，因此码率率Rc=(n-1)/n很高。设编码组为很高。设编码组为 ，其中前，其中前n-1位为位为信息码，第信息码，第n位为监督码位为监督码a0。),(021aaann 若若a0的加入使码组中的的加入使码组中的“1”的数目为偶数，即满足条件：的数目为偶数，即满足条件：0021aaann，则称为偶数监督码。，则称为偶数监督码。若若a0

20、的加入使码组中的的加入使码组中的“1”的数目为奇数，即满足条件：的数目为奇数，即满足条件：，则称为奇数监督码。，则称为奇数监督码。1021aaannu 适用：1CknRnnu 码率：电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2211.4 简单的实用编码简单的实用编码11.4.2 二维奇偶监督码（方阵码）二维奇偶监督码（方阵码）先把上述奇偶监督码的若干码组排成矩阵，每一码组写成先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。一行，然后再按列的

21、方向增加第二维监督位。纠检能力纠检能力：有较强的检错能力，并有一定的纠错能力。：有较强的检错能力，并有一定的纠错能力。适用适用：适于检测长度不大于行数：适于检测长度不大于行数(或列数或列数)的突发错误。的突发错误。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2311.4 简单的实用编码简单的实用编码11.4.3 恒比码恒比码 检测方法：检测方法：计算接收码组中计算接收码组中“1 1”的数目，就可知的数目，就可知是否有错是否有错。适用：适用：用于电报用于电报传输系统或其他键盘设备产生的

22、字母和符号。传输系统或其他键盘设备产生的字母和符号。编码规则：编码规则：377!/(3!4!35)C 电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2411.5 线性分组码线性分组码代数码代数码：建立在代数学基础上的编码。：建立在代数学基础上的编码。具有具有封闭性，即任意两个许用码组之和封闭性，即任意两个许用码组之和(逐位模逐位模2加加)仍为一仍为一许用码组。许用码组。它的最小码距等于非全零码组的最小重量。它的最小码距等于非全零码组的最小重量。线性码线性码：按照一组线性方程构成的代数码

23、。在线性码中信息位：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。和监督位是由一些线性代数方程联系着的。线性分组码线性分组码：按照一组线性方程构成的分组码：按照一组线性方程构成的分组码。线性分组码的性质：线性分组码的性质：电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2511.5 线性分组码线性分组码1、汉明码、汉明码若要构造具有若要构造具有纠错纠错能力的（能力的（n，k）码，则需增加督元的数目。）码，则需增加督元的数目。2121rrnkr 或 当

24、当“=”成立时，构造的线性分组码成立时，构造的线性分组码 称为称为汉明码汉明码),(),(rknrr1212 汉明码是一种汉明码是一种能够能够纠正纠正1位错码位错码，且编码效率较高的一种，且编码效率较高的一种线性分组码。线性分组码。其特点是其特点是d0=3(能够纠正一个错码或检两个错码能够纠正一个错码或检两个错码)，码长，码长n与与监督位数监督位数rnk满足关系式满足关系式n=2r-1。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2611.5 线性分组码线性分组码1、汉明码、汉明码例

25、 在在(7,4)码中，码中，n=7，k=4，rnk=3。设设码组为码组为a6 a5 a0，其中信息码元为其中信息码元为a6 a5 a4 a3，监督码元为，监督码元为a2 a1 a0。用。用S1、S2和和S3表示表示3个监督关系式中的校正子个监督关系式中的校正子(又称校验子、伴随式又称校验子、伴随式)。若。若S=0就认为无错码；若就认为无错码；若S=1就认为有错码。就认为有错码。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2711.5 线性分组码线性分组码1、汉明码、汉明码例 仅当一位

26、错码的位置在a2、a4、a5 或a6 时，校正子S1为1；否则S1为 0。16542Saaaa26531Saaaa36430Saaaa电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日2811.5 线性分组码线性分组码1、汉明码、汉明码例654653613204000aaaaaaaaaaaa654621536430aaaaaaaaaaaa(A)电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月

27、月7日日2911.5 线性分组码线性分组码1、汉明码、汉明码例(A)654621536430aaaaaaaaaaaa电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3011.5 线性分组码线性分组码1、汉明码、汉明码例16542Saaaa26531Saaaa36430Saaaa接收端译码检错纠错过程电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3111.5 线性分组码线性分组码1

28、、汉明码、汉明码 一般来说，若码长为一般来说，若码长为n，信息位数为，信息位数为k，则监督位数，则监督位数rnk。如果希望用。如果希望用r个监督位构造出个监督位构造出r个监督关系式来指示个监督关系式来指示1位位错码的错码的n种可能位置，则要求：种可能位置，则要求：对于汉明码，上式取等号。这表明用来纠正单个错误时，对于汉明码，上式取等号。这表明用来纠正单个错误时，汉明码所用的监督位最少。与码长相同的其他纠正单个错误的汉明码所用的监督位最少。与码长相同的其他纠正单个错误的码相比，其码率最高。码相比，其码率最高。1212rknrr或 表中所列的表中所列的(7,4)汉明码的最小码距汉明码的最小码距d0

29、=3。因此，这种码能。因此，这种码能够纠正够纠正1个错码或检测个错码或检测2个错码。由于码率个错码。由于码率k/n=(n-r)/n=1 r/n，故当故当n很大和很大和r很小时，码率接近很小时，码率接近1。可见，汉明码是一种高效码。可见，汉明码是一种高效码。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3211.5 线性分组码线性分组码2、监督矩阵（、监督矩阵（H矩阵矩阵）监督码元和信息码元之间的监督码元和信息码元之间的关系称为监督方程。关系称为监督方程。将它改写为：将它改写为：3460

30、35614562aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa可以表示成矩阵形式：可以表示成矩阵形式：）（模 20001011001110101011101000123456aaaaaaa简记为：简记为：H AT=0T 或或 A HT=0101100111010101110100HA=a6 a5 a4 a3 a2 a1 a00=000右上标右上标“T”表示将矩阵转置。表示将矩阵转置。将将H称为称为监督矩阵监督矩阵。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉

31、通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3311.5 线性分组码线性分组码2、监督矩阵（、监督矩阵（H矩阵矩阵）讨论：讨论：(1)监督矩阵监督矩阵H是一个是一个rn阶阶(r行行n列列)矩阵。矩阵。(2)任一发送码组任一发送码组A都满足式都满足式H AT=0T的关系。的关系。也就是说也就是说只要监督矩阵只要监督矩阵H给定，编码时监督位和信息给定，编码时监督位和信息位的关系就完全确定位的关系就完全确定了。了。H的每行中的的每行中的“1”的位置表示相应的位置表示相应 码元之间存在的监码元之间存在的监督关系。例如，督关系。例如，H的第一行的第一行111010

32、0表示监督位表示监督位a2是由是由a6 a5 a4 之和决定的。之和决定的。(n,k)码的码的H矩阵必须有矩阵必须有r=n-k行，且各行必须是线性无行，且各行必须是线性无关的。关的。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3411.5 线性分组码线性分组码2、监督矩阵（、监督矩阵（H矩阵矩阵）讨论：讨论：(3)H矩阵可以分成两部分：矩阵可以分成两部分：(4)典型典型H矩阵的各行一定是线性无关的。非典型形式的监督矩阵的各行一定是线性无关的。非典型形式的监督矩阵可以经过初等行运算化为

33、典型阵。矩阵可以经过初等行运算化为典型阵。rIPH 001101101011011001110式中，式中，P 为为r k阶矩阵，阶矩阵，Ir 为为r r阶单位方阵阶单位方阵。具有。具有P Ir形式的形式的H矩阵称为矩阵称为典型监督矩阵典型监督矩阵。由典型监督矩阵及信息。由典型监督矩阵及信息码元很容易算出各监督码元。码元很容易算出各监督码元。(7，4)码r=3电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3511.5 线性分组码线性分组码3、生成矩阵（、生成矩阵（G矩阵矩阵）汉明码例子汉

34、明码例子中的监督位中的监督位公式为：公式为：也可以改也可以改写成矩阵写成矩阵形式：形式：或者写成：或者写成：346035614562aaaaaaaaaaaa3456012 101111011110aaaaaaaQ 011101110111 34563456012aaaaaaaaaaa式中，式中，Q为一个为一个k r阶矩阵，它为阶矩阵，它为P的转置，即的转置，即：上式表示，在上式表示，在信息位信息位给定后，用信息位的行矩阵乘矩阵给定后，用信息位的行矩阵乘矩阵Q就产生出就产生出监督位监督位。P 阵阵Q 阵阵 Q=PT 电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理

35、通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3611.5 线性分组码线性分组码3、生成矩阵（、生成矩阵（G矩阵矩阵）将将Q的左边加上的左边加上1个个k k阶阶 单位方阵，就构成单位方阵，就构成1个矩阵个矩阵G。G称为称为生成矩阵生成矩阵，因为由它可以产生整个码组，即有，因为由它可以产生整个码组，即有：G34560123456aaaaaaaaaaaGA3456aaaa或者或者1000010000111111010100001 011kGQI I电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差

36、错控制编码2023年年2月月7日日3711.5 线性分组码线性分组码3、生成矩阵（、生成矩阵（G矩阵矩阵）讨论：讨论：(1)生成矩阵生成矩阵G是一个是一个kn阶矩阵。阶矩阵。(2)具有具有Ik Q形式的生成矩阵称为形式的生成矩阵称为典型生成矩阵典型生成矩阵，由它产，由它产生的分组码称为生的分组码称为系统码系统码。(3)典型生成矩阵典型生成矩阵G和典型和典型监督矩阵监督矩阵 H之间由之间由Q=PT或或P=QT相联系。即：相联系。即：若知若知H=P Ir，则由，则由Q=PT，可得，可得G=IkQ 若知若知G=Ik Q，则由，则由P=QT，可得，可得H=PIr电子与信息工程学院电子与信息工程学院 通

37、信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3811.5 线性分组码线性分组码3、生成矩阵（、生成矩阵（G矩阵矩阵）讨论：讨论：(4)任一码组任一码组A都是都是G的各行的线性组合。的各行的线性组合。G的各行本身就的各行本身就是一个许用码组。是一个许用码组。(5)非典型形式的生成矩阵经过初等行运算也一定可以化非典型形式的生成矩阵经过初等行运算也一定可以化为典型阵。为典型阵。(6)注意：注意：H矩阵、矩阵、G矩阵的各行应该线性无关的。矩阵的各行应该线性无关的。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨

38、会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日3911.5 线性分组码线性分组码4、校正子、校正子S与译码与译码 错误图样错误图样 若若ei=0，表示该接收码元无错；若，表示该接收码元无错；若ei=1，则表示该接收，则表示该接收码元有错。码元有错。设发送码组设发送码组A=a6 a5 a4 a3 a2 a1 a0，接收码组接收码组 ，则，则错误图样错误图样(收发码组之差收发码组之差)为：为：0121bbbbnnBB A=E(模模2)0121eeeennEiiiiiababe当当,1,0式中式中电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨

39、会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4011.5 线性分组码线性分组码4、校正子、校正子S与译码与译码 S 和和 E 的关系的关系接收端计算校正子为：接收端计算校正子为：可以改写成可以改写成 B=A+E(模模2)S=B H T=(A+E)H T =A H T+E H T=E H T 由于由于A HT=0，所以校正子，所以校正子S只只E与有关，即与有关，即S和错码和错码E之间有确定的线性变换关系之间有确定的线性变换关系。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码

40、差错控制编码2023年年2月月7日日4111.5 线性分组码线性分组码4、校正子、校正子S与译码与译码 译码译码 对接收码组对接收码组B计算校正子：计算校正子：S=B H T；译码过程即纠错和检错的过程。其步骤如下：译码过程即纠错和检错的过程。其步骤如下：若若S=0(全全0阵阵)，表示接收码组，表示接收码组B无错；无错；若若S0，则由，则由 S=E H T解得错误图样解得错误图样E；由由B=A+E(模模2)可得到纠错后的码组为可得到纠错后的码组为A=B+E。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码202

41、3年年2月月7日日4211.6 循环码循环码 循环码是循环码是(n,k)线性分组码的一个重要子类。线性分组码的一个重要子类。其编解码设备简单，检其编解码设备简单，检(纠纠)错能力较强。错能力较强。有有RS、BCH等高效子类码，实际应用广泛。等高效子类码，实际应用广泛。循环码除了具有线性分组码的一般性质外，还具有循环性。循环码除了具有线性分组码的一般性质外，还具有循环性。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4311.6 循环码循环码循环性：循环性：是指任一码组循环一位是指任一码

42、组循环一位(即将最右端的一个码元移至即将最右端的一个码元移至左端，或反之左端，或反之)以后，仍为该码中的一个码组。以后，仍为该码中的一个码组。表中的第 2 码组向 右移一位即得到第 5 码组；(7,3)循环码循环码表中的第 6 码组向 右移一位即得到第 3码组。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4411.6 循环码循环码1、码多项式、码多项式在代数编码理论中为了便于运算，常以多项式来表示码组。在代数编码理论中为了便于运算，常以多项式来表示码组。码字（1100101）的多项式

43、可表示为：多项式的系数就是码组中的各码元，多项式的系数就是码组中的各码元，x 仅是码元位置标记仅是码元位置标记。n=7 一个长度为一个长度为n的码组的码组A=an-1 an-2 a0可以表示成多项式形式：可以表示成多项式形式：电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4511.6 循环码循环码1、码多项式、码多项式码多项式的按模运算 一个整数一个整数m 可以表示为可以表示为npnpQnm,（Q 为整数）为整数）m p (模模n)在在模模n 运算下，有运算下，有电子与信息工程学院电子

44、与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4611.6 循环码循环码1、码多项式、码多项式码多项式的按模运算()()()()()F xR xQ xN xN x()()()()F xN x Q xR x或则则()()()F xR xN x（模）电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4711.6 循环码循环码1、码多项式、码多项式码多项式的按模运算 运算过程：运算过程：即有即有 则有则有电子

45、与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4811.6 循环码循环码 在循环码中，若在循环码中，若A(x)是一个长为是一个长为n的许用码组，则的许用码组，则xi A(x)在按模在按模xn+1运算下，也是该编码中的一个许用码组，即若：运算下，也是该编码中的一个许用码组，即若：）（模)1()()(nixxAxAx则则A (x)也是该编码中的一个许用码组。也是该编码中的一个许用码组。1、码多项式、码多项式电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理

46、 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日4911.6 循环码循环码2、生成多项式、生成多项式g(x)1)存在性存在性 在一个在一个(n,k)循环码中，有一个且仅有一个次数为循环码中，有一个且仅有一个次数为(n k)的多项式：的多项式：这唯一的这唯一的(n k)次多项式次多项式g(x)为码的生成多项式。为码的生成多项式。g(x)表表示该循环码的前示该循环码的前(k-1)位皆为位皆为“0”的码组。的码组。11)(111xaxaxxgknknkn电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制

47、编码2023年年2月月7日日5011.6 循环码循环码(2)所有码多项式所有码多项式A(x)都可被都可被g(x)整除，而且任意一个次数不大整除，而且任意一个次数不大于于(k-1)的多项式乘的多项式乘g(x)都是码多项式。都是码多项式。该条性质可用于编码，还可用于验证接收码组是否出错。该条性质可用于编码，还可用于验证接收码组是否出错。2、生成多项式、生成多项式g(x)2)性质性质(1)g(x)是一个：是一个：常数项为常数项为1；最高次数为最高次数为(n-k)次；次；是是xn+1的一个因式。的一个因式。该条性质给我们提供了一种对于给定的该条性质给我们提供了一种对于给定的(n,k)循环码，寻找循环码

48、，寻找或确定其生成多项式的方法。或确定其生成多项式的方法。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日5111.6 循环码循环码3、生成矩阵、生成矩阵G 在循环码中，一个在循环码中，一个(n,k)码有码有2k个不同的码组。个不同的码组。若用若用g(x)表示其中前表示其中前(k-1)位皆为位皆为“0”的码组，的码组，则则g(x)，xg(x)，x2g(x)，xk-1g(x)都是码组，而且这都是码组，而且这k个码个码组是线性无关的。组是线性无关的。因此它们可以用来构成此循环码的生成矩阵因此

49、它们可以用来构成此循环码的生成矩阵G。)()()()()(21xgxxgxgxxgxxkkG 由于此式不符合由于此式不符合G=IkQ的形式，所以它不是典型阵。将的形式，所以它不是典型阵。将其作线性变换，可化成典型阵。其作线性变换，可化成典型阵。一旦确定一旦确定g(x)，整个，整个(n,k)循环码就被确定了。循环码就被确定了。g(x)是循环码的核心。对于给定的是循环码的核心。对于给定的k位信息码，由位信息码，由g(x)构造出构造出G(x)，从，从而产生而产生(n,k)循环码。循环码。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控

50、制编码差错控制编码2023年年2月月7日日5211.6 循环码循环码4、循环码的编码、循环码的编码方法一：对于给定的信息码方法一：对于给定的信息码m(x)，相应的码多项式，相应的码多项式A(x)=m(x)g(x)，它是非系统码。，它是非系统码。方法二：方法二：m(x)与与G(x)相乘。此法得到的是非系统码；若先相乘。此法得到的是非系统码；若先将生成矩阵将生成矩阵G(x)化为典型阵，则可得到系统码。化为典型阵，则可得到系统码。电子与信息工程学院电子与信息工程学院 通信工程系通信工程系 杨会玉杨会玉通信原理通信原理 第第1111章章 差错控制编码差错控制编码2023年年2月月7日日5311.6 循