1、第第8章章 差错控制技术差错控制技术1第第8章差错控制技术章差错控制技术 第第8章章 差错控制技术差错控制技术2目的要求目的要求理解差错控制的基本方法和检错、纠错理解差错控制的基本方法和检错、纠错码构成的基本原理。码构成的基本原理。了解常用检错码的特性；了解常用检错码的特性；掌握线性分组码的一般特性；掌握线性分组码的一般特性；掌握汉明码以及循环码的编译码及其实掌握汉明码以及循环码的编译码及其实现原理；现原理；了解卷积码的基本概念。了解卷积码的基本概念。本章是本课程的重点。本章是本课程的重点。第第8章章 差错控制技术差错控制技术3 教学内容教学内容 8.1 概述 8.2 差错控制方法 8.3 常
2、用检错码 8.4 线性分组码 8.5 循环码 8.6 卷积码 返回总目录第第8章章 差错控制技术差错控制技术48.1 引言引言返回目录1引起误码的原因 信道中加性噪声的出现及其大小都是随机的，对这种随机加性干扰，信道一般分为三类：（1）随机信道，即这种信道中存在着随机白色干扰，噪声分布为高斯分布。它造成的误码前后无关，互为独立。（2）突发信道，即突发干扰造成的误码，在短时间内错码连串，误码的出现时前后有关的。造成这种误码的主要干扰是突发脉冲，如电话交换机干扰、闪电及电火花干扰等。这种干扰的出现也是随机的，且干扰幅度大。（3）混合信道，即随机干扰和突发干扰都存在。第第8章章 差错控制技术差错控制
3、技术58.1 引言引言返回目录2提高数字通信可靠性的途径 随着计算机技术的发展，在数据通信中，采用计算机技术进行编码和控制，以满足通信质量的要求，这就是差错控制技术。 差错控制技术包括抗干扰编码，以及与其相适应的差错控制方法。 第第8章章 差错控制技术差错控制技术6一、差错控制一、差错控制 所谓所谓差错控制差错控制是通过某种方法，发现是通过某种方法，发现并纠正传输中出现的错误。它是数据通信并纠正传输中出现的错误。它是数据通信系统中提高系统中提高传输可靠性传输可靠性，降低系统传输误降低系统传输误码率码率的有效措施的有效措施 。返回目录第第8章章 差错控制技术差错控制技术78.1.1差错控制基本概
4、念 在数据通信系统中，对信源输出的二进制的信息序列作某种变换，使原来彼此独立、互不相干的的信息码元序列产生某种规律性（相关性），从而在接收端有可能根据这种规律性来检查，进而检查或纠正传输信号中的差错。变换的方法不同就构成了不同的编码，在系统中使用不同的编码方法就产生了不同的差错控制方法。抗干扰编码可分成两大类，一类是检错码，另一类是纠错码。 第第8章章 差错控制技术差错控制技术81、基本思路、基本思路在发送端被传送的信息码序列的基础上，按在发送端被传送的信息码序列的基础上，按照一定的规则加入若干照一定的规则加入若干“监督码元监督码元”后进行传输，后进行传输，这些加入的码元与原来的信息码序列之间
5、存在着某这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。种确定的约束关系。 信息码信息码+监督码监督码=码组，称差错控制编码或纠码组，称差错控制编码或纠错编码或信道编码错编码或信道编码第第8章章 差错控制技术差错控制技术9返回目录2.2.差错控制的基本原理差错控制的基本原理1 1原理描述原理描述 在二进制编码中，一位二进制编码可表示在二进制编码中，一位二进制编码可表示两种不同的状态，两位二进制编码可表示四种不两种不同的状态，两位二进制编码可表示四种不同的状态，三位二进制编码可表示八种不同的状同的状态，三位二进制编码可表示八种不同的状态，态，n n位二进制编码可表示位二进制编码可表
6、示2 2n n种不同的状态。在种不同的状态。在n n位二进制编码的位二进制编码的2 2n n种不同的状态中，能表示有用种不同的状态中，能表示有用信息的码组称为信息的码组称为。不表示有用信息的码。不表示有用信息的码组称为组称为。 第第8章章 差错控制技术差错控制技术10信息码组信息码组M由由k个二进制码元（即比特）组个二进制码元（即比特）组成，所以就有成，所以就有2k个个M；A长度为长度为n，n位长度的码位长度的码字共有字共有2n个，信道编码实质是通过一定个，信道编码实质是通过一定 的规则，的规则，从从2n个长度为个长度为n的码字中选择了其中的的码字中选择了其中的2k个，每个，每个被选中的码字称
7、为许用码字；未被选中的个被选中的码字称为许用码字；未被选中的2n-2k个个n长的码字称为禁用码字，反映冗余大小长的码字称为禁用码字，反映冗余大小 。第第8章章 差错控制技术差错控制技术113 .3 .差错控制编码的特性和能力差错控制编码的特性和能力 差错控制编码的能力与差错控制编码的特性有差错控制编码的能力与差错控制编码的特性有关，编码的特性主要包括码字的汉明重量，码间距离关，编码的特性主要包括码字的汉明重量，码间距离d d，最小码距，最小码距d d0 0。 在说明这些特性之前，先说明在说明这些特性之前，先说明码元、码字、码码元、码字、码组组之间的关系。码字（用之间的关系。码字（用C C表示）
8、由许多码元组成，表示）由许多码元组成，码字中码元的个数称为码长（用码字中码元的个数称为码长（用n n表示），如码字表示），如码字C=C=（C Cn-1 n-1 C Cn-2n-2C C0 0）。许多个许用码字构成一个码组。）。许多个许用码字构成一个码组。 返回目录第第8章章 差错控制技术差错控制技术124. 检错和纠错的基本概念检错和纠错的基本概念一、基本概念一、基本概念1、码长码长：码字的码元数目，例如：码字的码元数目，例如(n，k)分组码分组码的码长为的码长为n 2、码重码重：指码字中：指码字中“1”的数目，记作的数目，记作W(A)。例如：例如：W(110110)=4 3、码距：又称汉明距
9、码距：又称汉明距，两个等长码对应位不同，两个等长码对应位不同的数目，记作的数目，记作d(A，B)， 例如：例如：A=110110，B=101011，则，则d(A，B)=4 4、码距与码重的关系：码距与码重的关系：d(A，B)=W (A+B) 返回目录第第8章章 差错控制技术差错控制技术135、最小码距、最小码距又称最小汉明距，又称最小汉明距， (n，k)分组码总共有分组码总共有2k个码字，记作个码字，记作Ai（i=0,1,2k-1）,则这些码则这些码字两两之间都有一个码距，定义该字两两之间都有一个码距，定义该(n，k)分组分组码的最小码距为码的最小码距为 ：例如：有一码组集合例如：有一码组集合
10、1 0 1 1 11 1 0 0 10 0 0 1 01 1 0 1 0 12 , 2 , 1 , 0; 12 , 2 , 1 , 0),(dmin0 kkjijijiAAd333422则该码组的最小码距为则该码组的最小码距为2。第第8章章 差错控制技术差错控制技术14检错：检错：验证收到的码字是否是需用码验证收到的码字是否是需用码字即可发现错误字即可发现错误纠错：纠错：能判断出错误发生的位置，将能判断出错误发生的位置，将其纠正其纠正第第8章章 差错控制技术差错控制技术15三、（三、（n, k）分组码的纠检错能力）分组码的纠检错能力一个一个(n，k)分组码的纠检错能力由其最小码距分组码的纠检错
11、能力由其最小码距决定决定 ：1、要在一个码组中检出、要在一个码组中检出e个误码，要求个误码，要求 即任一码组产生小于等于即任一码组产生小于等于e个误码时，都不会个误码时，都不会变成另一准用码组变成另一准用码组。C Ci iC Cj je e1 1d dminmin第第8章章 差错控制技术差错控制技术16C Ci iC Cj jt t1 1t td dminmin第第8章章 差错控制技术差错控制技术173、 要在一个码组中能纠正要在一个码组中能纠正t个误码，同时检个误码，同时检出出e (e t) 个误码个误码 d0 et1 当误码数小于等于当误码数小于等于t时，可纠正误码；时，可纠正误码； 当误
12、码数大于当误码数大于t小于等于小于等于e时，不会落入另一码组时，不会落入另一码组的纠错范围内的纠错范围内。C Ci iC Cj jt t1 1t td dminmine e返回第第8章章 差错控制技术差错控制技术18d0定理定理8-18-1 若一种码的最小距离为若一种码的最小距离为d d0 0，则它能，则它能检查传输差错个数（称为检错能力）检查传输差错个数（称为检错能力）e e应满应满足足d d0 0e+1e+1。定理定理8-2 8-2 若一种码的最小距离为若一种码的最小距离为d d0 0，则它能，则它能纠正传输差错个数（称为纠错能力）纠正传输差错个数（称为纠错能力）t t应满应满足足d d0
13、 02t+1 2t+1 第第8章章 差错控制技术差错控制技术19定理定理8.3 8.3 若一种码的最小距离为若一种码的最小距离为d d0 0，则它能检，则它能检查查e e个错误，同时又能纠正个错误，同时又能纠正t t个以下错误的条个以下错误的条件：件：d d0 0t+e+1t+e+1返回目录第第8章章 差错控制技术差错控制技术208.2差错控制方法差错控制方法利用差错控制编码来控制传输系统的传输差错的方法称做差错控制方法。差错控制编码按照能发现错误和能纠正错误分为检错码、纠错码两类。检错码只能发现错误，而不能纠正错误。纠错码不仅能发现错误，而且能自动纠正错误。返回目录第第8章章 差错控制技术差
14、错控制技术218.2差错控制方法差错控制方法差错控制方法的分类 在数据通信中，利用差错控制编码进行系统传输的差错控制的基本工作方式可分成四类：自动请求重发（ARQ, Automatic Repeat Request）方式前向纠错（FEC，Forword Error Correction）方式混合纠错（HEC，Hybrid Error Correction）方式信息反馈（IRQ，Information Repeat Request）方式 返回目录第第8章章 差错控制技术差错控制技术221、思路、思路这种差错控制方式在发送端对数据序列进行分组这种差错控制方式在发送端对数据序列进行分组编码，加入一定
15、编码，加入一定多余码元多余码元使之具有一定的使之具有一定的检错能力检错能力，成，成为能够发现错误的码组。接收端收到码组后，按一定规为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到出的信息重新传送一次，直到接收端认为已正确接收到信息为止。信息为止。第第8章章 差错控制技术差错控制技术23第第8章章 差错控制技术差错控制技术24（1）停止等候重发）停止等候重
16、发发送端每发送一个码组，就停下来等候，发送端发送端每发送一个码组，就停下来等候，发送端在在Tw时间内发送一个码组，然后等候，等候时间为时间内发送一个码组，然后等候，等候时间为Td，再发送下一个码组，再发送下一个码组，TdTw+反馈时间反馈时间； 收端判断下是否有错，会发送一个应答信号给发送端，收端判断下是否有错，会发送一个应答信号给发送端，发送端收到信号（可以是承认信号也可以是否认信号）发送端收到信号（可以是承认信号也可以是否认信号）后，让发送端在下一个发送时间内发送码组；后，让发送端在下一个发送时间内发送码组； 如果发送无错，则发送应答信号为如果发送无错，则发送应答信号为ACK，让发送端接，
17、让发送端接着发送下一个码组；如果发送出错，则发送应答信号为着发送下一个码组；如果发送出错，则发送应答信号为NAK，要求重发这个出错的码组。，要求重发这个出错的码组。示例动画演示第第8章章 差错控制技术差错控制技术258.2差错控制方法差错控制方法1停等ARQ返回目录停止等待式停止等待式ARQ数据帧在链路上传输的情况数据帧在链路上传输的情况 第第8章章 差错控制技术差错控制技术26示例动画演示第第8章章 差错控制技术差错控制技术278.2差错控制方法差错控制方法2返回N帧ARQ 返回目录返回返回N帧帧ARQ在线路上的传输情况在线路上的传输情况 第第8章章 差错控制技术差错控制技术28（3）选择重
18、发）选择重发发送端连续发送一个码组，一边发送，一发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。边等候接收端的应答信号。 接收端检验，如果发现无错，则发送应答接收端检验，如果发现无错，则发送应答信号信号ACK，则继续发送码组；如果发现有错，则继续发送码组；如果发现有错，则发送应答信号则发送应答信号NAK，如果这个码组出错，发，如果这个码组出错，发送端只需要重发这个出错的码组。送端只需要重发这个出错的码组。 示例动画演示第第8章章 差错控制技术差错控制技术298.2差错控制方法差错控制方法 3选择性重发ARQ返回目录选择性重发选择性重发ARQARQ在线路上的传输情况在线路上的传输情况
19、 第第8章章 差错控制技术差错控制技术303、特点、特点编码效率比较高，对信道的适应能力强编码效率比较高，对信道的适应能力强重发导致信道的有效利用率较低，通信重发导致信道的有效利用率较低，通信的实时性较差的实时性较差译码设备较简单译码设备较简单4、应用、应用数据通信系统数据通信系统第第8章章 差错控制技术差错控制技术31二、前向纠错（二、前向纠错（FEC）1、思路、思路前向纠错系统中，发送端的信道编码器将前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位收端的译码器根据编码规律检验出错误的位置并
20、自动纠正。置并自动纠正。第第8章章 差错控制技术差错控制技术322、特点、特点无需重发，实时性好无需重发，实时性好编码效率较低，译码设备比较复杂编码效率较低，译码设备比较复杂若错误超出纠错码纠错能力若错误超出纠错码纠错能力,只好将其抛弃只好将其抛弃3、应用、应用移动通信系统移动通信系统 第第8章章 差错控制技术差错控制技术331、思路、思路 混合纠错检错方式是前向纠错方式和检错重发方混合纠错检错方式是前向纠错方式和检错重发方式的结合。式的结合。 在这种系统中，发送端发出同时具有检错和纠错在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果能力的码，接收端收到码
21、后，检查错误情况，如果错误少于纠错能力错误少于纠错能力，则，则自行纠正自行纠正；如果干扰严重，；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。向信道要求发端重发。第第8章章 差错控制技术差错控制技术342、特点、特点集合了集合了ARQ和和FEC的优点，在保证系的优点，在保证系统较高的有效性的同时统较高的有效性的同时,大幅度提高了整大幅度提高了整个系统的可靠性个系统的可靠性3、应用、应用移动通信系统移动通信系统 ，数据传输系统，数据传输系统第第8章章 差错控制技术差错控制技术35四、信息反馈（四、信息反馈（IRQ）1、思
22、路、思路接收端把收到的数据序列全部由反向信道送回发接收端把收到的数据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。原数据再次传送，直到发端没有发现错误为止。返回第第8章章 差错控制技术差错控制技术36四、信息反馈（四、信息反馈（IRQ）2、特点、特点不需要纠错、检错的编译码器，设备简单。不需要纠错、检错的编译码器，设备简单。 需要和前向信道相同的反向信道，实时性差。需要和前向信道相同的反向信道，实时性
23、差。 发送端需要一定容量的存储器以存储发送码组，发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。环路时延越大，数据速率越高，所需存储容量越大。返回第第8章章 差错控制技术差错控制技术378.3 常用的简单信道编码常用的简单信道编码1 奇偶监督码奇偶监督码2 行列监督码行列监督码3 恒比码恒比码4 重复码重复码5 正反码正反码返回目录第第8章章 差错控制技术差错控制技术38码重为奇数或偶数的码重为奇数或偶数的(n , n-1)(n , n-1)系统分组码系统分组码)(0)(11010模二偶监督模二奇监督niiniiaa： ITU-TITU-T建议建议同步数
24、据传输使用偶监督同步数据传输使用偶监督异步数据传输使用奇监督异步数据传输使用奇监督监督关系：假设将（监督关系：假设将（n n，n-1n-1）的奇偶监督码的码字）的奇偶监督码的码字记作：记作：a an-1n-1,a,an-2n-2,a,a1 1,a,a0 0，其中，其中a a0 0为监督码元，其为监督码元，其余为信息码元，则各码元满足：余为信息码元，则各码元满足：1 奇偶监督码奇偶监督码返回第第8章章 差错控制技术差错控制技术39对水平方向对水平方向( (共共L L行行) )和垂直方向和垂直方向( (共共M M列列) ,) ,同时进同时进行奇偶监督的码，记作（行奇偶监督的码，记作（LM+L+M+
25、1 , LMLM+L+M+1 , LM）。）。(66(66，50)50)行列监督码的一个码字行列监督码的一个码字 ( (偶监督偶监督) )该码具有很强的纠检错能力，常用于短波散射信该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比道等信道干扰比 较严重的通信中。较严重的通信中。2 行列监督码行列监督码(矩阵校验码矩阵校验码)返回第第8章章 差错控制技术差错控制技术40该码的特点是码字中该码的特点是码字中1 1，0 0数目恒定，亦即数目恒定，亦即1 1，0 0数目之比恒定。数目之比恒定。电传通信中普遍采用电传通信中普遍采用3 3：2 2码，又称码，又称5 5中取中取3 3码：码： 国际上通
26、用的国际上通用的ARQARQ电报通信系统中，采用电报通信系统中，采用7 7中取中取3 3码。码。 3 恒比码恒比码第第8章章 差错控制技术差错控制技术41恒比码的优点：恒比码的优点：（1）简单）简单（2）能检测出单个和奇数个错误，）能检测出单个和奇数个错误，还能部分检测出偶数个错误还能部分检测出偶数个错误（3）适于传输电传机或其他键盘）适于传输电传机或其他键盘设备所产生的数字、字母和符号；但设备所产生的数字、字母和符号；但不适用于信源来的二进制随机数字序不适用于信源来的二进制随机数字序列列返回第第8章章 差错控制技术差错控制技术42 (3 (3，1)1)重复码两个码字为重复码两个码字为0000
27、00和和111111，其最小码，其最小码距为距为3 3； (n(n，1)1)重复码也只有全重复码也只有全0 0码和全码和全1 1码两个码字，码两个码字，其最小码距为其最小码距为n n，却有，却有2 2n n-2-2个禁用码组，随着码个禁用码组，随着码长的增大，其冗余也变得很大；长的增大，其冗余也变得很大；重复码只有一位信息码元，监督码元是重复码只有一位信息码元，监督码元是信息码元的重复，所以仅有两个码字；信息码元的重复，所以仅有两个码字；4 重复码重复码返回第第8章章 差错控制技术差错控制技术43 该码随码长增加，具有很强的纠检错该码随码长增加，具有很强的纠检错能力，但其编码效率的急剧下降；能
28、力，但其编码效率的急剧下降； 重复码并不是一种优秀的编码方案，重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。仅用于速率很低的数据通信系统中。特点：特点：4 重复码重复码返回第第8章章 差错控制技术差错控制技术44该码型多用于该码型多用于1010单位码的前向纠错设备中，可单位码的前向纠错设备中，可以以纠正一位错误纠正一位错误，发现全部，发现全部两个以下两个以下的错误，的错误，以及以及大部分两个以上的错误大部分两个以上的错误，其本质就是五单，其本质就是五单位码的重复；位码的重复；5 正反码正反码第第8章章 差错控制技术差错控制技术45信息码组中信息码组中1 1的数目为奇数时，监督
29、的数目为奇数时，监督码是信息码的重复即正码；码是信息码的重复即正码； 信息码组中信息码组中1 1的数目为偶数时，监的数目为偶数时，监督码是信息码的反码。督码是信息码的反码。5 正反码正反码第第8章章 差错控制技术差错控制技术46例如：例如：M=11001M=11001，则对应得码字为，则对应得码字为M=11101M=11101，则对应得码字为，则对应得码字为5 正反码正反码11001110011110100010第第8章章 差错控制技术差错控制技术47首先将收到的码字中的信息位和监督首先将收到的码字中的信息位和监督位按位按对应位作模对应位作模2 2相加相加，得到一个，得到一个5 5位码位码组组
30、若若接受码字中信息码接受码字中信息码有奇数个有奇数个1 1，则，则将其作为校验码组；若有偶数个将其作为校验码组；若有偶数个1 1，则，则取其反码作为校验码组。取其反码作为校验码组。然后，按照下表进行纠检错译码。然后，按照下表进行纠检错译码。5 正反码正反码第第8章章 差错控制技术差错控制技术48 正反码错误判决表正反码错误判决表 校验码组的形式校验码组的形式错误情况判断错误情况判断1全全“0”传输正确传输正确24个个“1”，1个个“0”信息元有信息元有1位出错，在校验码组中位出错，在校验码组中“0”对应的位置对应的位置34个个“0”，1个个“1”监督元有监督元有1位出错，在校验码组中位出错，在
31、校验码组中“1” 对应的位置对应的位置4其它形式其它形式传输出错，且错误位数大于传输出错，且错误位数大于1返回第第8章章 差错控制技术差错控制技术49接收码字接收码字01101011010110101101，则合成码为，则合成码为 ，信息元中有信息元中有3 3个个1 1，奇数，所以检验码，奇数，所以检验码为为 ，对应表，则传输，对应表，则传输 。接收码字接收码字01010101110101010111，则合成码组，则合成码组为为 ，因为信息元有，因为信息元有2 2个个1 1，偶数，所以，偶数，所以校验码为校验码为 ，则对照表，则对照表， 5 正反码正反码0000000000监督元有监督元有1位
32、出错，在校验码组中位出错，在校验码组中1对应的位置对应的位置正确正确1110100010即监督元即监督元10111中斜体中斜体1出错。出错。第第8章章 差错控制技术差错控制技术50接收码字接收码字01110101100111010110，则合成码，则合成码为为 ，信息元中有，信息元中有3 3个个1 1，则校验，则校验码组码组 ，则错误情况，则错误情况判断：判断：5 正反码正反码传输出错，且错误位数大于传输出错，且错误位数大于1。11000等于合成码组，等于合成码组，11000第第8章章 差错控制技术差错控制技术51返回目录8.4线性分组码线性分组码 8.4.1线性分组码的基本概念线性分组码的基
33、本概念线性分组码（线性分组码（Linear Block Codes）的构成是将信息的构成是将信息序列划分为等长（序列划分为等长（k位）的序列段，共有位）的序列段，共有2k个不同的个不同的序列段。在每一个信息段之后附加序列段。在每一个信息段之后附加r位监督码元位监督码元（Parity Chcck bits），构成长度为），构成长度为n=k+r的分组码的分组码（n，k），当监督码元与信息码元的关系为线性关系），当监督码元与信息码元的关系为线性关系时，构成线性分组码。时，构成线性分组码。 信息位信息位k信息位信息位k 监督位监督位r线性分组码的组成线性分组码的组成第第8章章 差错控制技术差错控制技术
34、522、线性分组码的性质、线性分组码的性质（1）封闭性：指码中任意两许用码组之和）封闭性：指码中任意两许用码组之和仍为一许用码组。仍为一许用码组。（2）线性分组码中必有一个全）线性分组码中必有一个全0码组码组（3）码的最小距离等于非零码的最小重量）码的最小距离等于非零码的最小重量例：已知一个线性分组码的码组集合为：例：已知一个线性分组码的码组集合为： 000000，001110，010101，011011，100011，101101，110110，111000求该码组集合的汉明距离。求该码组集合的汉明距离。解：根据线性分组码的性质可以求出此码组集合的解：根据线性分组码的性质可以求出此码组集合的
35、汉明距离为汉明距离为3。第第8章章 差错控制技术差错控制技术53三、线性分组码编码三、线性分组码编码1、生成矩阵、生成矩阵对于一个（对于一个（n, k）线性分组码，其生成）线性分组码，其生成矩阵矩阵G是是k行行n列的矩阵，只要有列的矩阵，只要有k个线性无个线性无关的关的n元行矢量，都可以构成生成矩阵元行矢量，都可以构成生成矩阵G，生成矩阵不同，则得到的分组码也不同。生成矩阵不同，则得到的分组码也不同。nknkkknnkgggggggggG1, 10 , 10 , 11, 110101, 00100110ggg第第8章章 差错控制技术差错控制技术542、编码原理、编码原理已知已知(n, k)线性
36、分组码线性分组码A=an-1 an-2 a0 1n，其信息码组，其信息码组M=mk-1 mk-2 m1 m0 1k ，则编码过程为：，则编码过程为：1, 10 , 10 , 11, 110101, 00100021nkkknnkkgggggggggmmmMGA第第8章章 差错控制技术差错控制技术55例：例：假设一个假设一个(6，3)分组码生成矩阵为：分组码生成矩阵为： 101100110010101011G编码过程为：编码过程为： 1011001100101010110121020122012mmmmmmmmmmmmmMGA第第8章章 差错控制技术差错控制技术56信息码组信息码组M m2 m1
37、 m0码字码字A a5 a4 a3 a2 a1 a0信息码组信息码组M m2 m1 m0码字码字A a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01 1 11 1 0 1 0 11 1 1 0 0 01 0 0 1 1 01 0 1 0 1 1根据编码原理，输入信息码组根据编码原理，输入信息码组M M，得到相应的码字，得到相应的码字A A。该该(6(6，3)3)码是非系统码，信息元码是非系统码，信息元m m2 2、m m0 0、m m1 1分别出现分
38、别出现在码字在码字A A的第的第1 1、3 3、5 5位，而位，而2 2、4 4、6 6位是编码器产生位是编码器产生的监督码元其码表为：的监督码元其码表为：要想得到系统码，即码组要想得到系统码，即码组A A中，信息位不变，监督位中，信息位不变，监督位附加于其后，则需要将生成矩阵附加于其后，则需要将生成矩阵G G进行典型化。进行典型化。第第8章章 差错控制技术差错控制技术57生成矩阵典型化生成矩阵典型化101100110010101011G101100110010011001G101100110010011001011202012012mmmmmmmmmmmmMGA编码过程编码过程第第8章章 差
39、错控制技术差错控制技术58(6(6，3)3)系统分组码表系统分组码表 监督元与信息元之间的一般关系监督元与信息元之间的一般关系 信息码组信息码组M m2 m1 m0码字码字A a5 a4 a3 a2 a1 a0信息码组信息码组M m2 m1 m0码字码字A a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01 1 11 0 0 1 1 01 0 1 0 1 11 1 0 1 0 11 1 1 0 0 0011202012012345mmmmmmmmmaa
40、aaaaA第第8章章 差错控制技术差错控制技术59系统码中前系统码中前k k位即信息元，将其写成线性方程位即信息元，将其写成线性方程组的形式组的形式034145235aaaaaaaaa监督关系监督关系 000034145235aaaaaaaaa0100110010011001101012345aaaaaa第第8章章 差错控制技术差错控制技术60监督矩阵监督矩阵 监督关系一般表达监督关系一般表达 100110010011001101H0THA0TAH或或生成矩阵典型阵一般形式生成矩阵典型阵一般形式nkrkknkrkkkrrQIqqqqqqqqqG1, 11 , 10, 11, 111101,00
41、100100000100001第第8章章 差错控制技术差错控制技术61(n(n，k)k)分组码码字可表示为分组码码字可表示为 ：(n(n，k)k)码的一般编码过程码的一般编码过程A =an-1 an-2 an-k ar-1 a1 a0 = mk-1 mk-2 m0 ar-1 a1 a0 对上式两边同时进行矩阵转置得：对上式两边同时进行矩阵转置得： QIMMGAkTTkTTTMQIMGA第第8章章 差错控制技术差错控制技术62生成矩阵和监督距阵的关系生成矩阵和监督距阵的关系(n(n，k)k)码的一般编码过程码的一般编码过程0rkrkrrkrkkrkTrTkTQQIQQIIQQIIQQIGH0TG
42、H0THG或 即即 根据需要选定一监督关系确定根据需要选定一监督关系确定H H阵；阵； 求由求由H H距阵和阵的关系确定距阵和阵的关系确定G G阵；阵； 由由A=MGA=MG生成所有码字。生成所有码字。 生成矩阵和监督矩阵是正交生成矩阵和监督矩阵是正交第第8章章 差错控制技术差错控制技术633、伴随式与检错原理、伴随式与检错原理所谓错误图样所谓错误图样E，是由发送码字，是由发送码字A和接收码字和接收码字B进行进行异或运算得到，若异或运算得到，若E0，说明传输无错，即码字，说明传输无错，即码字A与与B相同，相同，但是错误图样只能够反映的是信道噪声的情况，接收端是但是错误图样只能够反映的是信道噪声
43、的情况，接收端是不能依据其来检错。实际上，判断传输是否出错，可以将不能依据其来检错。实际上，判断传输是否出错，可以将接收到的码字接收到的码字B跟分组码的码字进行比较，如果跟分组码的码字进行比较，如果B是分组码是分组码(n,k)的码字，说明传输无错。因此，这里定义了个的码字，说明传输无错。因此，这里定义了个伴随式伴随式S错码的码字，判决传输出不是该错码的码字，判决传输无是该)(0)(0knBknBBHST，伴随式伴随式S S和错误图样和错误图样E E的关系的关系 TTTTTEHEHAHHEABHS)(第第8章章 差错控制技术差错控制技术64(6，3)分组码的监督矩阵为：分组码的监督矩阵为： 伴随
44、式伴随式 100110010011001101H034145235012345012100110010011001101bbbbbbbbbbbbbbbHBsssSTT第第8章章 差错控制技术差错控制技术65 (6，3)分组码伴随式计算电路分组码伴随式计算电路 第第8章章 差错控制技术差错控制技术66（1 1）已知某线形码监督矩阵为）已知某线形码监督矩阵为 试列出所有的许用码组试列出所有的许用码组4、举例、举例第第8章章 差错控制技术差错控制技术67（2）设（）设（7，4）线形码的生成矩阵：）线形码的生成矩阵：当信息位为当信息位为0001时，试求其后的监督位。时，试求其后的监督位。（3）求上题的
45、监督矩阵。）求上题的监督矩阵。返回第第8章章 差错控制技术差错控制技术68四、实例分析四、实例分析(7，4)汉明码汉明码 首先其监督矩阵，此时监督矩阵为首先其监督矩阵，此时监督矩阵为H H3 37 7， 3 3位二进制码元的组合有位二进制码元的组合有8 8种：种： 000000、001001、010010、011011、100100、101101、110110、111111其中不全为零的其中不全为零的7 7个正好可用作监督矩阵的个正好可用作监督矩阵的列列, ,可得到监督矩阵：可得到监督矩阵： 第第8章章 差错控制技术差错控制技术69任意调换监督矩阵各列位置并不影响码的纠错能力，任意调换监督矩阵
46、各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩将其转化成典型阵的形式，并由其可以得到生成矩阵阵G G 101010111001101111000H100110101010110010111H1101000101010001100101110001G由由A=MGA=MG得到其所有的码字，如下表所示：得到其所有的码字，如下表所示： 第第8章章 差错控制技术差错控制技术70假设发送端的码字是假设发送端的码字是A A1515=1111111=1111111，传输过程中第传输过程中第4 4位位a a3 3出现了错误，即接收的码字是出现了错误，即接收的码字是B=1110111
47、B=1110111 此时对应的伴随式为：此时对应的伴随式为： 信息码组信息码组Mm3 m2 m1 m0码字码字Aa6 a5 a4 a3 a2 a1 a0信息码组信息码组Mm3 m2 m1 m0码字码字Aa6 a5 a4 a3 a2 a1 a00 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0 0 0 0 00 0 0 1 0 1 10 0 1 0 1 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 1 0 0 01 0 0 01 0 0 11 0 1
48、 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 11 0 0 0 1 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 1 0 0 11 1 0 0 0 0 11 1 0 1 0 1 01 1 1 0 1 0 01 1 1 1 1 1 1第第8章章 差错控制技术差错控制技术71由于由于S S不是全零，可判断传输出错，不是全零，可判断传输出错，而而S ST T=0 1 1=0 1 1T T，是监督矩阵，是监督矩阵H H的第的第4 4列列, ,这正是错误码这正是错误码元发生的位置元发生的位置, ,因此可以得到错误图样为因此可以得到错误图样为E=00010
49、00E=0001000，进而按，进而按B+EB+E即可即可纠错。纠错。 1101110111100110101010110010111TTHBS第第8章章 差错控制技术差错控制技术72返回目录8.5循环码循环码8.5.18.5.1循环码的基本概念循环码的基本概念1 1循环冗余校验码循环冗余校验码(CRC)(CRC)的定义的定义 循环码是一种线性分组码，如果线性分组码中各码循环码是一种线性分组码，如果线性分组码中各码字中的码元循环左移位（或右移位）所形成的码字字中的码元循环左移位（或右移位）所形成的码字仍然是码组中的一个码字（除全零码外），则这种仍然是码组中的一个码字（除全零码外），则这种码称为
50、循环码。码称为循环码。 第第8章章 差错控制技术差错控制技术73 循环码循环码循环码是一类重要的线性分组码，若循环码是一类重要的线性分组码，若(a(an-1n-1 a an-2n-2 a a0 0) )是循环码的一个码组，则循环移位是循环码的一个码组，则循环移位后的码组：后的码组： (a(an-2n-2 a an-3n-3 a a0 0 a an-1n-1) ) (a (an-3n-3 a an-4n-4 a an-1n-1 a an-2n-2) ) (a (a0 0 a an-1n-1 a a2 2 a a1 1) )仍然是该编码中的码组。仍然是该编码中的码组。 返回目录第第8章章 差错控制
