差错控制编码差错控制编码(传媒传媒05级级)第8章 差错控制编码 8.1差错控制编码的基本概念差错控制编码的基本概念不管是模拟通信系统还是数字通信系统，都存在不管是模拟通信系统还是数字通信系统，都存在因干扰和信道传输特性不好对信号造成的不良影因干扰和信道传输特性不好对信号造成的不良影响。响。它使模拟信号波形会发生畸变，一旦失真很难它使模拟信号波形会发生畸变，一旦失真很难纠正。因此，在模拟系统中只能采取抗干扰、防干纠正。因此，在模拟系统中只能采取抗干扰、防干扰措施扰措施,尽量将干扰降到最低程度以保证通信质量。尽量将干扰降到最低程度以保证通信质量。7/20/20242第8章 差错控制编码 第8章 差错控制编码 第8章 差错控制编码 第8章 差错控制编码 第8章 差错控制编码 第8章 差错控制编码 第8章 差错控制编码 8.2差错控制方式差错控制方式差错控制方式可分为：前向纠错（差错控制方式可分为：前向纠错（FEC）、）、检错重发（检错重发（ARQ）和混合纠错（）和混合纠错（HEC）三）三种。图种。图82是这三种方式构成的差错控制系是这三种方式构成的差错控制系统原理框图。统原理框图。 7/20/20249第8章 差错控制编码 图图82三种差错控制方式示意图三种差错控制方式示意图7/20/202410第8章 差错控制编码 前向纠错前向纠错(FEC)：发端将信息码经信道编码后：发端将信息码经信道编码后变成能够纠正错误的码，收端通过译码能自动发现变成能够纠正错误的码，收端通过译码能自动发现并纠正因传输带来的数据错误。并纠正因传输带来的数据错误。优点：只要求单向信道，适合于只能提供单向信优点：只要求单向信道，适合于只能提供单向信道的场合，或广播传输方式。接收信号的延时小、道的场合，或广播传输方式。接收信号的延时小、实时性好。实时性好。缺点：设备复杂、成本高，且纠错能力愈强，设备缺点：设备复杂、成本高，且纠错能力愈强，设备就愈复杂。就愈复杂。7/20/202411第8章 差错控制编码 检错重发检错重发(ARQ)：发端将信息码编成能够检错：发端将信息码编成能够检错的码，收端收到后进行检验，将检验结果（有误码的码，收端收到后进行检验，将检验结果（有误码或者无误码）通过反向信道反馈给发端作为应答信或者无误码）通过反向信道反馈给发端作为应答信号。发端根据收到的应答信号做出是继续发送新的号。发端根据收到的应答信号做出是继续发送新的数据还是把出错的数据重发的判断。数据还是把出错的数据重发的判断。检错重发系统可分为三种，停发等候重发系检错重发系统可分为三种，停发等候重发系统、返回重发系统和选择重发系统。统、返回重发系统和选择重发系统。7/20/202412第8章 差错控制编码 收端收到该码组并检验后，将应答信号收端收到该码组并检验后，将应答信号ACK发回发端，发端确认码组发回发端，发端确认码组1无错，就将无错，就将码组码组2发送出来；收端判断该码组有错并以发送出来；收端判断该码组有错并以NAK信号告知发端，发端将码组信号告知发端，发端将码组1重新发送重新发送一次。一次。7/20/202413第8章 差错控制编码 图图83检错重发的三种工作方式检错重发的三种工作方式7/20/202414第8章 差错控制编码 返回重发系统如图返回重发系统如图83（b）所示，发端不停）所示，发端不停顿地发送信息码组，不再等候顿地发送信息码组，不再等候ACK信号，如果收信号，如果收端发现错误并发回端发现错误并发回NAK信号，则发端从下一个码信号，则发端从下一个码组开始重发前一段组开始重发前一段N个码组，图中个码组，图中N=5。收端收到。收端收到码组码组2有错。发端在码组有错。发端在码组6后重发码组后重发码组2、3、4、5、6，这种返回重发系统的传输效率比停发等候系统，这种返回重发系统的传输效率比停发等候系统有很大改进，在很多数据传输系统中得到应用。有很大改进，在很多数据传输系统中得到应用。7/20/202415第8章 差错控制编码 图图83（c）：系统也是连续不断地发送码）：系统也是连续不断地发送码组，收端检测到错误后发回组，收端检测到错误后发回NAK信号，但是发端不信号，但是发端不是重发前是重发前N个码组，而是只重发有错误的那一组。个码组，而是只重发有错误的那一组。如只重发收端检出有错的码组如只重发收端检出有错的码组2。收端对已认可的码组，从缓冲存储器读出时重收端对已认可的码组，从缓冲存储器读出时重新排序，恢复出正常的码组序列。新排序，恢复出正常的码组序列。系统传输效率最高，但价格也最贵。系统传输效率最高，但价格也最贵。7/20/202416第8章 差错控制编码 混合纠错方式是前向纠错方式和检错重发方式混合纠错方式是前向纠错方式和检错重发方式的结合。如图的结合。如图82（c）所示。）所示。其内层采用其内层采用FEC方式，纠正部分差错；外层采方式，纠正部分差错；外层采用用ARQ方式，重传那些虽已检出但未纠正的差方式，重传那些虽已检出但未纠正的差错。混合纠错方式在实时性和译码复杂性方面是前错。混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，较适合于环路延迟向纠错和检错重发方式的折衷，较适合于环路延迟大的高速数据传输系统。大的高速数据传输系统。7/20/202417第8章 差错控制编码 8.3差错控制编码分类差错控制编码分类介绍几种主要分类。介绍几种主要分类。(1)根据编码功能可分为检错码、纠错码和纠根据编码功能可分为检错码、纠错码和纠删码三种类型，只能完成检错功能的叫检错删码三种类型，只能完成检错功能的叫检错码；具有纠错能力的叫纠错码；而纠删码既码；具有纠错能力的叫纠错码；而纠删码既可检错也可纠错。可检错也可纠错。7/20/202418第8章 差错控制编码 (2)按照信息码元和附加的监督码元之间的按照信息码元和附加的监督码元之间的检验关系可以分为线性码和非线性码。检验关系可以分为线性码和非线性码。线性码：信息码元与监督码元之间的关系为线性码：信息码元与监督码元之间的关系为线性关系，即监督码元是信息码元的线性组线性关系，即监督码元是信息码元的线性组合，则称为线性码。合，则称为线性码。非线性码：两者不存在线性关系，称为非线非线性码：两者不存在线性关系，称为非线性码。性码。7/20/202419第8章 差错控制编码 (3)按按照照信信息息码码元元和和监监督督码码元元之之间间的的约约束束方方式式可可分分为为分组码和卷积码。分组码和卷积码。分组码：把信息序列分为分组码：把信息序列分为k位一组，附加位一组，附加m位监督码位监督码元，形成元，形成n=k+m位的码组。监督码元仅与本码组的位的码组。监督码元仅与本码组的信息码元有关，而与其它码组无关。信息码元有关，而与其它码组无关。卷积码：码组中的监督码元不但与本组信息码元有卷积码：码组中的监督码元不但与本组信息码元有关，而且与前面码组的信息码元也有约束关系，卷关，而且与前面码组的信息码元也有约束关系，卷积码又称连环码或链码。积码又称连环码或链码。7/20/202420第8章 差错控制编码 (4)系统码与非系统码。在线性分组码中所有码组系统码与非系统码。在线性分组码中所有码组的的k位信息码元在编码前后保持原来形式的码叫系位信息码元在编码前后保持原来形式的码叫系统码，反之就是非系统码。系统码的编、译码都相统码，反之就是非系统码。系统码的编、译码都相对比较简单，因此得到广泛应用。对比较简单，因此得到广泛应用。(5)纠正随机错误码和纠正突发错误码。前者用于纠正随机错误码和纠正突发错误码。前者用于纠正因信道中出现的随机独立干扰引起的误码，后纠正因信道中出现的随机独立干扰引起的误码，后者主要对付信道中出现的突发错误。者主要对付信道中出现的突发错误。7/20/202421第8章 差错控制编码 8.4检错和纠错原理检错和纠错原理数字通信中码元的两种错误形式：随机错误和突发数字通信中码元的两种错误形式：随机错误和突发错误。错误。(1)随机错误。由随机噪声引起的码元错误，其特随机错误。由随机噪声引起的码元错误，其特点是码元中任意一位或几位发生从点是码元中任意一位或几位发生从0变变1或从或从1变变0的的错误是相互独立的，彼此之间没有联系，一般不会错误是相互独立的，彼此之间没有联系，一般不会引起成片的码元错误。引起成片的码元错误。7/20/202422第8章 差错控制编码 (2)突发错误。由突发噪声引起的码元错误，突发错误。由突发噪声引起的码元错误，比如，闪电、电器开关的瞬态、磁带缺陷等比如，闪电、电器开关的瞬态、磁带缺陷等都属于突发噪声。该错误的特点是各错误码都属于突发噪声。该错误的特点是各错误码元之间存在相关性，因此是成片出现，错误元之间存在相关性，因此是成片出现，错误序列的长度（包括首和尾在内的错误所波及序列的长度（包括首和尾在内的错误所波及的段落长度）称为突发长度。的段落长度）称为突发长度。7/20/202423第8章 差错控制编码 简单例子：介绍检错和纠错的基本原理。简单例子：介绍检错和纠错的基本原理。假设要发送一组具有四个状态的数据信息假设要发送一组具有四个状态的数据信息（比如，一个电压信号的四个值，（比如，一个电压信号的四个值，1V、2V、3V、4V）。首先要用二进制码对数据信息进）。首先要用二进制码对数据信息进行编码，显然，用行编码，显然，用2位二进制码就可完成，编位二进制码就可完成，编码表如表码表如表81所示。所示。7/20/202424第8章 差错控制编码 表表812位编码表位编码表7/20/202425第8章 差错控制编码 假设不经信道编码，在信道中直接传输假设不经信道编码，在信道中直接传输按表中编码规则得到的按表中编码规则得到的0、1数字序列，则在数字序列，则在理想情况下，收端收到理想情况下，收端收到00就认为是就认为是1V，收到，收到10就是就是3V。而在实际通信中由于干扰（噪。而在实际通信中由于干扰（噪声）的影响，会使信息码元发生错误从而出声）的影响，会使信息码元发生错误从而出现误码（比如码组现误码（比如码组00变成变成10、01或或11）。从）。从而引起信息传输错误。而引起信息传输错误。7/20/202426第8章 差错控制编码 因此，以这种编码得到的数字信号在传输因此，以这种编码得到的数字信号在传输中不具备检错和纠错的能力。问题的关键是中不具备检错和纠错的能力。问题的关键是2位二进制码的全部组合都是信息码组或称许位二进制码的全部组合都是信息码组或称许用码组，任何一位（或两位）发生错误都会用码组，任何一位（或两位）发生错误都会引起歧义。为了克服这一缺点，在每组码后引起歧义。为了克服这一缺点，在每组码后面再加面再加1位码元，使位码元，使2位码组变成位码组变成3位码组。位码组。7/20/202427第8章 差错控制编码 表表823位编码表位编码表7/20/202428第8章 差错控制编码 在许用码组在许用码组000、011、101、110中，右中，右边加上的边加上的1位码元就是监督码元，它的加入位码元就是监督码元，它的加入原则是使码组中原则是使码组中1的个数为偶数。现在我们的个数为偶数。现在我们再看一下出现误码的情况，假设许用码组再看一下出现误码的情况，假设许用码组000出现出现1位误码，即变成位误码，即变成001、010或或100三三个码组中的一个，可见这三个码组中个码组中的一个，可见这三个码组中1的个的个数都是奇数，是禁用码组。数都是奇数，是禁用码组。7/20/202429第8章 差错控制编码 因此，当收端收到这三个码组中的任何一因此，当收端收到这三个码组中的任何一个时，就知道是误码，用这种方法可以发现个时，就知道是误码，用这种方法可以发现1位或位或3位出现错误的码组，而无法检出位出现错误的码组，而无法检出2位错位错误，通过增加误，通过增加1位监督码元，我们可以检出位监督码元，我们可以检出1位或位或3位错误（位错误（3位出错的概率极小），但无位出错的概率极小），但无法纠正错误。法纠正错误。7/20/202430第8章 差错控制编码 能否通过增加监督码元的位数来增加检错能否通过增加监督码元的位数来增加检错位数或实现纠错功能呢？比如我们在表位数或实现纠错功能呢？比如我们在表8-2中中再加再加1位监督码元变成位监督码元变成4位编码（表位编码（表83）。）。 表表834位编码表位编码表7/20/202431第8章 差错控制编码 编码原则仍然是偶校验。显然，检错编码原则仍然是偶校验。显然，检错1位位和和3位没问题，但检错位没问题，但检错2位还不行（比如位还不行（比如0000变成变成1100，而，而1100是许用码组）。设误码为是许用码组）。设误码为1110，则可能的原码为，则可能的原码为0110、1010、1100、1111四个（还按四个（还按1位误码考虑），而位误码考虑），而0110、1010、1100都是许用码组，所以无法纠错。都是许用码组，所以无法纠错。7/20/202432第8章 差错控制编码 可见，简单地增加可见，简单地增加1位监督码元并没有提位监督码元并没有提高检错与纠错能力，那么，检错与纠错能力高检错与纠错能力，那么，检错与纠错能力到底与什么有关呢？在回答这个问题之前，到底与什么有关呢？在回答这个问题之前，我我们们先先介介绍绍两两个个新新概概念念码码元元距距离离和和码码元元重重量。量。7/20/202433第8章 差错控制编码 码距（也称汉明距）：两个码组中对应码位上码距（也称汉明距）：两个码组中对应码位上码元不同的个数。码元不同的个数。码距反映的是码组之间的差异程度，比如，码距反映的是码组之间的差异程度，比如，00和和01两组码的码距为两组码的码距为1；011和和100的码距为的码距为3。多个。多个码组之间相互比较，可能会有不同的码距，其中的码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用最小值被称为最小码距（用dmin表示）。比如，表示）。比如，000、001、110三个码组相比较，码距有三个码组相比较，码距有1和和2两个两个值，则最小码距为值，则最小码距为1；7/20/202434第8章 差错控制编码 分析表明，一种编码方式的检错、纠错能力与分析表明，一种编码方式的检错、纠错能力与许用码组中的最小码距有关。比如，表许用码组中的最小码距有关。比如，表82中中8个个码组的最小码距为码组的最小码距为1，若这，若这8个码组都作为许用码个码组都作为许用码组，则没有检错能力，更不用说纠错了；组，则没有检错能力，更不用说纠错了；若只选其中四个作为许用码组，则最小码距为若只选其中四个作为许用码组，则最小码距为2，可检，可检1位或位或3位错误；若只选位错误；若只选000和和111为许用码为许用码组时，其最小码距为组时，其最小码距为3，那么就可发现所有，那么就可发现所有2位以下位以下的错误，若用来纠错，则可纠正的错误，若用来纠错，则可纠正1位错误。位错误。7/20/202435第8章 差错控制编码 根据理论推导，可以得出以下结论：根据理论推导，可以得出以下结论：(1)在一个码组内要检出在一个码组内要检出e位误码，要求最小码距为：位误码，要求最小码距为：dmine+1(8.41)(2)在一个码组内要纠正在一个码组内要纠正t位误码，要求最小码距为：位误码，要求最小码距为：dmin2t+1(8.42)(3)在一个码组内要纠正在一个码组内要纠正t位误码，同时检测出位误码，同时检测出e 位误码（位误码（et）,要求最小码距为：要求最小码距为：dmint+e+1(8.43) 7/20/202436第8章 差错控制编码 要提高编码的纠、检错能力，方法是：要提高编码的纠、检错能力，方法是：增加监督码元位数（即冗余度）；增加监督码元位数（即冗余度）；加大最小码距，最小码距增大，码元的冗余度就加大最小码距，最小码距增大，码元的冗余度就增大。冗余度增大，最小码距不一定增大。增大。冗余度增大，最小码距不一定增大。编码方式具有检错和纠错能力的必要条件是信编码方式具有检错和纠错能力的必要条件是信息编码必须有冗余，而充分条件是码元之间要有一息编码必须有冗余，而充分条件是码元之间要有一定的码距。另外，检错要求的冗余度比纠错要低。定的码距。另外，检错要求的冗余度比纠错要低。7/20/202437第8章 差错控制编码 把把k位信息码编成位信息码编成n位差错控制码，信息码的位数位差错控制码，信息码的位数k与差错控制码的位数与差错控制码的位数n之比定义为编码效率，用之比定义为编码效率，用Rc表示，即表示，即因为因为kn，所以，所以，Rck分组码元（分组码元（n位）位）=信息码元（信息码元（k位）位）+监督码监督码元（元（n-k位）位）2k个不同码组用矩阵个不同码组用矩阵C表示。表示。有时把监督码元称为或校验码元。有时把监督码元称为或校验码元。7/20/202458第8章 差错控制编码 k值越大，编码设备越复杂，因为编码设值越大，编码设备越复杂，因为编码设备必须储存备必须储存2k个码长为个码长为n的码组。因此，我的码组。因此，我们需要构造码组之间有某种关系的分组码，们需要构造码组之间有某种关系的分组码，以降低编码的复杂性，线性分组码就是满足以降低编码的复杂性，线性分组码就是满足这一条件的一种分组码。这一条件的一种分组码。7/20/202459第8章 差错控制编码 线性分组码：是一种长度为线性分组码：是一种长度为n，其中，其中2k个许个许用码组（代表信息的码组）中的任意两个码用码组（代表信息的码组）中的任意两个码组的模组的模2和仍为一个许用码组的分组码。称为和仍为一个许用码组的分组码。称为线性（线性（n，k）码。）码。重要性质：重要性质：封闭性，即任意两个许用码封闭性，即任意两个许用码组之模组之模2和仍为一许用码组；和仍为一许用码组；码组的最小码码组的最小码距等于非零码的最小码重。距等于非零码的最小码重。7/20/202460第8章 差错控制编码 图图84线性分组码格式线性分组码格式具有这种结构的线性分组码又叫做线性分组具有这种结构的线性分组码又叫做线性分组系统码。系统码。7/20/202461第8章 差错控制编码 相应的信息码组行向量和分组码码组行向相应的信息码组行向量和分组码码组行向量为量为 C =c1,c2,cn (8.61)D =d1,d2,dk (8.62)一个分组码组的前一个分组码组的前k位是信息码元，后位是信息码元，后n-k位是监督码元（设监督码元位数为位是监督码元（设监督码元位数为m，则有，则有m=n-k），每一个分组码组可以由信息码元），每一个分组码组可以由信息码元线性组合而成，即：线性组合而成，即：7/20/202462第8章 差错控制编码 7/20/202463第8章 差错控制编码 式中式中,hmidi表示模表示模2乘，也可表示为乘，也可表示为hm idi。其运。其运算规则是：算规则是：1 0=0 1=0 0=0；1 1=1。可见，在。可见，在线性分组码中，信息码元和监督码元可以用线性方线性分组码中，信息码元和监督码元可以用线性方程联系起来。程联系起来。将上述将上述C与与D的的n个关系式用矩阵表示为个关系式用矩阵表示为7/20/202464第8章 差错控制编码 即即 C=DG(8.63)式式中中,G称称为为生生成成矩矩阵阵，是是一一个个kn阶阶矩矩阵，具体形式为阵，具体形式为7/20/202465第8章 差错控制编码 该矩阵又可分解为两个子矩阵该矩阵又可分解为两个子矩阵:7/20/202466第8章 差错控制编码 其中其中Ik是是kk阶单位阵，阶单位阵，P为为km阶矩阶矩阵，即：阵，即：7/20/202467第8章 差错控制编码 这样，分组码这样，分组码C又可表示为又可表示为C =DIk P（8.64）需要说明的是，上述各式中的需要说明的是，上述各式中的C和和D可以是可以是由一个码组构成的一个行向量，也可以是由由一个码组构成的一个行向量，也可以是由2k个行向量构成的个行向量构成的2kn阶分组码矩阵或阶分组码矩阵或2kk阶信息码矩阵。阶信息码矩阵。 7/20/202468第8章 差错控制编码 式（式（8.63）说明：）说明：（n，k）线性码完全由生）线性码完全由生成矩阵成矩阵G的的k行元素决定，即任意一个分组码码组行元素决定，即任意一个分组码码组都是都是G的线性组合。的线性组合。（n，k）线性码中的任何）线性码中的任何k个线性无关的码组都可用来构成生成矩阵，所以，个线性无关的码组都可用来构成生成矩阵，所以，生成矩阵生成矩阵G的各行都线性无关。的各行都线性无关。G的各行本身就是的各行本身就是一个码组。一个码组。如果已有如果已有k个线性无关的码组，则可个线性无关的码组，则可用其直接构成用其直接构成G矩阵，并由此生成其余码组。矩阵，并由此生成其余码组。7/20/202469第8章 差错控制编码 综上所述，由于可用一个综上所述，由于可用一个kn阶矩阵阶矩阵G生生成成2k个不同的码组，因此，编码器只需储存个不同的码组，因此，编码器只需储存G矩阵的矩阵的k行元素（而不是一般分组码的行元素（而不是一般分组码的2k码码组），就可根据信息向量构造出相应的一个组），就可根据信息向量构造出相应的一个分组码码组（或根据信息码矩阵构造出相应分组码码组（或根据信息码矩阵构造出相应的一个分组码矩阵），从而降低了编码的复的一个分组码矩阵），从而降低了编码的复杂性，并提高了编码效率。杂性，并提高了编码效率。7/20/202470第8章 差错控制编码 【例例题题81】给给定定一一个个（7，4）线线性性分分组组码码的生成矩阵的生成矩阵 若若信信息息码码为为d=1101，求求该该信信息息码码的的线线性分组编码性分组编码C。7/20/202471第8章 差错控制编码 解解:根据式（根据式（8.63）可得）可得7/20/202472第8章 差错控制编码 即对信息码即对信息码1101的线性分组编码为的线性分组编码为1101000。注意在矩阵乘法中，是模。注意在矩阵乘法中，是模2乘和模乘和模2加。上式也可写成加。上式也可写成7/20/202473第8章 差错控制编码 以上讨论可知，编码前的信息码组共有以上讨论可知，编码前的信息码组共有2k种组合，编码后的码组在种组合，编码后的码组在k位信息码元之外还位信息码元之外还附加了附加了m位校验码元，共有位校验码元，共有2n种组合，种组合，2n2k，这就是说，这就是说C与与D的关系不惟一。的关系不惟一。因此，选择适当的矩阵因此，选择适当的矩阵P，就可得到既具，就可得到既具有较强检错或纠错能力，又较简单且编码效有较强检错或纠错能力，又较简单且编码效率较高的线性分组码。目前已经找到不少性率较高的线性分组码。目前已经找到不少性能较好的矩阵能较好的矩阵P。7/20/202474第8章 差错控制编码 【例题【例题82】已知线性（已知线性（6，3）码的生成）码的生成矩阵为矩阵为求线性分组码、各码组的码重、最小码距求线性分组码、各码组的码重、最小码距和该码的差错控制能力。和该码的差错控制能力。解：因为解：因为k=3，故信息码组矩阵（，故信息码组矩阵（38）为）为7/20/202475第8章 差错控制编码 7/20/202476第8章 差错控制编码 则由式（则由式（8.63）可得出分组码码组）可得出分组码码组矩阵（矩阵（68阶）为阶）为7/20/202477第8章 差错控制编码 表表88例例82编码表编码表7/20/202478第8章 差错控制编码 从表中可见非零码组的最小码重为从表中可见非零码组的最小码重为3，则，则分组码的最小码距分组码的最小码距dmin=3，根据式（，根据式（8.41）、）、（8.42）和（）和（8.43）可知该分组码能够检）可知该分组码能够检2位错，纠位错，纠1位错，或同时纠位错，或同时纠1位错检位错检1位错。位错。需要说明的是，任何线性分组码都包含全需要说明的是，任何线性分组码都包含全零码组。因任一码组与其本身模零码组。因任一码组与其本身模2加都会得到加都会得到全零码组。全零码组。7/20/202479第8章 差错控制编码 下面我们简要介绍译码原理。从式（下面我们简要介绍译码原理。从式（8.47）可得）可得（8.66）（8.65） 式式中中，Cm是是km阶阶监监督督码码元元矩矩阵阵。将将式式(8.66)改写为改写为: (8.67)(8.68)7/20/202480第8章 差错控制编码 该式说明线性分组码中任一码组与校验矩该式说明线性分组码中任一码组与校验矩阵阵H的转置相乘，其结果为的转置相乘，其结果为m位全零向量，因位全零向量，因此，用校验矩阵检查二元序列是不是给定分此，用校验矩阵检查二元序列是不是给定分组码中的码组非常方便，组码中的码组非常方便，“校验校验”由此而来。由此而来。可以推导出校验矩阵可以推导出校验矩阵H与生成矩阵与生成矩阵G满足满足 GHT=HGT=0(8.69)7/20/202481第8章 差错控制编码 设行向量设行向量R=r1，r2，rn是收信端收是收信端收到的码组。由于信道干扰产生误码，接收向到的码组。由于信道干扰产生误码，接收向量量R和发送向量和发送向量C就有差别，用向量就有差别，用向量E=e1，e2，en表示这种差别。由此定义三者之表示这种差别。由此定义三者之间的关系为间的关系为（8.610） 7/20/202482第8章 差错控制编码 若若R中的某一位中的某一位ri与与C中的相同位中的相同位ci一样一样时，时，E中的中的ei=0；若不同（即出现误码），则；若不同（即出现误码），则ei=1。可见向量。可见向量E能够反映误码状况，故称之能够反映误码状况，故称之为错误向量或错误图样。可见，为错误向量或错误图样。可见，E的码重就的码重就是误码的个数，因此是误码的个数，因此E的码重越小越好。的码重越小越好。7/20/202483第8章 差错控制编码 式（式（8.610）也可写为）也可写为 R =E C（8.611）定义矩阵定义矩阵S为伴随式为伴随式S =RHT（8.612）S是长度为是长度为m=n-k的二元序列，有的二元序列，有2m种组合。由式种组合。由式（8.68）、（）、（8.611）和（）和（8.612）得）得S =（E C）HT=EHT C HT=EHT（8.6-13）7/20/202484第8章 差错控制编码 式（式（8.613）表明伴随式）表明伴随式S只与错误图样只与错误图样E有关，与发送码组无关。有关，与发送码组无关。S称为称为R的伴随式或的伴随式或称校正子。称校正子。当当S为零矢量时，说明为零矢量时，说明R没有错，没有错，R是码组是码组C；否则，说明；否则，说明R有错，有错，R不是码组不是码组C。当通信双方确定了信道编码后，生成矩阵当通信双方确定了信道编码后，生成矩阵G和监督矩阵和监督矩阵H也就随之而定。收端可以知道也就随之而定。收端可以知道G、H和和R。7/20/202485第8章 差错控制编码 译码方法：译码方法：收端先求出伴随式收端先求出伴随式S解出错误图样解出错误图样E解出发送码组解出发送码组C7/20/202486第8章 差错控制编码 需要说明的是，上述步骤只是一个概念上需要说明的是，上述步骤只是一个概念上的解释，具体方法还比较麻烦。因为对于一个的解释，具体方法还比较麻烦。因为对于一个伴随式伴随式S，有，有2k个错误图样与之对应，换句话个错误图样与之对应，换句话说，就是式说，就是式(8.613)的解不唯一，真正的错误的解不唯一，真正的错误图样只是图样只是2k个错误图样中的一个。个错误图样中的一个。7/20/202487第8章 差错控制编码 【例例题题83】已已知知一一线线性性(6，3)码码的的生生成成矩矩阵阵G、S和和E的对照表分别为：的对照表分别为：7/20/202488第8章 差错控制编码 SE000000000101100000011010000110001000100000100010000010001000001111100010 求求当当接接收收端端收收到到码码组组R=111011时时，所所对对应应的的信息码组信息码组D。7/20/202489第8章 差错控制编码 解：解：根据前面根据前面HT的定义式可得的定义式可得将接收码组将接收码组R=111011代入代入(8.612)式，可得：式，可得：7/20/202490第8章 差错控制编码 7/20/202491第8章 差错控制编码 从从SE关系表中可知，关系表中可知，S=011所对应的错误所对应的错误图样为图样为E =010000。将。将R =111011和和E=010000代入式代入式(813)或式或式(814)可得可得 C =R E =101011从从C中分出信息码组为中分出信息码组为D=101信息码组为信息码组为D =1017/20/202492第8章 差错控制编码 8.7循循环环码码定义：对于一个（定义：对于一个（n，k）线性码）线性码C，若其中，若其中的任一码组向左或向右循环移动任意位后仍的任一码组向左或向右循环移动任意位后仍是是C中的一个码组，则称中的一个码组，则称C是一个循环码。循是一个循环码。循环码是一种分组码，前环码是一种分组码，前k位为信息码元，后位为信息码元，后m位为监督码元。位为监督码元。优点：纠错能力强，编解码简单。优点：纠错能力强，编解码简单。7/20/202493第8章 差错控制编码 若若c=c1，c2，cn是一个循环码组，左循环是一个循环码组，左循环移移位位一一次次，得得到到c（1）=c2，c3，cn，c1也也是是许许用码组，移位用码组，移位i次得到次得到c(i)=ci+1，ci+2，cn，c1，ci还是许用码组。还是许用码组。在代数编码理论中，可以把循环码组中各码元当在代数编码理论中，可以把循环码组中各码元当作一个多项式的系数，即把一个长为作一个多项式的系数，即把一个长为n的码组表示的码组表示 c(x)=c1xn-1+c2xn-2+cn7/20/202494第8章 差错控制编码 式中，式中，c(x)称为码多项式，变量称为码多项式，变量x称为元素，其幂称为元素，其幂次对应元素的位置，它的系数即为元素的取值（我次对应元素的位置，它的系数即为元素的取值（我们不关心们不关心x本身的取值），系数之间的加法和乘法仍本身的取值），系数之间的加法和乘法仍服从模服从模2规则。比如一个（规则。比如一个（7，3）循环码（见表）循环码（见表89）中第）中第7个码组为（个码组为（1100101），则该码组可表），则该码组可表示为示为 c7(x)=1x6+1x5+0x4+0x3+1x2+0x +1=x6+x5+x2+17/20/202495第8章 差错控制编码 表表89一种（一种（7，3）循环码的全部码组）循环码的全部码组7/20/202496第8章 差错控制编码 举例说明系统码与非系统码的区别。对一组举例说明系统码与非系统码的区别。对一组4位信位信息码组，附加息码组，附加3位监督码元可编成两种（不只两种）位监督码元可编成两种（不只两种）循环码，见表循环码，见表810所示。所示。系统码的前系统码的前4位对应的都是信息码，而后位对应的都是信息码，而后3位都是位都是监督码元，且编码前后信息码形式保持不变。监督码元，且编码前后信息码形式保持不变。非系统码从第非系统码从第5组开始信息码就组开始信息码就“乱乱”了，没有系统了，没有系统码那种前后一致的信息码结构。码那种前后一致的信息码结构。7/20/202497第8章 差错控制编码 另外，还需说明的是，对于一个（另外，还需说明的是，对于一个（n，k）线性）线性码码C，根据不同的方法（生成矩阵）可以有多种编，根据不同的方法（生成矩阵）可以有多种编码形式，其中包含系统码和非系统码，但系统码码形式，其中包含系统码和非系统码，但系统码是惟一的，其余的都是非系统码。是惟一的，其余的都是非系统码。小结：简要地了解了数字（数据）通信中信小结：简要地了解了数字（数据）通信中信道编码的基本概念和常用的检纠错编码，编码所道编码的基本概念和常用的检纠错编码，编码所研究的主要问题是：研究的主要问题是：7/20/202498第8章 差错控制编码 (1)根据系统对纠错能力的要求，寻找合适根据系统对纠错能力的要求，寻找合适的码型。要求该码型可在数学上证明具有满的码型。要求该码型可在数学上证明具有满足要求的纠错能力，并具有数学结构，且能足要求的纠错能力，并具有数学结构，且能够根据此结构具体实现编码和译码。够根据此结构具体实现编码和译码。(2)寻找实用的编码方法，提高编码效率。寻找实用的编码方法，提高编码效率。(3)寻找实用的译码方法，降低译码复杂性。寻找实用的译码方法，降低译码复杂性。7/20/202499第8章 差错控制编码 表表810（7，4）循环码码组）循环码码组7/20/2024100第8章 差错控制编码 7/20/2024101第8章 差错控制编码 图图5-4（7，4）系统循环码编码器与时序图）系统循环码编码器与时序图7/20/2024102第8章 差错控制编码 节拍 1 2 3 4 5 6 7d (x) 1 0 1 0 0 0 0D1状态 0 1 1 0 1 0 0D2状态 0 0 1 1 0 1 0D3状态 0 1 1 1 0 0 1c(x) 1 0 1 0 0 0 1表表8-118-11（补）图（补）图5-45-4的电路工作过程的电路工作过程7/20/2024103结束语结束语谢谢大家聆听！谢谢大家聆听！104