资源描述
第4章 数据通信中的差错控制技术,内容提要：,差错控制的基本方式 反馈重发纠错（ARQ）方式 前向纠错（FEC）方式 混合纠错（HEC）方式 常用检错码： 奇偶监督码 行列监督码 恒比码 海明码,数据通信中的差错控制技术,在数据传输中，可靠性是一个重要的性能指标，由于传输信道不理想以及来自各个方面的干扰，出现错误码元是不可避免的。 随着现代数据处理系统的不断发展以及传输速率的不断提高，对信息码元的差错概率误码率Pe的要求也在提高。 计算机与计算机之间的数据传输，要求低于109。,数据通信中的差错控制技术,如果不加处理地把信息直接送入信道，这样的信息码元是没有任何检、纠错能力的。 信道编码：为了克服干扰，增加传输的可靠性，需要引入差错控制技术。 差错控制技术：其实质是在信息码元中增加一定数量的多余码元（称为监督码元），即由信信息码元和监督码元共同组成一个码字，二者之间满足一定的约束关系。,数据通信中的差错控制技术,传输过程中若受到干扰，某位码元发生了变化，相当于破坏了它们之间的约束关系。 接收端通过检验这种约束关系是否成立，完成识别错误或者进一步判定错误位置并加以纠正的工作，从而保证可靠性。,差错控制的基本方式,差错控制的基本方式主要有以下三种： 1.反馈重发纠错（ARQ）方式 2.前向纠错（FEC）方式 3.混合纠错（HEC）方式,1.反馈重发纠错（ARQ）方式,反馈重发纠错（ARQ）又称判决反馈纠错。 它的工作原理是： 发送端对原始数据进行差错控制编码，产生可以检测出错误的发送序列，将被传数据按8位分组，每组后面附加校验位，使之成为码长为n的校验序列（nk）。,反馈重发纠错（ARQ）方式,接收机根据收到的码元序列中附加校验位的编码规则，进行判决。 判决结果通过反馈信道回传，无错认可（ACK），有错否认（NAK）。 发送端根据回传指令，将有错的码组重传，直到正确接收为止。,图是反馈重发纠错（ARQ）方式的原理示意图,ARQ系统（反馈重发纠错）,实际的ARQ系统又可分为三种类型： 停止等待ARQ（半双工） 连续ARQ（全双工） 选择重发ARQ（全双工）。, 停止等待ARQ （解释）,停止等待ARQ是最简单的ARQ系统。 实际过程：发送端每发送一个码组就停止并等待接收端的应答信号。得到确认信号（ACK）后，发下一个码组；收到否认信号（NAK），重发此码组。 应用范围： 半双工，操作简单，需缓冲存储器的容量小，等待应答费时，传输效率低，仅适用于低速传输系统和信号往返延迟不大的情况。,如图, 连续 ARQ,在该系统中，收、发两端可同时发送信息，发送端通过前向信道发送消息数据，接收端通过反向信道发送应答信号。 发送端按顺序发送各码组，在收到否认信号时，返回并重发有错的码组及其后面顺序相接的各级。,连续 ARQ,图（b）连续ARQ原理图。收到否认应答信号与重传码组之间相隔4个码组，发送端收到否认应答后，要退回4个码组重发。 该方式需要全双工连接。当信道较好、错码组较少时，连续ARQ的传输效率很高。 主要缺点：是对缓冲器容量有要求（容量大小由传播延迟时间决定）。, 选择重发ARQ（全双工）,选择重发ARQ，它的发送端仅重发接收出错的码组，如图（c）。 在信道差错率高时，性能较好； 需要复杂的控制逻辑和大容量的缓冲器，在应答信号中还必须标明出错码组编号，就增加了系统的复杂性。,ARQ 方式的选择,ARQ方式的选择：使用通信资源以及需要全双工通信等因素考虑。 反馈重发纠错方式的优点：是检错码构造简单，不需要复杂的编、译码设备，在冗余度一定的条件下，检错码比纠错码的纠错能力强多。 ARQ的缺点：不能单向传输、要反馈信道，适用于双向通信，该方式要求数据源必须是可控的，并配置缓冲设备。,2. 前向纠错（FEC）方式,前向纠错，又称自动纠错，下图为前向纠错（FEC）系统框图。 图中发送端将原始数据进行纠错编码后送入信道，接收端在对信号能自动纠正错误码元。,前向纠错（FEC）方式,前向纠错（FEC）方式,优点：不需要反馈信道，纠错迅速、及时，具有恒定的信息传输速率。 缺点：译码设备复杂，需纠正较多位的突发错码，要附加较多的监督码元，增加了译码算法选择的难度，降低了传输效率，不适宜应用于传输条件恶化的信道。,3. 混合纠错（HEC）方式,混合纠错（HEC）方式：FEC和ARQ两种纠错方式的结合。 发送端发出具有一定纠错能力和较高检错能力的码字，由信道编码而附加的监督码元并不多。 典型的HEC系统框图如图所示。在ARQ系统中包含一个FEC子系统。,混合纠错（HEC）方式,接收端检测数据码流，发现错误时，先由FEC子系统自动纠错，当错误较多超出纠错能力时，再发反馈信息要求重发，减少了重发次数。,混合纠错（HEC）方式,这种方式：弥补了反馈重发和前向纠错两种方式的缺点，发挥了码的检、纠错能力，在较强干扰的信道中仍可获得较低误码率，通信中应用较多。,纠错编码的基本原理,表 41 分组码示意,1海明（Hamming）距离,海明（Hamming）距离，即两个不同的码组，其对应的码位的码元不同的个数，用d表示，可以写做 式中，aji 、aki 分别为第 k 码组和第 j 码组的第位码元， n 为码组长度。 表示模2加。 例如，码组（01）和（00）海明距离的为1。（110）和（101）的海明距离为2。,最小距离,一个码组中，任何两个码组间海明距离最小值称为该码组的最小码距。用 d0 表示： （4.2 ） 海明距离增大了，原来8个码组都使用时；在（000），（011），（101），（110）4个两组集合中，最小距离=2，而码组集合（000），（111）最小距离=3。由此可见，码组的最小距离越大，其抗干扰能力越强。,3最小码距与编码的检错和纠错能力的关系,差错控制编码的抗干扰能力与码的结构有关，编码的结构可用该码的距离特性描述，差错控制编码的距离可以反映该码的抗干扰能力。 对于n =3的编码组，可以在三维空间中说明码距的几何意义。,3位的码共有8种不同的可能码组。在三维空间中它们分别位于一个单位立方体的各顶点上。 每一码组的3个码元的值（a2,a1,a0）就是此立方体各顶点的坐标。码距概念在此图中则对应于各顶点之间沿立方体各边的几何距离。,最小码距与编码的检错和纠错能力的关系,最小码距与编码的检错和纠错能力的关系,图47码距与检错和纠错能力的关系,（1）为检测e个错码，要求最小码距 d0e1 （4.3）,（2）为纠正t个错码，要求最小码距（b） d02t1 （4.4）（3）为纠正t个错码，同时检测e个错码（c） 要求最小码距d0et1（et）（4.5）,最小码距与编码的检错和纠错能力的关系,例4.1求码集合（000）、（011）、（101）、（110）和（000）、（111）最小距离及纠（检）错的能力。,解：（1）最小距离 第一组,最小码距与编码的检错和纠错能力的关系,例4.1求码集合(2),第二组 000 111 111 所以最小距离3。,例4.1求码集合(3),（2）对第一组集合，由式（4.3 ） 求得ed0 1211，可检测出一个错。 （3）对第二组集合，由式（4.3）求得 ed0 1312，可检测出二个错。 当用于纠错时，由式（4.4）求得 能纠正一个错。,例4.1求码集合(4),（4）对第二组集合，由式（4.5），可求出 e+td0 1312 所以e1，t1，即纠错、检错各1。,求码集合,在随机信道中发送“0”时的错误概率和发送“1”时的相等，都等于p，且p1，容易证明，在码长为n的码组中恰好发生r个错码的概率为,求码集合,例如，当码长n=7，p=10-3 时，则有,采用差错控制编码，能纠正（或检测）这种码组中的12个错误，使误码率下降几个数量级。 较简单的差错控制编码具有较大的实际应用价值。,4.5.2 常用检错码,常用检错码的构造一般都很简单，但因其具有较强的检错能力，且易于实现，所以实际中应用较多。 1.奇偶监督码 2.行列监督码 3.恒比码 4.海明码,常用的简单编码,1奇偶监督码 码组中“1”的数目为偶数： （4.7） 式中，a0为监督位，其他为信息位。 奇数监督码与其相似，其码组中“1”的数目为奇数，即满足条件 （4.8）,1. 奇偶监督码,奇偶监督码又称奇偶校验码，它只有一个监督元，是一种最简单的检错码，在计算机内部的数据传送以及输入输出设备中得到了广泛的应用。,奇偶监督码,编码方法：在每个信息码组之后附加一位监督码元，称为奇校验或偶校验。 错码的检测：当错码为奇数个时，因打乱了“1”数目的奇偶性，能发现差错。 缺陷：错码为偶数时，不能发现偶数个错码。,2. 行列监督码,行列监督码也叫方阵校验码，可以克服奇偶监督码不能发现偶数个差错的缺点，还能纠正某些位置的错码。 基本原理与简单的奇偶监督码相似，不同点在于每个码元都要受到纵、横两个方向的监督。,行列监督码,以图为例，有28个待发送的数据码元，排成4行7列的方阵。方阵中每行是一个码组，每行、每列的最后加上一个监督码元进行列监督，然后按行（或列）发送。,行列监督码,行列监督码,接收端按同样行列排成方阵，发现不符合行列监督规则的判决有错。 方阵码只是对构成矩形四角的错码无法检测，故其检错能力较强。 使误码率降至原误码率的百分之一到万分之一。,行列监督码(含突发错码),当差错个数恰为4的倍数，且差错位置正好构成矩形的四个角时（如上图所示方阵码中标有D的码元），方阵码检查不出错误。,含突发错码行列监督码,行列监督码,接收端按同样行列排成方阵，发现不符合行列监督规则的判决有错。 行列监督码在某些条件下还能纠错。,突发差错行列监督码,行列监督码也常用于检查或纠正突发差错。可以检查出错误码元长度小于或等于码组长度的所有错码，并纠正某些情况下的突发差错。,3. 恒比码(3:2),恒比码又称等比码或等重码（非零码组中“1”码的个数称为码重）。恒比码的每个码组中，“1”和“0”的个数之比都是恒定的。,3恒比码,表4-2 恒比码和5单元国际电码,恒比码,我国电报通信中采用的3：2等比码，也叫五中取三码，在5单位电传码的码组中（25 32），取其“1”的数目恒为3的码组（ ），代表十个字符（09）。 除10种许用码组外，还有22种禁用码组，其多余度较高，经验表明：能使差错减至原来的十分之一左右。,恒比码,恒比码在检测时，通过计算接收码组中“1”的数目，判定传输有无错误。这种码除了“1”错成“0”和“0”错成“1”成对出现的错误以外，还能发现其他所有形式的错误，故检错能力很强。 应用这类码后，国际电报的误字率保持在 10-6以下。,4.5.3 纠错编码,现行的抗干扰编码发展成为两大类：分组码和卷积码。 分组码：每组监督元只监督本组信息码，与其他码组无关，具有分组独立监督的作用； 卷积码：监督位可监督前后信息码组，具有连环监督的作用，也称之为连环码。 共同点：监督码元和信息码元之间，满足各自的数学关系。,1. 线性分组码,长为n的分组码，码字由两部分构成：信息码元（k位） 监督码元（n-k位）。 监督元：根据一定规则由信息码元变换得到的，变换规则不同就构成不同的分组码。 如果码字中的监督位为信息位的线性组合：它们之间由一个线性（一次）方程来联系，就称其为线性分组码。,4.5 线性分组码,海明码：能够纠正一位错码且编码效率较高的线性分组码。 （4.9） 若S0，认为无错；若S1，认为有错。式（4.9）称为监督关系式，S称为校正子。由于校正子S的取值有两种，只能代表有错和无错这两种信息，不能指出错码的位置。,线性分组码,码长为n，信息位数为k，则监督位数为rnk。用个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求: （4.10） 设分组码（n，k）中k4。为了纠正一位错码，由式（4.10）可知，要求监督位数r3。 若取r=3，则 。,线性分组码,错码位置在a2、a4、a5或a6时，校正子S1为1；否则S1为0。这就意味着a2、a4、a5和a6四个码元构成偶数监督关系： （4.11） 同理，a1、a3、a5和a6构成偶数监督关系： （4.12） （4.13）,表43 错码位置示意图,线性分组码中的监督位,即监督位应使上三式中S1、S2和S3的值为零（表示编成的码组中应无错码）。 由上式经移项运算，解出监督位：,表44 （7，4）汉明码,上述方法构造的码称为汉明码。表中所列的（7, 4）海明码的最小码距d03,因此，根据式（4.3）和式（4.4）可知，这种码能纠正一个错码或检测两个错码。,2.循环码,线性分组码中有一个主要的码是循环码。 它可以用现代代数理论进行分析和构造，是计算机通信中常用的一种检、纠错码。 循环码除了具有一般线性分组码的特性外，还具有循环性。 考查一组（7，3）循环码，它有3个信息元，4个监督元，监督元与信息元之间存在线性关系,2.循环码,循环码表,循环码表表45,循环码表,循环码除了具有线性码的一般性质外，还具有循环性，即循环码中任一码组循环移位一位（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。 在表4-5中给出一种（7，3）循环码的全部码组。由此表可以直观看出这种码的循环性。,循环码表,2号码字（0010111）为例，左移循环一位变3号码（0101110），依次左移一位构成的状态图如下：,3.循环码的产生,例如，表中的 第2码组向右移一位即得到第5码组； 第6码组向右移一位即得到第7码组。 一般来说，若（a n-1an-2a0）是一个循环码组，则（a n-2an-3a0 a n-1），（a n-3an-4an-1 a n-2）（a 0an-1a2 a 1）也是该编码中的码组。,循环码的产生,竖式为：,1.码多项式的按模运算,在整数运算中，有模n运算。例如，在模2运算中，有1+1=2=0（模2），1+2=3=1（模2），2 3=6=0（模2）等。若一整数m可以表示为 Q为整数。,码多项式的按模运算,在码多项式运算中也有类似的按模运算。若一任意多项式F（x）被一n次多项式N（x）除，得到商式Q（x）和一个次数小于n的余式R（x）。即 模,码多项式的按模运算,码多项式的按模运算,即循环码的生成多项式应该是 的一个 次因式。例如， 可以分解为,2循环码的生成矩阵G,例如，在表45所给出的循环码中 可见，唯一的一个 次码多项式代表的码组是第二码组0010111，相对应的码多项式（即生成多项式） 将此 代入上式，得到,循环码的生成矩阵G,可以写出此循环码组，即,4.8.1 其他差错控制方式,其它几种差错控制方法。 1冗余法 冗余法的基本思想是发送端发送两份完全相同的文件，接收端接收完两份文件后；首先进行比较，如果两份文件完全相同，则接受此文件。否则，接收端将要求发送端再重发。,2多数表决法,多数表决法也叫重复码。最简单的能纠正错误的办法是将有用信息重复传送几次，只要正确的次数多于传错的次数，就用少数服从多数的原则排除差错，这就是简单的重复码的原理。 多数表决法如图419所示。,多数表决法,（1）逐位重复：即每个信息连续传几次。例如，若原始信息为10110100则三重码为111000111111000111000000 （2）分段重复：即所传信息按固定位数分段，每段信息连续传几次，例如，若四位为一段，那么对上述同样的信息10110100可得三重码为：1011，1011，1011，0100，0100，0100，,3. 反正码,反正码是一种能简单纠正错码的编码，多用于10单位电码的前向自动纠错设备中，5单位电码的重复，能纠正一位差错，发现大部分两位以上的差错。 （1）当信息码中“1”的个数是奇数时，监督码与信息码相同，这种情况称监督码为信息码的“正码”。 （2）当信息码中的“ 1”是偶数个时，监督码是信息码的反码，即“0”和“1”互换，正反码的名称即由此而来。,反正码,例如1： 若信息码为11010则监督码为11010构成的码组为1101011010 若信息码为10100，则监督码为01011，构成的码组为1010001011。,表49 正反码的判决,正反码的判决,例如，发送码组为（1101011010），若无传输差错，则收到的仍为（1101011010），合成码组应为 11010 1101000000 由于接收码中信号码（前 5位）“ 1”的个数为奇数，故检验码组即为 00000，按表4-9判决无错码。,正反码的判决,若传输过程出现差错，收到的码组为（1001011010）则合成码组应为 10010 1101001000 由于接收码组中信息码有偶数个“1”，故检验码组应是合码的反码，即10111，按表49判决，信息码有一位错码，差错位置即为检验码的“0”所对应位置，即信息码第二位为错码。,正反码的判决,若收到的码组为（1101001010）此时合成码组为 11010 0101010000 由于接收码组中信息码有奇数个“1”，故检验码组就是10000。按表49判决，监督码第一位为错码。,正反码的判决,又若接收的码组为（1000011010），则合成码组为 10000 1101001010 因接收码中信息有奇数个“1”，故检验码组即为01010。按表4-9检验码组中出现两个“1”属其他情况，判决差错个数大于1个，不能自动纠正。只能通过其他办法来改正这个差错。,小 结,差错控制编码是提高数字信息传输可靠性的一项重要技术，当然它是以牺牲数字信息传输的有效性为代价的。 为了进行差错控制，不得不增加额外比特，这就是所谓的“冗余”技术。海明距离是判断码组检错/纠错能力的重要依据。,小 结,本章主要是讲述差错控制的基本原理，主要包括：差错控制的三种控制方式（即前向纠错（FEC）、自动请求重传（ARQ）以及混合纠错方式），和几种常用的差错控制编码的方法（检错码、线性分组码、卷积码）。 常用的差错校验方法有： （1）奇偶校验，（2）方阵校验，（3）循环冗余校验（CRC），（4）恒比码校验，（5）卷积码校验。,习 题 4,1. 纠错码能够检错或纠错的根本原因是什么? 2. 差错控制的基本工作方式有哪几种?各有什么特点? 3. 什么是分组码?其结构特点如何? 4. 分组码的检（纠）错能力与最小码距有什么关系?检、纠错能力之间有什么联系? 5. 二维监督码检测随机错误和突发错误的能力如何?是否能够纠错? 6. 海明码有哪些特点?,习 题 4,7. 系统分组码的监督矩阵、生成矩阵各有什么特点?相互之间有什么关系? 8. 循环码的生成多项式、监督多项式各有什么特点? 9. 已知码集合中有8个码组为（000000）、 （001110）、 （010101）、 （011011）、（100011）、（101101）、（110110）和（111000），求该码集合的最小码距。,校园,老校门,谢谢各位！,
展开阅读全文