数据通信原理第章

目的要求•理解差错控制的基本方法和检错、纠错码构成的基本原理。掌握信道编码的基本原理；了解常用检错码的特性；掌握线性分组码的一般特性；掌握汉明码以及循环码的编译码及其实现原理；了解卷积码的基本概念。•本章是本课程的重点。授课内容•6.1差错控制的基本概念•6.2检错和纠错•6.3简单差错控制编码•6.4汉明码•6.5线性分组码•6.6循环码•6.7卷积码•6.8交织码1，数据信号传输过程中，会出现误码。出现误码的原因：（回顾）2，要保证数据通信的可靠性，要求误码率足够低。3，故需要引入差错控制，核心是差错控制编码，又称纠错编码，也称信道编码。一、差错控制所谓差错控制是通过某种方法，发现并纠正传输中出现的错误。它是数据通信系统中提高传输可靠性，降低系统传输误码率的有效措施。6.1差错控制的基本概念返回目录6.1.1差错分类•噪声分类：随机噪声、脉冲噪声。•差错分类：随机差错、突发差错。•随机差错：又称独立差错，是指在随机信道中出现的，彼此独立的、稀疏的、互不相关地发生差错。•突发差错：指在突发信道中出现的，一串串、甚至成片的，密集地、彼此相关地发生的差错。•几个概念•（1）错误图样。•发送序列S：1111111111，•接受序列R：1101001111，•错误图样E：0010110000（S异或R）•突发长度：第一个错误码元和最后一个错误码元之间的码元数目。本例中突发长度为4.•错误密度：第一个错码至最后一个错码之间的错误码元与总码元数之比。本例中错误密度为：3/46.1.2差错控制的基本工作方式•在数据通信系统中，差错控制方式可以分为四种：反馈纠错（ARQ）、前向纠错（FEC）、混合纠错（HEC）和信息反馈（IRQ）四种。一、检错重发或反馈纠错（ARQ）1、思路这种差错控制方式在发送端对数据序列进行分组编码，加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。发收检错码反馈信息2、重发方式在具体实现检错重发系统时，通常有3种形式：停止等候重发返回重发选择重发（1）停止等候重发1，发送端每发送一个码组，就停下来等候，发送端在Tw时间内发送一个码组，然后等候，等候时间为Td，再发送下一个码组，TdTw+反馈时间；2，收端判断下是否有错，会发送一个应答信号给发送端，发送端收到信号（可以是承认信号也可以是否认信号）后，让发送端在下一个发送时间内发送码组。3，如果发送无错，则发送应答信号为ACK，让发送端接着发送下一个码组；如果发送出错，则发送应答信号为NAK，要求重发这个出错的码组。示例动画演示（2）返回重发发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。接收端检验，如果发现无错，则发送应答信号ACK，则继续发送码组；如果发现有错，则发送应答信号NAK，如果这个码组出错，那么发送端要求这个错误码组以后已经发送的码组都要重发。比如接收端第2个码组出错，那么接收端返回NAK应答信号时，发送端正在发送第6个码组，等第6个码组发送完，发送端要从这个有错的码组，即第2个码组开始，把已经发送出去的第2、3、4、5、6个码组都要重发。（3）选择重发发送端连续发送一个码组，一边发送，一边等候接收端的应答信号。接收端检验，如果发现无错，则发送应答信号ACK，则继续发送码组；如果发现有错，则发送应答信号NAK，如果这个码组出错，发送端只需要重发这个出错的码组。3、特点•编码效率比较高，对信道的适应能力强•重发导致信道的有效利用率较低，通信的实时性较差•译码设备较简单4、应用•数据通信系统二、前向纠错（FEC）1、思路•前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。发收纠错码2、特点•无需重发，实时性好•编码效率较低，译码设备比较复杂•若错误超出纠错码纠错能力,只好将其抛弃3、应用•移动通信系统三、混合纠错检错（HEC）•1、思路•混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。发收纠检错码反馈信息2、特点•集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性3、应用•移动通信系统，数据传输系统四、信息反馈（IRQ）1、思路•接收端把收到的数据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。2、特点•不需要纠错、检错的编译码器，设备简单。•需要和前向信道相同的反向信道，实时性差。•发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。返回•6.2前言•差错控制编码（信道编码）的思想：发送端在信息码元序列中加入一些附加码元（监督码元），这些附加码元和信息码元有一定约束关系，一旦传输中发生差错使这种约束关系破坏，收端就可能发现甚至纠正错误。6.2检错和纠错的基本概念一、基本概念1、码长：在信道编码中，码组（码字）中码元的数目称为码组的长度，简称码长，记作n。2、码重：指码组中“1”的数目，记作W(n)。例如：W(110110)=43、许用码组和禁用码组。在信道编码中，被定义用来表示一定信息的码组，称为许用码组，而未被定义的码组称为禁用码组。4、码距：又称汉明距，两个等长码组对应位不同的数目，记作d(A，B)，例如：A=110110，B=101011，则d(A，B)=45、最小码距：又称最小汉明距。在一组编码中，任意两个许用码组间距离的最小值，称为这一编码的最小汉明距。例如：有一码组集合：10111、11001、00010、和11010，该码组最小码距为2二、信道编码的基本概念1、基本思路在发送端被传送的信息码序列的基础上，按照一定的规则加入若干“监督码元”后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则在接收端可以发现传输中的错误，乃至纠正错误。信息码+监督码=码组，称差错控制编码或纠错编码或信道编码（加的监督码越多，差错控制能力越强）2、编码效率将信息序列按照k位码元的长度分成若干个信息码组M，再将信息码组输入到信道编码器，信道编码器按照一定的算法，产生一个新的n位码字A输出，nk；所谓编码效率是指信道编码后码字中信息码元的数目与码字总码元数目之比，记为k/n。6.2.4（n,k）分组码的纠检错能力一个(n，k)分组码的纠检错能力由其最小码距决定：1、要在一个码组中检出e个误码，要求d0e＋1即任一码组产生小于等于e个误码时，都不会变成另一准用码组。CiCje1dmin2、要在一个码组中能纠正t个误码，要求d02t＋1将以t为半径的“球”内所有的禁用码组均判为球心中的准用码组，可纠正t个以内的错误。CiCjt1tdmin3、要在一个码组中能纠正t个误码，同时检出e(et)个误码d0e＋t＋1当误码数小于等于t时，可纠正误码；当误码数大于t小于等于e时，不会落入另一码组的纠错范围内。CiCjt1tdmine返回•结论：编码的最小码距直接关系到这种码的检错和纠错能力；码距越大，检错和纠错能力越强。•对于分组码一般有以下结论：(1)在一个码组内检测e个误码，要求最小码距dmine+1(2)在一个码组内纠正t个误码，要求最小码距dmin2t+1(3)在一个码组内纠正t个误码，同时检测e(et)个误码，要求最小码距：dmint+e+16.2.5信道编码的分类1.按码组的功能分为检错码和纠错码2.按监督码与信息码元之间的关系分为线性码和非线性码（1）线性码：是指监督码元与信息码元之间的关系是线性关系，即可用一组线性代数方程联系起来（2）非线性码：指的是二者是非线性关系3.按照对信息码元处理方法的不同分为分组码和卷积码（1）分组码：是将信息划分为k个码元一组。然后由这k个码元按照一定的规则产生r，从而组成长度n的码组＝k个信息码元＋r个监督码元。分组码一般用符号(n,k)表示，；（2）在卷积码中，每组的监督码元不但与本码组的信息码元有关，而且还与前面若干组信息码元有关。即不是分组监督，而是每个监督码元对它的前后码元都实行监督，前后相连，因此有时也称为连环码。4.按照信息码元在编码后是否保持原形式不变来分为系统码和非系统码（1）系统码：编码后的信息码元保持原样不变（2）非系统码：编码后的信息码元改变了原来的信号形式6.2.5差错控制编码分类检错码按信息码与线性码按功能分按信息码与监督码间约束按纠正错误码类型不同纠错码纠删码分组码（n,k）卷积码纠正随机错误码纠正突发错误码监督码间关系按信息码编码后是否保持原形式按构造的数学方法不同非线性码系统码非系统码代数码几何码算术码6.3简单差错控制编码•6.3.1奇偶监督码•6.3.2恒比码•6.3.3正反码•6.3.4重复码码重为奇数或偶数的(n,n-1)系统分组码)(0)(11010模二偶监督模二奇监督niiniiaa：：ITU-T建议——同步数据传输使用偶监督——异步数据传输使用奇监督监督关系：假设将（n，n-1）的奇偶监督码的码字记作：an-1,an-2,…,a1,a0，其中a0为监督码元，其余为信息码元，则各码元满足：6.3.1奇偶监督码返回•1，奇偶校验只能发现单个或奇数个错误，而不能检测出偶数个错误，因此它的检错能力不高。•2，实际数据传输中所用的奇偶监督分类：水平奇偶监督、垂直奇偶监督、垂直水平奇偶监督（二维奇偶监督）、斜奇偶监督。对水平方向(共L行)和垂直方向(共M列),同时进行奇偶监督的码，记作（LM+L+M+1,LM）。(66，50)行列监督码的一个码字(偶监督)该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比较严重的通信中。11001010001010101010110001111010011100000111100001010000110100010100垂直水平奇偶监督返回该码的特点是码字中1，0数目恒定，亦即1，0数目之比恒定。电传通信中普遍采用3：2码，又称5中取3码，如下所示数字普通五单位码恒比码数字普通五单位码恒比码00110101101500001001111111010101161010110101211001110017111001110031000010110801100011104010101101090001110011国际上通用的ARQ电报通信系统中，采用7中取3码。6.3.2恒比码恒比码的优点：（1）简单（2）能检测出单个和奇数个错误，还能部分检测出偶数个错误（3）适于传输电传机或其他键盘设备所产生的数字、字母和符号；但不适用于信源来的二进制随机数字序列返回该码型多用于10单位码的前向纠错设备中，可以纠正一位错误，发现全部两个以下的错误，以及大部分两个以上的错误，其本质就是五单位码的重复；编码规则：信息码组中1的数目为奇数时，监督码是信息码的重复即正码；信息码组中1的数目为偶数时，监督码是信息码的反码。例如：M=11001，则对应得码字为1100111001M=11101，则对应得码字为11101000106.3.3正反码译码规则：首先将收到的码字重的信息位和监督位按对应位作模2运算，得到一个5位码组（合成码组），若该码字中有奇数个1，则将其作为校验码组，若有偶数个1，则取其反码作为校验码组。然后，按照下表进行纠检错译码。例如：0110101101，则合出码组为00000，信息元中有3个1，奇数，所以检验码组即合成码组00000，对应表，则传输正确。如0