《计算机通信技术》课件 第5章 差错控制.ppt

1、计算机通信技术第第5章章 差错控制差错控制Error Control1本章内容纠错检错编码原理纠错检错编码原理 常用的校验编码方法常用的校验编码方法 差错控制方法差错控制方法 ARQ的各种类型的各种类型 信道的差错特性信道的差错特性 2纠错检错编码原理 差错类型差错类型 校验码的分类校验码的分类 编码的纠检错能力编码的纠检错能力 3差错类型 单比特比特错只改只改变一个比特一个比特 不影响不影响邻近的其它比特近的其它比特 也称也称为随机差随机差错或独立差或独立差错 突突发错 连续发生的一串生的一串错差差错之之间有相关性有相关性 突突发长度度B 出出错的串的串长度度 4校验码的分类 检错码和和纠错

2、码分分组码和卷和卷积码线性性码和非和非线性性码 系系统码和非系和非系统码 5检错码和纠错码 检错码只能只能检错，不能，不能纠错 纠错码能能够发现差差错知道是哪个比特知道是哪个比特传输出出错采取采取纠正措施正措施 6分组码和卷积码 分分组码附加的附加的监督位督位仅仅根据本根据本组内的信息代内的信息代码决定决定常用符号（常用符号（M，N）表示）表示N为每每组内信息的位数内信息的位数M是是编码后的后的总长度度K=M-N为每每组内内监督位的数目督位的数目卷卷积码监督位不督位不仅与本与本组的信息有关，而且的信息有关，而且还与前若干与前若干组的信息有关的信息有关纠错能力能力强 7线性码和非线性码 线性性码

3、数据位与数据位与监督位之督位之间的关系的关系为线性关系性关系即即满足一足一组线性方程式性方程式非非线性性码数据位与数据位与监督位之督位之间是非是非线性关系性关系 8系统码和非系统码 系系统码数据位在数据位在编码后保持原来的形式不后保持原来的形式不变非系非系统码数据数据码元改元改变了原来的位置了原来的位置监督督码元可能会散落分布在数据元可能会散落分布在数据码元中元中 9编码术语海明距离海明距离两个两个码字之字之间对应位不同的个数位不同的个数码距距某种某种编码的的码距是全部距是全部码字中两两之字中两两之间海明距离海明距离的最小的最小值。合法合法码字字如果一个如果一个码字符合字符合编码规则，则称称该

4、码字是一个字是一个合法合法码字。字。非法非法码字字10编码的纠检错能力码距距d与与编码的的检错和和纠错能力的关系是：能力的关系是：1.若若d e+1，只要出，只要出错位数不超位数不超过e，则可可检测出出e个个错误；2.若若d 2t+1，只要出，只要出错位数不超位数不超过t，则可可纠正正t个个错误；3.若若d e+t+1（e t），只要），只要出出错位数不超位数不超过e，则可可纠正正t个个错误，同，同时检测出出e个个错误。11码距与编码纠检错能力的关系1.若若d e+1，只要出，只要出错位数不超位数不超过e，则可可检测出出e个个错误；12码距与编码纠检错能力的关系2.若若d 2t+1，只要出，只

5、要出错位数不超位数不超过t，则可可纠正正t个个错误；13码距与编码纠检错能力的关系3.若若d e+t+1（e t），只要出），只要出错位位数不超数不超过e，则可可纠正正t个个错误，同，同时检测出出e个个错误。14常用的校验编码方法 奇偶检验码奇偶检验码方阵校验码方阵校验码 恒比码恒比码校验和校验和 循环冗余校验码循环冗余校验码15奇偶校验码在字符上附加奇偶校在字符上附加奇偶校验位位奇偶校奇偶校验码是是奇校奇校验码和和偶校偶校验码的的统称称偶校偶校验：整个字符中有：整个字符中有偶数个偶数个1 0 1奇校奇校验：整个字符中有：整个字符中有奇数个奇数个1 0 1只能只能检测奇数位出奇数位出错，如果有

6、偶数位出，如果有偶数位出错，检测不到不到16奇偶校验码奇校奇校验：奇数个：奇数个1则为0，否，否则为1偶校偶校验：偶数个：偶数个1则为0，否，否则为117原原编码 奇校奇校验 偶校偶校验00000000 10000 000100010 00010 111001100 11100 010101010 11010 0奇偶校验码只能只能检测奇数位出奇数位出错出出错则要求重要求重传18原原编码 奇校奇校验 错误码信息位出错00000000 10100 1校验位出错00100010 00010 1偶数位出错00100010 00100 0例题已知字符已知字符M的的ASCII码值的十的十进制表示制表示为7

7、7，如果将最高位，如果将最高位设置置为奇校奇校验位，位，则字符字符M的的ASCII码值设置奇校置奇校验位后，它的二位后，它的二进制制表示表示为（）A.01001101 B.11001101 C.01101011 D.10111101答案：答案：B19方阵检验码垂直冗余校垂直冗余校验VRC：就是字符奇偶校：就是字符奇偶校验；水平冗余校水平冗余校验LRC：就是：就是对数据数据块中每个字中每个字符的符的对应位位进行奇偶校行奇偶校验。20恒比码 恒比恒比码就是使校就是使校验码中的中的1和和0的数目之比是的数目之比是一个常数。一个常数。编码生成生成时是是查表表接收接收检验时是是检查每个每个编码中中1出出

8、现的次数是否的次数是否正确正确21中国五单位保护电码表22数字数字电码电码数字数字电码电码001101500111101011610101211001711100310110801110411010910011校验和 把数据把数据块中的每一个字符代中的每一个字符代码都按二都按二进制加制加法求和法求和 例：例：传送送CA：1000011 100000123IP数据报校验方式发送方送方校校验和字段全和字段全设0；将将IP报头按按16位分位分组，不足，不足16位用位用0补足；足；将各将各组数据反数据反码求和；求和；将得到的和的反将得到的和的反码填入校填入校验和字段；和字段；接收方接收方将将IP报头按

9、按16位分位分组，不足，不足16位用位用0补足；足；将各将各组数据反数据反码求和，求和，检查得到的和是否是全得到的和是否是全1如果是全如果是全1则进行下步行下步处理，否理，否则意味着包已意味着包已变化从化从而而丢弃之。弃之。24循环冗余校验码CRC用事先用事先约定的一个定的一个生成多生成多项式式去除数据串，去除数据串，将余数作将余数作为帧校校验序列（序列（FCS）生成多生成多项式：可以用一个二式：可以用一个二进制串表示制串表示K位的二位的二进制串，和制串，和xk-1x0的的k-1阶多多项式式对应例如：例如：代代码1010111对应的多的多项式式为x6+x4+x2+x+1多多项式式为x5+x3+

10、x2+x+1对应的代的代码101111 25CRC码的实现方法 D：k位数据位数据F：n-k位的位的FCSP：n-k+1位的生成多位的生成多项式式T：n位的位的帧，即，即D+F将将k位的数据左移位的数据左移n-k位，低位位，低位补0，再用，再用n-k+1位的生成多位的生成多项式式进行模行模2除，所得的除，所得的n-k位余数就是位余数就是FCS。26CRC码的计算 D(x)=x5+x4+x+1，G(x)=x4+x3+1，求，求CRC码。数据：数据：110011生成多生成多项式：式：11001 CRC码：110011100127CRC码算法的证明 28生成多项式的选择生成多生成多项式的最高位和最低

11、位必式的最高位和最低位必须为1。当当CRC码的任何一位的任何一位发生生错误时，被生成多，被生成多项式做模式做模2除后除后应该使余数不使余数不为0。不同位不同位发生生错误时，应该使余数不同。使余数不同。对余数余数继续做模做模2除，除，应使余数循使余数循环。检测单错，要含一个以上的非零，要含一个以上的非零项检测双双错，要含一个三，要含一个三项因式因式检测奇数奇数错，要含因式，要含因式(x+1)29生成多项式标准CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12

12、+x11+x10+x8+x7+x5+x4+x2+x+1 30CRC电路用硬件用硬件电路生成路生成CRC码生成多生成多项式式为CRC-CCITT 31CRC计算程序/CRC calculation，x is the byte to be added to CRC./CCITT polynomial used for CRC calculation：x16+x12+x5+1void updcrc（x）unsigned char x;extern unsigned int crcaccum;/CRC result，2 byte unsigned shifter，flag;for（shifter=0

13、x80;shifter;shifter=1）flag=（crcaccum&0 x8000）;/First bit=1?crcaccum=1;/left shift 1 bit crcaccum|=（shifter&x）?1：0）;/add x to crcaccum tail if（flag）crcaccum=0 x1021;/XOR polynomial 32海明码 纠错码 多重奇偶校多重奇偶校验 非系非系统码 33海明不等式 对于只能于只能纠正一位正一位错的校的校验码校校验位的位数位的位数K和数据位的位数和数据位的位数N之之间的关系的关系由下面的海明不等式由下面的海明不等式给出：出：34海

14、明码编码规则 校校验位位放在第放在第2i-1位置位置即，校即，校验位一般放在第位一般放在第1、2、4、8位位数据位数据位依次从低到高占据海明依次从低到高占据海明码中剩下的位置中剩下的位置被校被校验的数据位的下的数据位的下标等于所有参与校等于所有参与校验该位的校位的校验位的下位的下标之和。之和。35海明码编码规则 H7H6H5H4H3H2H1数据和校验位D4D3D2P3D1P2P1参与校验位号7=4+2+16=2+45=4+143=1+221参与校验位P3、P2、P1P3、P2P3、P1P3P2、P1P2P136P1=D4 D2 D1P2=D4 D3 D1P3=D4 D3 D2例如：数据例如：数

15、据1001P1=0 P2=0 P3=1海明码：海明码：1001100接收译码S1=P1 D4 D2 D1S2=P2 D4 D3 D1S3=P3 D4 D3 D2若若S3S2S1为000，则表示接收无表示接收无错37差错控制方法 反馈重发纠错（反馈重发纠错（ARQ）前向纠错（前向纠错（FEC）混合纠错（混合纠错（HEC）38ARQ Automatic-Repeat Request 必必须有反有反馈信道信道用于点用于点对点的通信点的通信 39ARQ类型停止等待停止等待ARQ重返重返N-ARQ选择重重发ARQ 40FEC前向前向纠错方式方式Forward Error Correction纠错码适用于

16、适用于单工通信工通信不需要反向信道不需要反向信道 41HEC混合混合纠错Hybrid Error Correction反反馈重重传纠错和前向和前向纠错方式的方式的综合合 校校验码的的码距必距必须大于或等于大于或等于4 42其它差错控制方式 回送法回送法冗余法冗余法多数表决法多数表决法 43ARQ的各种类型停止等待停止等待ARQ重返重返N-ARQ选择重发选择重发ARQ 44停止等待ARQ 等待接收端的等待接收端的应答响答响应信号信号正确接收（正确接收（ACK）未正确接收（未正确接收（NAK）45传输效率 接收端所接收的数据比特数与接收端所接收的数据比特数与发送端在相同送端在相同时间内所内所发送的

17、送的总比特数之比比特数之比 46编码效率c 考考虑了控制比特数和了控制比特数和监督督码元之后的效率元之后的效率如如码组的起止的起止标志志n为码组长度度r为控制比特数加控制比特数加监督督码元数元数 47等待效率w 考考虑了等待了等待应答答时间后的效率后的效率n为码组的的长度度R为数据数据传输速率速率T为环路路迟延延时间 48数据信息有效率s 考考虑了了传输差差错后的效率后的效率 误组率率PB 49总传输效率 编码效率效率c等待效率等待效率w数据信息有效率数据信息有效率s 50重返N-ARQ GO BACK N-ARQ发生生错误时退回退回N个个码组，重新，重新发送送这N个个码组 51重返N-ARQ

18、的效率 传输效率效率N的取的取值 52选择重发ARQ SRQ，也称，也称为选择拒拒绝ARQ只重只重发有有错码组其余正确的其余正确的码组先存先存储起来起来 53选择重发ARQ的传输效率传输效率与信道效率与信道环路路迟延没有直接关系延没有直接关系重重发效率效率为（1-PB）54各种ARQ传输效率的比较 等待等待时间的影响的影响 减少开减少开销减少重减少重传次数次数选用最佳用最佳码长 55信道的差错特性 信道的差错统计特性信道的差错统计特性反馈信道对应答信号的影响反馈信道对应答信号的影响 56信道的差错统计特性 信道的差信道的差错分布特性分布特性随机差随机差错无无记忆信道或随机信道信道或随机信道 突突发差差错二元二元对称信道称信道 信道只有两个状信道只有两个状态即即“1”和和“0”“1”和和“0”正确正确传输的概率相同的概率相同 修正二元修正二元对称信道称信道考考虑突突发差差错57反馈信道对应答信号的影响 ACK错成其它字符成其它字符NAK错成其它字符成其它字符ACK错成成NAKNAK错成成ACK 58复习题差错控制方法有哪些？差错控制方法有哪些？ARQ的工作过程是什么？的工作过程是什么？ARQ有哪几种类型？有哪几种类型？59本章总结差错控制方法差错控制方法 纠错检错编码原理纠错检错编码原理 校验码校验码 ARQ601101 0011 写出他的海明写出他的海明码