network-2.ppt

CRC校验码设计中科大软件学院2012-8-work-2network-2CRC产生背景在数字通信系统中可靠与快速往往是矛盾的。如何合理地解决可靠与速度这一对矛盾呢?work-2network-2纠错码:在每一个发送的数据块中包含足够的冗余信息,以便接收方可以推断出被发送的数据中肯定有哪些内容。检错码:包含一些冗余信息,但是这些信息只能让接收方推断出发生了错误,但推断不出发生了哪个错误,然后接收方可以请求重传。参考:《计算机网络》、CRC校验码的区别在无线链路、光纤、铜线上应用的区别checksum:work-2network-2多项式编码特点:检错能力极强,开销小,易于用编码器及检测电路实现。从其检错能力来看,%以下。从性能上和开销上考虑,均远远优于奇偶校验及算术和校验等方式。因而,在数据存储和数据通讯领域,CRC无处不在:(帧检错序列)ITT,WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。work-2network-2多项式编码多项式编码(polynomialcode),也称为CRC(cyclicredundancycheck,循环冗余校验码),多项式编码的思想是:将位串看成是系数为0或1的多项式。CRC校验保护的单位是数据块。数据块的大小根据实际情况而定。每一个数据块均被看作是一个二进制多项式,即所有系数均为二进制(即1或0)的多项式。当使用多项式编码时,发送方和接受方必须预先商定一个生成多项式(generatorpolynomial)G(x)。生成多项式的最高位和最低位必须为1。work-2network-2CRC应用CRC的主要特点检错能力极强开销很小易于实现ARJ,LHA,ZIP等压缩软件采用的是CRC-32;GIF,TIFF等图像存储格式;所有链路层或网络接口层协议中,例如HDLC、DDCMP等众多领域。work-2network-2CRC原理将待发送的位串看成系数为0或1的多项式;收发双方约定一个生成多项式G(x)(其最高阶和最低阶系数必须为1),发送方用位串及G(x)进行某种运算得到校验和,并在帧的末尾加上校验和,使带校验和的帧的多项式能被G(x)整除;接收方收到后,用G(x)除多项式,若有余数,则传输有错。work-2network-(x)为r阶(即r+1位位串),原帧为m位,其多项式为M(x),则在原帧后面添加r个0,即循环左移r位,帧成为m+r位,相应多项式成为xrM(x);(x)对应的位串去除对应于xrM(x)的位串,得余数R(x);(即模2加)从对应于xrM(x)的位串中减去(加上)余数R(x),结果即传送的带校验和的帧多项式T(x)。 T(x)=xrM(x)+R(x)work-2network-2CRC验证发送方接收方设xrM(x)除以G(x)的商和余数分别为Q(x)和R(x)。则有:xrM(x)=G(x)Q(x)+R(x)即:接收方收到带CRC校验和的帧多项式T(x)=xrM(x)+R(x)。由于模2加减相当于异或运算,于是接收方模2除后商Q(x),!work-2network-2举一个例子(1)发送数据110011;(2)生成多项式G(x)=x4+x3+1;(3)将要发送的数据系列左移4位,新的序列为1100110000;(4)按模2算法,将生成的新序列除以生成多项式序列;(5)将余数多项式比特序列加到新的序列中即得发送端传送序列。下面。work-2network-2