差错控制方法课件.ppt

1、主讲人：徐光达主讲人：徐光达l信道噪声信道噪声F热噪声热噪声v由由传输媒体传输媒体的电子热运动引起的电子热运动引起v时刻存在，幅度小，属于时刻存在，幅度小，属于随机噪声随机噪声F冲击噪声冲击噪声v是由外界是由外界电磁电磁干扰引起干扰引起v幅度较大，是引起幅度较大，是引起差错差错的主要原因的主要原因v冲击噪声引起的传输差错称为冲击噪声引起的传输差错称为突发差错突发差错3 按照噪声或干扰的变化规律，可把信道分为三类：随机信道随机信道：恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。突发信道突发信道：具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即

2、在短时间内出现大量错误。混合信道混合信道l前向纠错方式前向纠错方式FECFECF发端发送能够发端发送能够纠正错误的码纠正错误的码，收端收，收端收到信码后自动地到信码后自动地纠正传输纠正传输中的错误。中的错误。F特点是特点是单向传输单向传输，实时性好，但，实时性好，但译码译码设备设备较复杂。较复杂。发发收收自己纠正自己纠正单向信道单向信道设备复杂设备复杂l检错检错重发方式重发方式ARQARQF发端发送发端发送检错码检错码，收端收到信码后能够，收端收到信码后能够检查检查出错误。出错误。l信息反馈信息反馈方式方式IFIFF收端将接收的消息收端将接收的消息原封不动地原封不动地送回发端，由发端将送回发端

3、，由发端将反反馈信息馈信息和和原发送信息原发送信息进行比较，发现错误进行比较，发现错误进行重发进行重发，其优点是其优点是方法和设备简单方法和设备简单，无需纠（检）错编译系统。，无需纠（检）错编译系统。发发收收有错码有错码无错码无错码双向信道双向信道发发收收是否有错是否有错双向信道双向信道效率低效率低l混合纠错混合纠错方式方式HECHECF是是FEC和和ARQ方式的结合。方式的结合。 信信 源源 编码器编码器 缓冲器缓冲器重发控制重发控制 双双 向向 信信 道道 解码器解码器 指令产生指令产生 输出缓冲输出缓冲 收收 信信 者者正确时输出正确时输出错误时删除错误时删除l差错编码差错编码的基本思想

4、是在被的基本思想是在被传输信息传输信息中增加一些中增加一些冗余码冗余码，利用，利用附加码元附加码元和和信息码元信息码元之间的约束关之间的约束关系加以系加以校验校验，以，以检测检测和和纠正纠正错误，增加冗余码的错误，增加冗余码的个数可增加个数可增加纠检错能力纠检错能力。l（1）举例：举例：发短信、发短信、天气预报天气预报l（2）基本思想：基本思想：在发送信息时，加入某种关联性某种在发送信息时，加入某种关联性某种约束关系。约束关系。l（3）基本原理基本原理：k位信息码位信息码+r位监督码位监督码n位编码。位编码。l（4）编码效率编码效率：k/n=1-r/n。l 若若2个信息码元中加个信息码元中加1

5、个监督码元，编码效率个监督码元，编码效率2/3。码长、码重码长、码重l编码码组的编码码组的码元总位数码元总位数称为码组的长度，称为码组的长度，简称简称码长码长。l码组中，码组中，“1”码元的数目称为码组的码元的数目称为码组的重量重量，简称码重。简称码重。码字、码组、码距码字、码组、码距l码字码字：由若干个码元组成的序列。例：由若干个码元组成的序列。例：1011001称称为一个码字为一个码字 。l码组码组：由多个码字构成的集合。例：由多个码字构成的集合。例：00,01,10,11。l码距码距：两个码字对应位上数字不同的个数；（汉：两个码字对应位上数字不同的个数；（汉明距离）明距离）l例如：例如：

6、11000 与与 10011之间的距离之间的距离d=3l最小码距：码组集中各码距的最小值。最小码距：码组集中各码距的最小值。l码重码重/汉明重量：码字中汉明重量：码字中“1”的个数；例：码字的个数；例：码字 10110，码重，码重w=3。举例：举例： 1、 2位码只能表示位码只能表示4种组合。种组合。00（晴）（晴）01（云）（云）10（阴）（阴）11（雨）（雨）2、 假如用假如用3位二进制数字来传送这位二进制数字来传送这4种信息种信息000（晴）（晴）011（云）（云）101（阴）（阴）110（雨）（雨）接收端不能检错，也不能纠错。接收端不能检错，也不能纠错。那么，若任一组码组有一个或多个发

7、生错码，那么，若任一组码组有一个或多个发生错码，变成另一信息码组。变成另一信息码组。接收端此时有可能发现一个或三个错码，接收端此时有可能发现一个或三个错码，但不能发现两个错码。但不能发现两个错码。（3）、基本原理：）、基本原理：0 0（晴）（晴）0 1（云）（云）1 0（阴）（阴）1 1（雨）（雨）0 0 0（晴）（晴）0 1 1（云）（云）1 0 1（阴）（阴）1 1 0（雨）（雨）信息位信息位监督位监督位信息码加若干监督码的编码集合，用信息码加若干监督码的编码集合，用 表示。表示。),(knkn ：信息码元的数目，：信息码元的数目， ： 码组码组 的总位数的总位数knr表示监督码元的数目表

8、示监督码元的数目其结构为：信息码其结构为：信息码+ +监督码监督码二、最小码距二、最小码距d0与纠错能力的关系：与纠错能力的关系：1、重复码重复码：用来发送天气预报用来发送天气预报 结论：纠错能力与码的位数有关。怎么样的关系呢？结论：纠错能力与码的位数有关。怎么样的关系呢？2、最小码距、最小码距d0与纠错能力的关系：与纠错能力的关系：(1) 检测检测e个随机错误，则要求码的最小距离个随机错误，则要求码的最小距离d0e+1;(2) 纠正纠正t个随机错误，个随机错误， 则要求码的最小距离则要求码的最小距离d02t+1;(3) 纠正纠正t个同时检测个同时检测e个随机错误，则要求码的最小距离个随机错误

9、，则要求码的最小距离d0t+e+1， (et)。三、差错控制编码的分类：三、差错控制编码的分类：从从用途用途、监督关系监督关系、码字结构码字结构、信息处理信息处理等方面分类等方面分类l按照差错控制编码的按照差错控制编码的用途用途：检错码检错码、纠错码纠错码和和纠删码纠删码。l按照信息码元和监督码元之间的按照信息码元和监督码元之间的函数关系函数关系：线性码线性码和和非非线性码线性码。l按照对信息元按照对信息元处理方式处理方式的：的：分组码分组码和和卷积码卷积码。l按照码组中信息码元在按照码组中信息码元在编码前后是否相同编码前后是否相同：系统码系统码和和非非系统码系统码。l按照纠（检）错误的类型：

10、按照纠（检）错误的类型：纠（检）随机错误码纠（检）随机错误码、纠纠（检）突发错误码（检）突发错误码和既能纠（检）随机错误同时又能纠和既能纠（检）随机错误同时又能纠（检）突发错误码。（检）突发错误码。l按照每个按照每个码元码元的取值：的取值：二进码二进码和和多进码多进码。举例：举例： 1、 2位码只能表示位码只能表示4种组合。种组合。00（晴）（晴）01（云）（云）10（阴）（阴）11（雨）（雨）2、 假如用假如用3位二进制数字来传送这位二进制数字来传送这4种信息种信息000（晴）（晴）011（云）（云）101（阴）（阴）110（雨）（雨）接收端不能检错，也不能纠错。接收端不能检错，也不能纠错。

11、那么，若任一组码组有一个或多个发生错码，那么，若任一组码组有一个或多个发生错码，变成另一信息码组。变成另一信息码组。接收端此时有可能发现一个或三个错码，接收端此时有可能发现一个或三个错码，但不能发现两个错码。但不能发现两个错码。 它只能检测错误，而不能纠正错误。它只能检测错误，而不能纠正错误。若要想能纠正错误，还要增加冗余度。若要想能纠正错误，还要增加冗余度。000、101、110011接收端接收端发送端发送端 错一个错一个错三个错三个100肯定出错了肯定出错了（禁用码组）（禁用码组）000错两个错两个011、110、101正确正确不能肯定出错不能肯定出错（许用码组）（许用码组）3、若用、若用

12、3位码表示位码表示2种信息，种信息， 000（晴）（晴） 111（雨）（雨）接收端此时有可能发现一个错码并能纠正它，接收端此时有可能发现一个错码并能纠正它，或发现二个以下错码不能纠正，不能发现三个错误。或发现二个以下错码不能纠正，不能发现三个错误。000接收端接收端发送端发送端错一个错一个100肯定出错了，且能纠错肯定出错了，且能纠错（禁用码组）（禁用码组）A、若错一位，则能确定发端的码、若错一位，则能确定发端的码。000错三个错三个111正确正确不能肯定出错不能肯定出错B、若错码不超过二位，、若错码不超过二位， 则则 不能确定发端的码不能确定发端的码。000111接收端接收端发送端发送端错一

13、个错一个错两个错两个100肯定出错了，不能纠错肯定出错了，不能纠错返回返回1、奇偶监督码、奇偶监督码 奇偶监督码奇偶监督码可分为可分为奇数监督码奇数监督码和和偶数监督码偶数监督码，两者的原，两者的原理相同。理相同。（1）偶数监督码：监督位只有一位，使得码组中）偶数监督码：监督位只有一位，使得码组中“1”的个的个数为偶数，即满足数为偶数，即满足0021aaann0a为监督位为监督位它能检测奇数个错码，无纠错能力。它能检测奇数个错码，无纠错能力。例例 收端：收端：1001 1011，则可能发生了奇数个错码，则可能发生了奇数个错码0001 1011、1101 10110111 1011发端可能为发端

14、可能为错一位错一位错三位错三位（2）奇数监督码：监督位也只有一位，使得码组中）奇数监督码：监督位也只有一位，使得码组中“1”的的个数为奇数，即满足个数为奇数，即满足它也能检测奇数个错码，无纠错能力。它也能检测奇数个错码，无纠错能力。1021aaann编码效率：编码效率：(n-1)/n应用：适用于一般随机错误的检测应用：适用于一般随机错误的检测R=d/(d+r) 其中，d是信息元的个数，r为校验码个数 2、二维奇偶监督码、二维奇偶监督码行监督行监督列监督列监督码组码组1）原理：）原理：2）举例：）举例：3）检错能力：）检错能力：4）编码效率：）编码效率：5）特点：适合检测突发误码。）特点：适合检

15、测突发误码。2）举例：）举例：4行行7列信列信息组的水平垂直偶校息组的水平垂直偶校验码为：验码为：发往线路顺序：发往线路顺序： 01110010|00101011|01010110|10101010|10100101 第第1字符字符 第第2字符字符 第第3字符字符 第第4字符字符 偶校验字符偶校验字符 3、恒比码、恒比码 码组中码组中“1”（或（或“0”）的个数相同。也即它们）的个数相同。也即它们的比的比保持恒定保持恒定。接收端计算码组中接收端计算码组中“1”的个数即可知道有无误码。的个数即可知道有无误码。优点：适合用来传输电传机或键盘设备产生的信息。优点：适合用来传输电传机或键盘设备产生的信

16、息。举例：举例：5取取3恒比码我国电传机，恒比码我国电传机，7取取3恒比码国恒比码国际电传电报际电传电报4、正反码（能纠正一位错码）、正反码（能纠正一位错码）1）、编码规则：监督位数与信息位数相同。）、编码规则：监督位数与信息位数相同。“1”的个数决定的个数决定监督码元监督码元是否与信息码元相同或相反。是否与信息码元相同或相反。举例：举例：电报通信电报通信 （10 5) 若有奇数个若有奇数个“1”，则监督码元与信息码元相同，则监督码元与信息码元相同若有偶数个若有偶数个“1”，则监督码元与信息码元相反，则监督码元与信息码元相反110011100110001011102）、解码原理：）、解码原理：

17、A、信息位与监督位按位模、信息位与监督位按位模2加加合成码字合成码字校验码字校验码字B、 合成码字合成码字校验码字的规则校验码字的规则若收到码字的信息位有奇数个若收到码字的信息位有奇数个“1”，合成码字就是校验码字，合成码字就是校验码字若收到码字的信息位有偶数个若收到码字的信息位有偶数个“1”，合成码字的反码是校验码字，合成码字的反码是校验码字3）、由校验码字来检错纠错：）、由校验码字来检错纠错：全全“0”无错码无错码4个个“1”，1个个“0”一位错码，其位置为校验码中一位错码，其位置为校验码中“0”的位置的位置一位错码，其位置为监督码中一位错码，其位置为监督码中“1”的位置的位置4个个“0”

18、，1个个“1”其他其他错码多于一位错码多于一位l循环冗余编码（循环冗余编码（CRC）F发送端将发送数据与一个发送端将发送数据与一个通信双方共同约定的数据通信双方共同约定的数据进行除法运算，进行除法运算，根据余数得出校验码，然后将根据余数得出校验码，然后将校校验码附加在信息数据帧之后发送验码附加在信息数据帧之后发送出去出去。F接收端接收数据后，将包括校验码在内的数据帧再接收端接收数据后，将包括校验码在内的数据帧再与与约定的数据约定的数据进行除法运算进行除法运算，若，若余数为余数为“0”，就表示接收的数据，就表示接收的数据正确正确，若，若余数余数不为不为“0”，则表明数据在传输的过程中，则表明数据

19、在传输的过程中出错。出错。24l假设待传送的数据假设待传送的数据 M = 1010001101（共（共k bit）。在）。在 M 的后面再添加供差错检测用的的后面再添加供差错检测用的 n bit 冗余码冗余码一起发送。一起发送。l用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘 M 的运算，这相当于在的运算，这相当于在 M 后面添加后面添加 n 个个 0。l得到的得到的 (k + n) bit 的数除以事先选定好的长度为的数除以事先选定好的长度为 (n + 1) bit 的除数的除数P，得出商是，得出商是 Q 而余数是而余数是 R，余数余数 R 比除数比除数 P 至少要少至少要少1个

20、比特个比特。25l设设 n = 5, P = 110101，模，模 2 运算的结果是：运算的结果是：商商 Q = 1101010110 余数余数 R = 01110l将余数将余数 R 作为冗余码作为冗余码添加在数据添加在数据 M 的后面的后面发送发送出去，即发送的数据是出去，即发送的数据是101000110101110，或，或 2nM + R。l差错检测差错检测F接收端收到的带有接收端收到的带有CRC校验码的比特序列一定能被相校验码的比特序列一定能被相同的生成多项式整除，只要得出的余数同的生成多项式整除，只要得出的余数 R 不为不为 0，就，就表示检测到了差错。表示检测到了差错。F这种检测方法

21、并不能确定究竟是哪一个或哪几个比特这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。出现了差错。F一旦检测出差错，就丢弃这个出现差错的帧。一旦检测出差错，就丢弃这个出现差错的帧。26l循环冗余检验原理循环冗余检验原理 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数27l反馈重发反馈重发(自动请求重发自动请求重发ARQ)：F接收端检测到接收信息有错后，通过反馈信

22、道要求发送接收端检测到接收信息有错后，通过反馈信道要求发送端重发原信息，直到接收端认可为止，从而实现纠错。端重发原信息，直到接收端认可为止，从而实现纠错。F反馈重发纠错实现方法有两种：反馈重发纠错实现方法有两种：v停止等待方式停止等待方式v连续工作方式。连续工作方式。28l停止等待停止等待ARQ协议：协议：发送端在发送完一个数据帧后，等待接收端应答发送端在发送完一个数据帧后，等待接收端应答帧信息，若应答为确认信息（帧信息，若应答为确认信息（ACK）时，发送端可以继续发送下一个）时，发送端可以继续发送下一个数据帧；若应答为不确认帧（数据帧；若应答为不确认帧（NAK）时，发送端需要重发这个数据帧。

23、）时，发送端需要重发这个数据帧。l停止等待停止等待ARQ协议简单，是一种半双工的协议，系统的通信效率低。协议简单，是一种半双工的协议，系统的通信效率低。时间ABDATA0送主机ACKDATA1送主机ACK(a) 正常情况ABDATA0NAKDATA0送主机ACK(b) 数据帧出错重传出错29l连续连续ARQ协议协议F发送方发完一帧后，不必停下来等待对方的应答，可以发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；连续发送若干帧；F如果在发送过程中收到接收方的肯定应答，可以继续发如果在发送过程中收到接收方的肯定应答，可以继续发送；送；F若收到对其中某一帧的否认帧，则使用某种若收到对其中某一帧的否认帧，则使用某种ARQ方式重方式重发数据发数据。l优点优点F连续发送提高了信道利用率；连续发送提高了信道利用率；l连续连续ARQ协议包括协议包括F选择重发方式选择重发方式F拉回方式拉回方式3031 某数据通信系统采用某数据通信系统采用CRC校验方式，生成多项校验方式，生成多项式式G(x)的二进制比特序列为的二进制比特序列为11001，目的结点接收，目的结点接收到的二进制比特序列为到的二进制比特序列为110111001（含（含CRC校验校验码）。试判断传输过程是否出现了差错？为什么？码）。试判断传输过程是否出现了差错？为什么？32