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

《计算机通信技术》第5章差错控制ErrorControl1本章内容纠错检错编码原理

常用的校验编码方法

差错控制方法

ARQ的各种类型

信道的差错特性

2纠错检错编码原理

差错类型

校验码的分类

编码的纠检错能力

3差错类型单比特错只改变一个比特不影响邻近的其它比特也称为随机差错或独立差错突发错连续发生的一串错差错之间有相关性突发长度B出错的串长度4校验码的分类

检错码和纠错码分组码和卷积码线性码和非线性码系统码和非系统码5检错码和纠错码

检错码只能检错，不能纠错纠错码能够发现差错知道是哪个比特传输出错采取纠正措施6分组码和卷积码

分组码附加的监督位仅仅根据本组内的信息代码决定常用符号（M，N）表示N为每组内信息的位数M是编码后的总长度K=M-N为每组内监督位的数目卷积码监督位不仅与本组的信息有关，而且还与前若干组的信息有关纠错能力强7线性码和非线性码

线性码数据位与监督位之间的关系为线性关系即满足一组线性方程式非线性码数据位与监督位之间是非线性关系8系统码和非系统码

系统码数据位在编码后保持原来的形式不变非系统码数据码元改变了原来的位置监督码元可能会散落分布在数据码元中9编码术语海明距离两个码字之间对应位不同的个数码距某种编码的码距是全部码字中两两之间海明距离的最小值。合法码字如果一个码字符合编码规则，则称该码字是一个合法码字。非法码字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，只要出错位数不超过t，则可纠正t个错误；13码距与编码纠检错能力的关系3.若d≥e+t+1（e>t），只要出错位数不超过e，则可纠正t个错误，同时检测出e个错误。14常用的校验编码方法

奇偶检验码方阵校验码恒比码校验和

循环冗余校验码15奇偶校验码在字符上附加奇偶校验位奇偶校验码是奇校验码和偶校验码的统称偶校验：整个字符中有偶数个101奇校验：整个字符中有奇数个101只能检测奇数位出错，如果有偶数位出错，检测不到16奇偶校验码奇校验：奇数个1则为0，否则为1偶校验：偶数个1则为0，否则为117原编码奇校验偶校验00000000100000001000100001011100110011100010101010110100奇偶校验码只能检测奇数位出错出错则要求重传18原编码奇校验错误码信息位出错00000000101001校验位出错00100010000101偶数位出错00100010001000例题已知字符M的ASCII码值的十进制表示为77，如果将最高位设置为奇校验位，则字符M的ASCII码值设置奇校验位后，它的二进制表示为（）A.01001101B.11001101C.01101011D.10111101答案：B19方阵检验码垂直冗余校验VRC：就是字符奇偶校验；水平冗余校验LRC：就是对数据块中每个字符的对应位进行奇偶校验。20恒比码恒比码就是使校验码中的1和0的数目之比是一个常数。编码生成时是查表接收检验时是检查每个编码中1出现的次数是否正确21中国五单位保护电码表22数字电码数字电码001101500111101011610101211001711100310110801110411010910011校验和

把数据块中的每一个字符代码都按二进制加法求和例：传送CA：1000011100000123IP数据报校验方式发送方校验和字段全设0；将IP报头按16位分组，不足16位用0补足；将各组数据反码求和；将得到的和的反码填入校验和字段；接收方将IP报头按16位分组，不足16位用0补足；将各组数据反码求和，检查得到的和是否是全1如果是全1则进行下步处理，否则意味着包已变化从而丢弃之。

24循环冗余校验码CRC用事先约定的一个生成多项式去除数据串，将余数作为帧校验序列（FCS）生成多项式：可以用一个二进制串表示K位的二进制串，和xk-1~x0的k-1阶多项式对应例如：代码1010111对应的多项式为x6+x4+x2+x+1多项式为x5+x3+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生成多项式：11001CRC码：110011100127CRC码算法的证明28生成多项式的选择生成多项式的最高位和最低位必须为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+x11+x10+x8+x7+x5+x4+x2+x+130CRC电路用硬件电路生成CRC码生成多项式为CRC-CCITT31CRC计算程序//CRCcalculation，'x'isthebytetobeaddedtoCRC.//CCITTpolynomialusedforCRCcalculation：x16+x12+x5+1voidupdcrc（x）unsignedcharx;{externunsignedint

crcaccum;//CRCresult，2byteunsignedshifter，flag;for（shifter=0x80;shifter;shifter>>=1）

{flag=（crcaccum&0x8000）;//Firstbit=1?

crcaccum<<=1;//leftshift1bit

crcaccum|=（（shifter&x）?1：0）;//addxtocrcaccumtailif（flag）crcaccum^=0x1021;//XORpolynomial}}32海明码

纠错码多重奇偶校验非系统码33海明不等式对于只能纠正一位错的校验码校验位的位数K和数据位的位数N之间的关系由下面的海明不等式给出：34海明码编码规则校验位放在第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例如：数据1001P1=0P2=0P3=1海明码：1001100接收译码S1=P1⊕D4⊕D2⊕D1S2=P2⊕D4⊕D3⊕D1S3=P3⊕D4⊕D3⊕D2若S3S2S1为000，则表示接收无错37差错控制方法

反馈重发纠错（ARQ）前向纠错（FEC）混合纠错（HEC）

38ARQ

Automatic-RepeatRequest必须有反馈信道用于点对点的通信39ARQ类型停止等待ARQ重返N-ARQ选择重发ARQ40FEC前向纠错方式ForwardErrorCorrection纠错码适用于单工通信不需要反向信道41HEC混合纠错HybridErrorCorrection反馈重传纠错和前向纠错方式的综合校验码的码距必须大于或等于442其它差错控制方式

回送法冗余法多数表决法43ARQ的各种类型停止等待ARQ重返N-ARQ选择重发ARQ44停止等待ARQ

等待接收端的应答响应信号正确接收（ACK）未正确接收（NAK）45传输效率

接收端所接收的数据比特数与发送端在相同时间内所发送的总比特数之比46编码效率ηc

考虑了控制比特数和监督码元之后的效率如码组的起止标志n为码组长度r为控制比特数加监督码元数47等待效率ηw

考虑了等待应答时间后的效率n为码组的长度R为数据传输速率T为环路迟延时间48数据信息有效率ηs

考虑了传输差错后的效率误组率PB

49总传输效率

编码效率ηc等待效率ηw数据信息有效率ηs

50重返N-ARQ

GOBACKN-ARQ发生错误时退回N个码组，重新发送这N个码组51重返N-ARQ的效率传输效率N的取值52选择重发ARQ

SRQ，也称为选择拒绝ARQ只重发有错码组其余正确的码组先存储起来53选择重发ARQ的传输效率传输效率与信道环路迟延没有直接关系重发效率为（1-PB）54各种ARQ传输效率的比较

等待时间的影响减少开销减少重传次数选用最佳码长55信道的差错特性

信道的差错统计特性反馈信道对应答信号的影响

56信道的差错统计特性