《第8章-差错控制技术要点课件.ppt》由会员分享，可在线阅读，更多相关《第8章-差错控制技术要点课件.ppt（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第8章章 差错控制技术差错控制技术第第8章差错控制技术章差错控制技术 1第第8章章 差错控制技术差错控制技术目的要求目的要求理解差错控制的基本方法和检错、纠错理解差错控制的基本方法和检错、纠错码构成的基本原理。码构成的基本原理。了解常用检错码的特性；了解常用检错码的特性；掌握线性分组码的一般特性；掌握线性分组码的一般特性；掌握汉明码以及循环码的编译码及其实掌握汉明码以及循环码的编译码及其实现原理；现原理；了解卷积码的基本概念。了解卷积码的基本概念。本章是本课程的重点。本章是本课程的重点。2第第8章章 差错控制技术差错控制技术教学内容教学内容 8.1 概述 8.2 差错控制方法 8.3 常用检
2、错码 8.4 线性分组码 8.5 循环码 8.6 卷积码 返回总目录3第第8章章 差错控制技术差错控制技术8.1 引言引言返回目录1引起误码的原因 信道中加性噪声的出现及其大小都是随机的，对这种随机加性干扰，信道一般分为三类：（1）随机信道，即这种信道中存在着随机白色干扰，噪声分布为高斯分布。它造成的误码前后无关，互为独立。（2）突发信道，即突发干扰造成的误码，在短时间内错码连串，误码的出现时前后有关的。造成这种误码的主要干扰是突发脉冲，如电话交换机干扰、闪电及电火花干扰等。这种干扰的出现也是随机的，且干扰幅度大。（3）混合信道，即随机干扰和突发干扰都存在。4第第8章章 差错控制技术差错控制技
3、术8.1 引言引言返回目录5第第8章章 差错控制技术差错控制技术一、差错控制一、差错控制所谓所谓差错控制差错控制是通过某种方法，发现是通过某种方法，发现并纠正传输中出现的错误。它是数据通信并纠正传输中出现的错误。它是数据通信系统中提高系统中提高传输可靠性传输可靠性，降低系统传输误降低系统传输误码率码率的有效措施的有效措施。返回目录6第第8章章 差错控制技术差错控制技术8.1.1差错控制基本概念 在数据通信系统中，对信源输出的二进制的信息序列作某种变换，使原来彼此独立、互不相干的的信息码元序列产生某种规律性（相关性），从而在接收端有可能根据这种规律性来检查，进而检查或纠正传输信号中的差错。变换的
4、方法不同就构成了不同的编码，在系统中使用不同的编码方法就产生了不同的差错控制方法。抗干扰编码可分成两大类，一类是检错码，另一类是纠错码。7第第8章章 差错控制技术差错控制技术1、基本思路、基本思路在发送端被传送的信息码序列的基础上，按在发送端被传送的信息码序列的基础上，按照一定的规则加入若干照一定的规则加入若干“监督码元监督码元”后进行传输，后进行传输，这些加入的码元与原来的信息码序列之间存在着某这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。种确定的约束关系。信息码信息码+监督码监督码=码组，称差错控制编码或纠码组，称差错控制编码或纠错编码或信道编码错编码或信道编码（加的监督码
5、越多，差错控制能力越强）（加的监督码越多，差错控制能力越强）（加的监督码越多，差错控制能力越强）（加的监督码越多，差错控制能力越强）8第第8章章 差错控制技术差错控制技术返回目录2.2.差错控制的基本原理差错控制的基本原理1 1原理描述原理描述 在在二二进进制制编编码码中中，一一位位二二进进制制编编码码可可表表示示两两种种不不同同的的状状态态，两两位位二二进进制制编编码码可可表表示示四四种种不不同同的的状状态态，三三位位二二进进制制编编码码可可表表示示八八种种不不同同的的状状态态，n n位位二二进进制制编编码码可可表表示示2 2n n种种不不同同的的状状态态。在在n n位位二二进进制制编编码码
6、的的2 2n n种种不不同同的的状状态态中中，能能表表示示有有用用信信息息的的码码组组称称为为许许许许可可可可码码码码组组组组。不不表表示示有有用用信信息息的的码码组称为组称为禁用码组禁用码组禁用码组禁用码组。9第第8章章 差错控制技术差错控制技术2举例说明信息码组信息码组M由由k个二进制码元（即比特）组个二进制码元（即比特）组成，所以就有成，所以就有2k个个M；A长度为长度为n，n位长度的码位长度的码字共有字共有2n个，信道编码实质是通过一定个，信道编码实质是通过一定的规则，的规则，从从2n个长度为个长度为n的码字中选择了其中的的码字中选择了其中的2k个，每个，每个被选中的码字称为许用码字；
7、未被选中的个被选中的码字称为许用码字；未被选中的2n-2k个个n长的码字称为禁用码字，反映冗余大小长的码字称为禁用码字，反映冗余大小。10第第8章章 差错控制技术差错控制技术3.3.差错控制编码的特性和能力差错控制编码的特性和能力 差错控制编码的能力与差错控制编码的特性有差错控制编码的能力与差错控制编码的特性有关，编码的特性主要包括码字的汉明重量，码间距离关，编码的特性主要包括码字的汉明重量，码间距离d d，最小码距最小码距d d0 0。在说明这些特性之前，先说明在说明这些特性之前，先说明码元、码字、码码元、码字、码组组之间的关系。码字（用之间的关系。码字（用C C表示）由许多码元组成，表示）
8、由许多码元组成，码字中码元的个数称为码长（用码字中码元的个数称为码长（用n n表示），如码字表示），如码字C=C=（C Cn-1 n-1 C Cn-2n-2CC0 0）。）。许多个许用码字构成一个码组。许多个许用码字构成一个码组。返回目录11第第8章章 差错控制技术差错控制技术4.检错和纠错的基本概念检错和纠错的基本概念一、基本概念一、基本概念1、码长码长：码字的码元数目，例如：码字的码元数目，例如(n，k)分组码分组码的码长为的码长为n2、码重码重：指码字中：指码字中“1”的数目，记作的数目，记作W(A)。例如：例如：W(110110)=43、码距：又称汉明距码距：又称汉明距，两个等长码对应
9、位不同，两个等长码对应位不同的数目，记作的数目，记作d(A，B)，例如：例如：A=110110，B=101011，则，则d(A，B)=44、码距与码重的关系：码距与码重的关系：d(A，B)=W(A+B)返回目录12第第8章章 差错控制技术差错控制技术5、最小码距、最小码距又称最小汉明距，又称最小汉明距，(n，k)分组码总共有分组码总共有2k个码字，记作个码字，记作Ai（i=0,1,2k-1）,则这些码则这些码字两两之间都有一个码距，定义该字两两之间都有一个码距，定义该(n，k)分组分组码的最小码距为码的最小码距为：例如：有一码组集合例如：有一码组集合1011111001000101101033
10、3422则该码组的最小码距为则该码组的最小码距为2。13第第8章章 差错控制技术差错控制技术二、检错和纠错的基本概念二、检错和纠错的基本概念检错：检错：验证收到的码字是否是需用码验证收到的码字是否是需用码字即可发现错误字即可发现错误纠错：纠错：能判断出错误发生的位置，将能判断出错误发生的位置，将其纠正其纠正14第第8章章 差错控制技术差错控制技术三、（三、（n,k）分组码的纠检错能力）分组码的纠检错能力一个一个(n，k)分组码的纠检错能力由其最小码距分组码的纠检错能力由其最小码距决定决定：1、要在一个码组中检出、要在一个码组中检出e个误码，要求个误码，要求d d0 0 ee1 1即任一码组产生
11、小于等于即任一码组产生小于等于e个误码时，都不会个误码时，都不会变成另一准用码组变成另一准用码组。15第第8章章 差错控制技术差错控制技术 2 2、要在一个码组中能纠正要在一个码组中能纠正要在一个码组中能纠正要在一个码组中能纠正t t个误码，要求个误码，要求个误码，要求个误码，要求d d0 0 2t2t1 1 将以将以将以将以t t为半径的为半径的为半径的为半径的“球球球球”内所有的禁用码组均判为球内所有的禁用码组均判为球内所有的禁用码组均判为球内所有的禁用码组均判为球心中的准用码组，可纠正心中的准用码组，可纠正心中的准用码组，可纠正心中的准用码组，可纠正t t个以内的错误个以内的错误个以内的
12、错误个以内的错误。16第第8章章 差错控制技术差错控制技术3、要在一个码组中能纠正要在一个码组中能纠正t个误码，同时检个误码，同时检出出e(e t)个误码个误码d0 et1当误码数小于等于当误码数小于等于t时，可纠正误码；时，可纠正误码；当误码数大于当误码数大于t小于等于小于等于e时，不会落入另一码组时，不会落入另一码组的纠错范围内的纠错范围内。返回17第第8章章 差错控制技术差错控制技术检错和纠错与最小码检错和纠错与最小码d0之间的关系之间的关系定理定理8-18-1 若一种码的最小距离为若一种码的最小距离为d d0 0，则它能则它能检查传输差错个数（称为检错能力）检查传输差错个数（称为检错能
13、力）e e应满应满足足d d0 0e+1e+1。定理定理8-2 8-2 若一种码的最小距离为若一种码的最小距离为d d0 0，则它能则它能纠正传输差错个数（称为纠错能力）纠正传输差错个数（称为纠错能力）t t应满应满足足d d0 02t+1 2t+1 18第第8章章 差错控制技术差错控制技术检错和纠错与最小码之间的关系检错和纠错与最小码之间的关系定理定理8.3 8.3 若一种码的最小距离为若一种码的最小距离为d d0 0，则它能检查则它能检查e e个错误，同时又能纠正个错误，同时又能纠正t t个以下错误的条件：个以下错误的条件：d d0 0t+e+1t+e+1返回目录编码效率：编码效率：在分组
14、码中，加入的监督位越多纠错能在分组码中，加入的监督位越多纠错能力越强，但编码的效率越低。力越强，但编码的效率越低。19第第8章章 差错控制技术差错控制技术8.2差错控制方法差错控制方法利用差错控制编码来控制传输系统的传输差错的方法称做差错控制方法。差错控制编码按照能发现错误和能纠正错误分为检错码、纠错码两类。检错码只能发现错误，而不能纠正错误。纠错码不仅能发现错误，而且能自动纠正错误。返回目录20第第8章章 差错控制技术差错控制技术8.2差错控制方法差错控制方法差错控制方法的分类 在数据通信中，利用差错控制编码进行系统传输的差错控制的基本工作方式可分成四类：自动请求重发（ARQ,Automat
15、ic Repeat Request）方式前向纠错（FEC，Forword Error Correction）方式混合纠错（HEC，Hybrid Error Correction）方式信息反馈（IRQ，Information Repeat Request）方式 返回目录21第第8章章 差错控制技术差错控制技术一、检错重发或反馈纠错（一、检错重发或反馈纠错（ARQ）1、思路、思路这种差错控制方式在发送端对数据序列进行分组这种差错控制方式在发送端对数据序列进行分组编码，加入一定编码，加入一定多余码元多余码元使之具有一定的使之具有一定的检错能力检错能力，成，成为能够发现错误的码组。接收端收到码组后，按
16、一定规为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到出的信息重新传送一次，直到接收端认为已正确接收到信息为止。信息为止。22第第8章章 差错控制技术差错控制技术2、重发方式、重发方式在具体实现检错重发系统时，通常有在具体实现检错重发系统时，通常有3种形式：种形式：停止等候重发停止等候重发返回重发返回重发选择重发选择重发23第第8章章 差错控制技术差错控
17、制技术（1）停止等候重发）停止等候重发发送端每发送一个码组，就停下来等候，发送端发送端每发送一个码组，就停下来等候，发送端在在Tw时间内发送一个码组，然后等候，等候时间为时间内发送一个码组，然后等候，等候时间为Td，再发送下一个码组，再发送下一个码组，TdTw+反馈时间反馈时间；收端判断下是否有错，会发送一个应答信号给发送端，收端判断下是否有错，会发送一个应答信号给发送端，发送端收到信号（可以是承认信号也可以是否认信号）发送端收到信号（可以是承认信号也可以是否认信号）后，让发送端在下一个发送时间内发送码组；后，让发送端在下一个发送时间内发送码组；如果发送无错，则发送应答信号为如果发送无错，则发
18、送应答信号为ACK，让发送端接，让发送端接着发送下一个码组；如果发送出错，则发送应答信号为着发送下一个码组；如果发送出错，则发送应答信号为NAK，要求重发这个出错的码组。，要求重发这个出错的码组。示例动画演示24第第8章章 差错控制技术差错控制技术8.2差错控制方法差错控制方法1停等ARQ返回目录停止等待式停止等待式ARQ数据帧在链路上传输的情况数据帧在链路上传输的情况 25第第8章章 差错控制技术差错控制技术（2）返回重发）返回重发发送端连续发送一个码组，一边发送，一边等候接发送端连续发送一个码组，一边发送，一边等候接发送端连续发送一个码组，一边发送，一边等候接发送端连续发送一个码组，一边发
19、送，一边等候接收端的应答信号。收端的应答信号。收端的应答信号。收端的应答信号。接收端检验，如果发现无错，则发送应答信号接收端检验，如果发现无错，则发送应答信号接收端检验，如果发现无错，则发送应答信号接收端检验，如果发现无错，则发送应答信号ACKACK，则继续发送码组；如果发现有错，则发送应答信号，则继续发送码组；如果发现有错，则发送应答信号，则继续发送码组；如果发现有错，则发送应答信号，则继续发送码组；如果发现有错，则发送应答信号NAKNAK，如果这个码组出错，那么发送端要求这个错误，如果这个码组出错，那么发送端要求这个错误，如果这个码组出错，那么发送端要求这个错误，如果这个码组出错，那么发送
20、端要求这个错误码组以后已经发送的码组都要重发。码组以后已经发送的码组都要重发。码组以后已经发送的码组都要重发。码组以后已经发送的码组都要重发。示例动画演示 接收端第接收端第接收端第接收端第2 2个码组出错，那么接收端返回个码组出错，那么接收端返回个码组出错，那么接收端返回个码组出错，那么接收端返回NAKNAK应应应应答信号时，发送端正在发送第答信号时，发送端正在发送第答信号时，发送端正在发送第答信号时，发送端正在发送第6 6个码组，等第个码组，等第个码组，等第个码组，等第6 6个码个码个码个码组发送完，发送端要从这个有错的码组，即第组发送完，发送端要从这个有错的码组，即第组发送完，发送端要从这
21、个有错的码组，即第组发送完，发送端要从这个有错的码组，即第2 2个个个个码组开始，把已经发送出去的第码组开始，把已经发送出去的第码组开始，把已经发送出去的第码组开始，把已经发送出去的第2 2、3 3、4 4、5 5、6 6个个个个码组都要重发。码组都要重发。码组都要重发。码组都要重发。26第第8章章 差错控制技术差错控制技术8.2差错控制方法差错控制方法2返回N帧ARQ 返回目录返回返回N帧帧ARQ在线路上的传输情况在线路上的传输情况27第第8章章 差错控制技术差错控制技术（3）选择重发）选择重发发送端连续发送一个码组，一边发送，一发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。边
22、等候接收端的应答信号。接收端检验，如果发现无错，则发送应答接收端检验，如果发现无错，则发送应答信号信号ACK，则继续发送码组；如果发现有错，则继续发送码组；如果发现有错，则发送应答信号则发送应答信号NAK，如果这个码组出错，发，如果这个码组出错，发送端只需要重发这个出错的码组。送端只需要重发这个出错的码组。示例动画演示28第第8章章 差错控制技术差错控制技术8.2差错控制方法差错控制方法 3选择性重发ARQ返回目录选择性重发选择性重发ARQARQ在线路上的传输情况在线路上的传输情况 29第第8章章 差错控制技术差错控制技术3、特点、特点编码效率比较高，对信道的适应能力强编码效率比较高，对信道的
23、适应能力强重发导致信道的有效利用率较低，通信的重发导致信道的有效利用率较低，通信的实时性较差实时性较差译码设备较简单译码设备较简单4、应用、应用数据通信系统数据通信系统30第第8章章 差错控制技术差错控制技术二、前向纠错（二、前向纠错（FEC）1、思路、思路前向纠错系统中，发送端的信道编码器将前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位收端的译码器根据编码规律检验出错误的位置并自动纠正。置并自动纠正。31第第8章章 差错控制技术差错控制技术2、特点、特点无需重发，实时性好无需重发，实时性好
24、编码效率较低，译码设备比较复杂编码效率较低，译码设备比较复杂若错误超出纠错码纠错能力若错误超出纠错码纠错能力,只好将其抛弃只好将其抛弃3、应用、应用移动通信系统移动通信系统32第第8章章 差错控制技术差错控制技术三、混合纠错检错（三、混合纠错检错（HEC）1、思路、思路混合纠错检错方式是前向纠错方式和检错重发方混合纠错检错方式是前向纠错方式和检错重发方式的结合。式的结合。在这种系统中，发送端发出同时具有检错和纠错在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力错误少于纠错能力，则，则自行纠正自行纠
25、正；如果干扰严重，；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。向信道要求发端重发。33第第8章章 差错控制技术差错控制技术2、特点、特点集合了集合了ARQ和和FEC的优点，在保证系的优点，在保证系统较高的有效性的同时统较高的有效性的同时,大幅度提高了整大幅度提高了整个系统的可靠性个系统的可靠性3、应用、应用移动通信系统移动通信系统，数据传输系统，数据传输系统34第第8章章 差错控制技术差错控制技术四、信息反馈（四、信息反馈（IRQ）1、思路、思路接收端把收到的数据序列全部由反向信道送回发接收端把收到的数据序列全部由
26、反向信道送回发端，发端比较发送的数据序列与送回的数据序列，端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。原数据再次传送，直到发端没有发现错误为止。返回35第第8章章 差错控制技术差错控制技术四、信息反馈（四、信息反馈（IRQ）2、特点、特点不需要纠错、检错的编译码器，设备简单。不需要纠错、检错的编译码器，设备简单。需要和前向信道相同的反向信道，实时性差。需要和前向信道相同的反向信道，实时性差。发送端需要一定容量的存储器以存储发送码组，发送端需要一定容量的存储器以存储发
27、送码组，环路时延越大，数据速率越高，所需存储容量越大。环路时延越大，数据速率越高，所需存储容量越大。返回36第第8章章 差错控制技术差错控制技术8.3常用的简单信道编码常用的简单信道编码1奇偶监督码奇偶监督码2行列监督码行列监督码3恒比码恒比码4重复码重复码5正反码正反码返回目录37第第8章章 差错控制技术差错控制技术码重为奇数或偶数的码重为奇数或偶数的(n,n-1)(n,n-1)系统分组码系统分组码 ITU-TITU-T建议建议同步数据传输使用偶监督同步数据传输使用偶监督异步数据传输使用奇监督异步数据传输使用奇监督监督关系：假设将（监督关系：假设将（n n，n-1n-1）的奇偶监督码的码字）
28、的奇偶监督码的码字记作：记作：a an-1n-1,a,an-2n-2,a,a1 1,a,a0 0，其中，其中a a0 0为监督码元，其为监督码元，其余为信息码元，则各码元满足：余为信息码元，则各码元满足：1奇偶监督码奇偶监督码返回38第第8章章 差错控制技术差错控制技术对水平方向对水平方向(共共L L行行)和垂直方向和垂直方向(共共M M列列),),同时进同时进行奇偶监督的码，记作（行奇偶监督的码，记作（LM+L+M+1,LMLM+L+M+1,LM）。）。(66(66，50)50)行列监督码的一个码字行列监督码的一个码字 (偶监督偶监督)该码具有很强的纠检错能力，常用于短波散射信该码具有很强的
29、纠检错能力，常用于短波散射信道等信道干扰比道等信道干扰比 较严重的通信中。较严重的通信中。2行列监督码行列监督码(矩阵校验码矩阵校验码)返回39第第8章章 差错控制技术差错控制技术该码的特点是码字中该码的特点是码字中1 1，0 0数目恒定，亦即数目恒定，亦即1 1，0 0数目之比恒定。数目之比恒定。电传通信中普遍采用电传通信中普遍采用3 3：2 2码，又称码，又称5 5中取中取3 3码：码：国际上通用的国际上通用的ARQARQ电报通信系统中，采用电报通信系统中，采用7 7中取中取3 3码。码。3恒比码恒比码40第第8章章 差错控制技术差错控制技术恒比码的优点：恒比码的优点：（1）简单）简单（2
30、）能检测出单个和奇数个错误，）能检测出单个和奇数个错误，还能部分检测出偶数个错误还能部分检测出偶数个错误（3）适于传输电传机或其他键盘）适于传输电传机或其他键盘设备所产生的数字、字母和符号；但设备所产生的数字、字母和符号；但不适用于信源来的二进制随机数字序不适用于信源来的二进制随机数字序列列返回41第第8章章 差错控制技术差错控制技术 (3(3，1)1)重复码两个码字为重复码两个码字为000000和和111111，其最小码，其最小码距为距为3 3；(n(n，1)1)重复码也只有全重复码也只有全0 0码和全码和全1 1码两个码字，码两个码字，其最小码距为其最小码距为n n，却有，却有2 2n n
31、-2-2个禁用码组，随着码个禁用码组，随着码长的增大，其冗余也变得很大；长的增大，其冗余也变得很大；重复码只有一位信息码元，监督码元是重复码只有一位信息码元，监督码元是信息码元的重复，所以仅有两个码字；信息码元的重复，所以仅有两个码字；4重复码重复码返回42第第8章章 差错控制技术差错控制技术 该码随码长增加，具有很强的纠检错该码随码长增加，具有很强的纠检错能力，但其编码效率的急剧下降；能力，但其编码效率的急剧下降；重复码并不是一种优秀的编码方案，重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。仅用于速率很低的数据通信系统中。特点：特点：4重复码重复码返回43第第8章章 差错控
32、制技术差错控制技术该码型多用于该码型多用于1010单位码的前向纠错设备中，可单位码的前向纠错设备中，可以以纠正一位错误纠正一位错误，发现全部，发现全部两个以下两个以下的错误，的错误，以及以及大部分两个以上的错误大部分两个以上的错误，其本质就是五单，其本质就是五单位码的重复；位码的重复；5正反码正反码44第第8章章 差错控制技术差错控制技术信息码组中信息码组中1 1的数目为奇数时，监督的数目为奇数时，监督码是信息码的重复即正码；码是信息码的重复即正码；信息码组中信息码组中1 1的数目为偶数时，监的数目为偶数时，监督码是信息码的反码。督码是信息码的反码。5正反码正反码45第第8章章 差错控制技术差
33、错控制技术例如：例如：M=11001M=11001，则对应得码字为，则对应得码字为M=11101M=11101，则对应得码字为，则对应得码字为5正反码正反码1100111001111010001046第第8章章 差错控制技术差错控制技术首先将收到的码字中的信息位和监督首先将收到的码字中的信息位和监督位按位按对应位作模对应位作模2 2相加相加，得到一个，得到一个5 5位码位码组组若若接受码字中信息码接受码字中信息码有奇数个有奇数个1 1，则，则将其作为校验码组；若有偶数个将其作为校验码组；若有偶数个1 1，则，则取其反码作为校验码组。取其反码作为校验码组。然后，按照下表进行纠检错译码。然后，按照
34、下表进行纠检错译码。5正反码正反码47第第8章章 差错控制技术差错控制技术 正反码错误判决表正反码错误判决表 校验码组的形式校验码组的形式 错误情况判断错误情况判断1全全“0”传输正确传输正确24个个“1”，1个个“0”信息元有信息元有1位出错，在校验码组位出错，在校验码组中中“0”对应的位置对应的位置34个个“0”，1个个“1”监督元有监督元有1位出错，在校验码组位出错，在校验码组中中“1”对应的位置对应的位置4其它形式其它形式传输出错，且错误位数大于传输出错，且错误位数大于1返回48第第8章章 差错控制技术差错控制技术接收码字接收码字01101011010110101101，则合成码为，则
35、合成码为 ，信息元中有信息元中有3 3个个1 1，奇数，所以检验码为，奇数，所以检验码为 ，对应表，则传输，对应表，则传输 。接收码字接收码字01010101110101010111，则合成码组为，则合成码组为 ，因为信息元有，因为信息元有2 2个个1 1，偶数，所以校验码为，偶数，所以校验码为 ，则对照表，则对照表，5正反码正反码0000000000监督元有监督元有1位出错，在校验码组中位出错，在校验码组中1对应的位置对应的位置正确正确1110100010即监督元即监督元10111中斜体中斜体1出错。出错。49第第8章章 差错控制技术差错控制技术接收码字接收码字011101011001110
36、10110，则合成码为，则合成码为 ，信息元中有，信息元中有3 3个个1 1，则校验码组，则校验码组 ，则错误情况判断：，则错误情况判断：5正反码正反码传输出错，且错误位数大于传输出错，且错误位数大于1。11000等于合成码组，等于合成码组，1100050第第8章章 差错控制技术差错控制技术返回目录8.4线性分组码线性分组码 8.4.1线性分组码的基本概念线性分组码的基本概念线线性性分分组组码码（Linear Block Codes）的的构构成成是是将将信信息息序序列列划划分分为为等等长长（k位位）的的序序列列段段，共共有有2k个个不不同同的的序序列列段段。在在每每一一个个信信息息段段之之后后
37、附附加加r位位监监督督码码元元（Parity Chcck bits），构构成成长长度度为为n=k+r的的分分组组码码（n，k），当当监监督督码码元元与与信信息息码码元元的的关关系系为为线线性性关关系系时，构成线性分组码。时，构成线性分组码。信息位信息位k信息位信息位k 监督位监督位r线性分组码的组成线性分组码的组成51第第8章章 差错控制技术差错控制技术2、线性分组码的性质、线性分组码的性质（1）封闭性：指码中任意两许用码组之和）封闭性：指码中任意两许用码组之和仍为一许用码组。仍为一许用码组。（2）线性分组码中必有一个全）线性分组码中必有一个全0码组码组（3）码的最小距离等于非零码的最小重量）
38、码的最小距离等于非零码的最小重量例：已知一个线性分组码的码组集合为：例：已知一个线性分组码的码组集合为：000000，001110，010101，011011，100011，101101，110110，111000求该码组集合的汉明距离。求该码组集合的汉明距离。解：根据线性分组码的性质可以求出此码组集合的解：根据线性分组码的性质可以求出此码组集合的汉明距离为汉明距离为3。52第第8章章 差错控制技术差错控制技术三、线性分组码编码三、线性分组码编码1、生成矩阵、生成矩阵对于一个（对于一个（n,k）线性分组码，其生成）线性分组码，其生成矩阵矩阵G是是k行行n列的矩阵，只要有列的矩阵，只要有k个线性
39、无个线性无关的关的n元行矢量，都可以构成生成矩阵元行矢量，都可以构成生成矩阵G，生成矩阵不同，则得到的分组码也不同。生成矩阵不同，则得到的分组码也不同。53第第8章章 差错控制技术差错控制技术2、编码原理、编码原理已知已知(n,k)线性分组码线性分组码A=an-1an-2a01n，其信息码组，其信息码组M=mk-1mk-2m1m01k，则编码过程为：则编码过程为：54第第8章章 差错控制技术差错控制技术例：例：假设一个假设一个(6，3)分组码生成矩阵为：分组码生成矩阵为：编码过程为：编码过程为：55第第8章章 差错控制技术差错控制技术信息码组信息码组Mm2m1m0码字码字Aa5a4a3a2a1
40、a0信息码组信息码组Mm2m1m0码字码字Aa5a4a3a2a1a0000001010011000000001101010011011110100101110111110101111000100110101011根据编码原理，输入信息码组根据编码原理，输入信息码组M M，得到相应的码字，得到相应的码字A A。该该(6(6，3)3)码是非系统码，信息元码是非系统码，信息元m m2 2、m m0 0、m m1 1分别出现分别出现在码字在码字A A的第的第1 1、3 3、5 5位，而位，而2 2、4 4、6 6位是编码器产生位是编码器产生的监督码元其码表为：的监督码元其码表为：要想得到系统码，即码组
41、要想得到系统码，即码组A A中，信息位不变，监督位中，信息位不变，监督位附加于其后，则需要将生成矩阵附加于其后，则需要将生成矩阵G G进行典型化。进行典型化。56第第8章章 差错控制技术差错控制技术生成矩阵典型化生成矩阵典型化编码过程编码过程57第第8章章 差错控制技术差错控制技术(6(6，3)3)系统分组码表系统分组码表 监督元与信息元之间的一般关系监督元与信息元之间的一般关系 信息码组信息码组Mm2m1m0码字码字Aa5a4a3a2a1a0信息码组信息码组Mm2m1m0码字码字Aa5a4a3a2a1a000000101001100000000110101001101111010010111
42、011110011010101111010111100058第第8章章 差错控制技术差错控制技术系统码中前系统码中前k k位即信息元，将其写成线性方程位即信息元，将其写成线性方程组的形式组的形式监督关系监督关系 59第第8章章 差错控制技术差错控制技术监督矩阵监督矩阵 监督关系一般表达监督关系一般表达 或或生成矩阵典型阵一般形式生成矩阵典型阵一般形式60第第8章章 差错控制技术差错控制技术(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
43、a0 对上式两边同时进行矩阵转置得：对上式两边同时进行矩阵转置得：61第第8章章 差错控制技术差错控制技术生成矩阵和监督距阵的关系生成矩阵和监督距阵的关系(n(n，k)k)码的一般编码过程码的一般编码过程或 即即 根据需要选定一监督关系确定根据需要选定一监督关系确定H H阵；阵；求由求由H H距阵和阵的关系确定距阵和阵的关系确定G G阵；阵；由由A=MA=MG G生成所有码字。生成所有码字。生成矩阵和监督矩阵是正交生成矩阵和监督矩阵是正交62第第8章章 差错控制技术差错控制技术3、伴随式与检错原理、伴随式与检错原理所谓错误图样所谓错误图样E，是由发送码字，是由发送码字A和接收码字和接收码字B进
44、行进行异或运算得到，若异或运算得到，若E0，说明传输无错，即码字，说明传输无错，即码字A与与B相同，相同，但是错误图样只能够反映的是信道噪声的情况，接收端是但是错误图样只能够反映的是信道噪声的情况，接收端是不能依据其来检错。实际上，判断传输是否出错，可以将不能依据其来检错。实际上，判断传输是否出错，可以将接收到的码字接收到的码字B跟分组码的码字进行比较，如果跟分组码的码字进行比较，如果B是分组码是分组码(n,k)的码字，说明传输无错。因此，这里定义了个的码字，说明传输无错。因此，这里定义了个伴随式伴随式S伴随式伴随式S S和错误图样和错误图样E E的关系的关系 63第第8章章 差错控制技术差错
45、控制技术(6，3)分组码的监督矩阵为：分组码的监督矩阵为：伴随式伴随式 64第第8章章 差错控制技术差错控制技术(6，3)分组码伴随式计算电路分组码伴随式计算电路 65第第8章章 差错控制技术差错控制技术（1 1）已知某线形码监督矩阵为）已知某线形码监督矩阵为 试列出所有的许用码组试列出所有的许用码组4、举例、举例66第第8章章 差错控制技术差错控制技术（2）设（）设（7，4）线形码的生成矩阵：）线形码的生成矩阵：当信息位为当信息位为0001时，试求其后的监督位。时，试求其后的监督位。（3）求上题的监督矩阵。）求上题的监督矩阵。返回67第第8章章 差错控制技术差错控制技术四、实例分析四、实例分
46、析(7，4)汉明码汉明码 首先其监督矩阵，此时监督矩阵为首先其监督矩阵，此时监督矩阵为H H3 37 7，3 3位二进制码元的组合有位二进制码元的组合有8 8种：种：000000、001001、010010、011011、100100、101101、110110、111111其中不全为零的其中不全为零的7 7个正好可用作监督矩阵的个正好可用作监督矩阵的列列,可得到监督矩阵：可得到监督矩阵：68第第8章章 差错控制技术差错控制技术任意调换监督矩阵各列位置并不影响码的纠错能力，任意调换监督矩阵各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩阵将其转化成典型阵的形式，并由其
47、可以得到生成矩阵G G 由由A=MGA=MG得到其所有的码字，如下表所示：得到其所有的码字，如下表所示：69第第8章章 差错控制技术差错控制技术假设发送端的码字是假设发送端的码字是A A1515=1111111=1111111，传输过程中第传输过程中第4 4位位a a3 3出现了错误，即接收的码字是出现了错误，即接收的码字是B=1110111 B=1110111 此时对应的伴随式为：此时对应的伴随式为：信息码组信息码组Mm3m2m1m0码字码字Aa6a5a4a3a2a1a0信息码组信息码组Mm3m2m1m0码字码字Aa6a5a4a3a2a1a00000000100100011010001010
48、110011100000000001011001010100111100100110010110101100110111000100010011010101111001101111011111000111100110010100101011001110000111010101110100111111170第第8章章 差错控制技术差错控制技术由于由于S S不是全零，可判断传输出错，不是全零，可判断传输出错，而而S ST T=0 1 1=0 1 1T T，是监督矩阵，是监督矩阵H H的第的第4 4列列,这正是错误码元这正是错误码元发生的位置发生的位置,因此可以得到错误图样为因此可以得到错误图样为E
49、=0001000E=0001000，进而按，进而按B+EB+E即可即可纠错。纠错。71第第8章章 差错控制技术差错控制技术返回目录8.5循环码循环码8.5.18.5.1循环码的基本概念循环码的基本概念1 1循环冗余校验码循环冗余校验码(CRC)(CRC)的定义的定义 循环码是一种线性分组码，如果线性分组码中各码循环码是一种线性分组码，如果线性分组码中各码字中的码元循环左移位（或右移位）所形成的码字字中的码元循环左移位（或右移位）所形成的码字仍然是码组中的一个码字（除全零码外），则这种仍然是码组中的一个码字（除全零码外），则这种码称为循环码。码称为循环码。72第第8章章 差错控制技术差错控制技术
50、循环码循环码循环码是一类重要的线性分组码，若循环码是一类重要的线性分组码，若(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)仍然是该编码中的码组。仍然是该编码中的码组。返回目录73第第8章章 差错控制技术差错控制技术一个一个(7(7，3)3)系统循环码系统循环码 码表如下所示：码表如下所示