差错控制方法,主讲人：徐光达,1、差错原因,信道噪声 热噪声 由传输媒体的电子热运动引起 时刻存在，幅度小，属于随机噪声 冲击噪声 是由外界电磁干扰引起 幅度较大，是引起差错的主要原因 冲击噪声引起的传输差错称为突发差错,3,差错产生的原因,信道的分类,按照噪声或干扰的变化规律，可把信道分为三类： 随机信道：恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。 突发信道：具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即在短时间内出现大量错误。 混合信道,2、差错控制的基本工作方式,前向纠错方式FEC 发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。 特点是单向传输，实时性好，但译码设备较复杂。,检错重发方式ARQ 发端发送检错码，收端收到信码后能够检查出错误。 信息反馈方式IF 收端将接收的消息原封不动地送回发端，由发端将反馈信息和原发送信息进行比较，发现错误进行重发，其优点是方法和设备简单，无需纠（检）错编译系统。,混合纠错方式HEC 是FEC和ARQ方式的结合。,3、差错控制编码的基本原理,差错编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加冗余码的个数可增加纠检错能力。 （1）举例：发短信、天气预报 （2）基本思想：在发送信息时，加入某种关联性某种约束关系。 （3）基本原理：k位信息码+r位监督码n位编码。 （4）编码效率：k/n=1-r/n。 若2个信息码元中加1个监督码元，编码效率2/3。,涉及基本概念的理解,码长、码重,编码码组的码元总位数称为码组的长度，简称码长。 码组中，“1”码元的数目称为码组的重量，简称码重。,涉及基本概念的理解,码字、码组、码距 码字：由若干个码元组成的序列。例：1011001称为一个码字 。 码组：由多个码字构成的集合。例：00,01,10,11。 码距：两个码字对应位上数字不同的个数；（汉明距离） 例如：11000 与 10011之间的距离d=3 最小码距：码组集中各码距的最小值。 码重/汉明重量：码字中“1”的个数；例：码字 10110，码重w=3。,接收端不能检错，也不能纠错。,（3）、基本原理：,0 0（晴）0 1（云）1 0（阴）1 1（雨）,信息码加若干监督码的编码集合，用 表示。,：信息码元的数目， ： 码组 的总位数,表示监督码元的数目,其结构为：信息码+监督码,差错控制编码的基本原理,二、最小码距d0与纠错能力的关系： 1、重复码：用来发送天气预报 结论：纠错能力与码的位数有关。怎么样的关系呢？ 2、最小码距d0与纠错能力的关系： (1) 检测e个随机错误，则要求码的最小距离d0e+1; (2) 纠正t个随机错误， 则要求码的最小距离d02t+1; (3) 纠正t个同时检测e个随机错误，则要求码的最小距离d0t+e+1， (et)。 三、差错控制编码的分类： 从用途、监督关系、码字结构、信息处理等方面分类,差错控制编码的分类,按照差错控制编码的用途：检错码、纠错码和纠删码。 按照信息码元和监督码元之间的函数关系：线性码和非线性码。 按照对信息元处理方式的：分组码和卷积码。 按照码组中信息码元在编码前后是否相同：系统码和非系统码。 按照纠（检）错误的类型：纠（检）随机错误码、纠（检）突发错误码和既能纠（检）随机错误同时又能纠（检）突发错误码。 按照每个码元的取值：二进码和多进码。,接收端不能检错，也不能纠错。,3、若用3位码表示2种信息， 000（晴） 111（雨）,接收端此时有可能发现一个错码并能纠正它， 或发现二个以下错码不能纠正，不能发现三个错误。,返回,4、常用的简单编码,1、奇偶监督码 奇偶监督码可分为奇数监督码和偶数监督码，两者的原理相同。 （1）偶数监督码：监督位只有一位，使得码组中“1”的个数为偶数，即满足,为监督位,（2）奇数监督码：监督位也只有一位，使得码组中“1”的个数为奇数，即满足 它也能检测奇数个错码，无纠错能力。,编码效率：(n-1)/n,应用：适用于一般随机错误的检测,R=d/(d+r) 其中，d是信息元的个数，r为校验码个数,2、二维奇偶监督码,1）原理：,2）举例：,3）检错能力：,4）编码效率：,5）特点：适合检测突发误码。,2）举例：4行7列信息组的水平垂直偶校验码为：,发往线路顺序： 01110010|00101011|01010110|10101010|10100101 第1字符 第2字符 第3字符 第4字符 偶校验字符,3、恒比码 码组中“1”（或“0”）的个数相同。也即它们的比保持恒定。 接收端计算码组中“1”的个数即可知道有无误码。 优点：适合用来传输电传机或键盘设备产生的信息。 举例：5取3恒比码我国电传机，7取3恒比码国际电传电报,4、正反码（能纠正一位错码）,1）、编码规则：监督位数与信息位数相同。,“1”的个数决定监督码元是否与信息码元相同或相反。,举例：,电报通信 （10 5),若有奇数个“1”，则监督码元与信息码元相同,若有偶数个“1”，则监督码元与信息码元相反,2）、解码原理：,若收到码字的信息位有奇数个“1”，合成码字就是校验码字,若收到码字的信息位有偶数个“1”，合成码字的反码是校验码字,3）、由校验码字来检错纠错：,24,5、循环冗余编码原理,循环冗余编码（CRC） 发送端将发送数据与一个通信双方共同约定的数据进行除法运算，根据余数得出校验码，然后将校验码附加在信息数据帧之后发送出去。 接收端接收数据后，将包括校验码在内的数据帧再与约定的数据进行除法运算，若余数为“0”，就表示接收的数据正确，若余数不为“0”，则表明数据在传输的过程中出错。,25,假设待传送的数据 M = 1010001101（共k bit）。在 M 的后面再添加供差错检测用的 n bit 冗余码一起发送。 用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。 得到的 (k + n) bit 的数除以事先选定好的长度为 (n + 1) bit 的除数P，得出商是 Q 而余数是 R，余数 R 比除数 P 至少要少1个比特。,26,差错产生与差错控制方法 循环冗余编码原理,设 n = 5, P = 110101，模 2 运算的结果是： 商 Q = 1101010110 余数 R = 01110 将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2nM + R。 差错检测 接收端收到的带有CRC校验码的比特序列一定能被相同的生成多项式整除，只要得出的余数 R 不为 0，就表示检测到了差错。 这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。 一旦检测出差错，就丢弃这个出现差错的帧。,27,差错产生与差错控制方法 循环冗余编码原理,循环冗余检验原理,28,差错产生与差错控制方法 差错控制机制,反馈重发(自动请求重发ARQ)： 接收端检测到接收信息有错后，通过反馈信道要求发送端重发原信息，直到接收端认可为止，从而实现纠错。 反馈重发纠错实现方法有两种： 停止等待方式 连续工作方式。,29,差错产生与差错控制方法 差错控制机制,停止等待ARQ协议：发送端在发送完一个数据帧后，等待接收端应答帧信息，若应答为确认信息（ACK）时，发送端可以继续发送下一个数据帧；若应答为不确认帧（NAK）时，发送端需要重发这个数据帧。 停止等待ARQ协议简单，是一种半双工的协议，系统的通信效率低。,30,差错产生与差错控制方法 差错控制机制,连续ARQ协议 发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧； 如果在发送过程中收到接收方的肯定应答，可以继续发送； 若收到对其中某一帧的否认帧，则使用某种ARQ方式重发数据。 优点 连续发送提高了信道利用率； 连续ARQ协议包括 选择重发方式 拉回方式,31,差错产生与差错控制方法 差错控制机制,32,作业,某数据通信系统采用CRC校验方式，生成多项式G(x)的二进制比特序列为11001，目的结点接收到的二进制比特序列为110111001（含CRC校验码）。试判断传输过程是否出现了差错？为什么？,