文档介绍:CRC校验码设计
中科大软件学院
2014-8-29
第1页/共23页
CRC产生背景
在数字通信系统中可靠与快速往往是矛盾的。如何合理地解决可靠与速度这一对矛盾呢?
可靠性
快速性
可靠性
快速性
第2页/共23页
纠错码:在每一个发送的数据块中包含足够的冗余信息,以便接收方可以推断出被发送的数据中肯定有哪些内容。
检错码:包含一些冗余信息,但是这些信息只能让接收方推断出发生了错误,但推断不出发生了哪个错误,然后接收方可以请求重传。
CRC产生背景
第3页/共23页
多项式编码
多项式编码(polynomial code),也称为CRC(cyclic redundancy check,循环冗余校验码),多项式编码的思想是:将位串看成是系数为0或1的多项式。CRC校验保护的单位是数据块。数据块的大小根据实际情况而定。每一个数据块均被看作是一个二进制多项式,即所有系数均为二进制(即1或0)的多项式。
当使用多项式编码时,发送方和接受方必须预先商定一个生成多项式(generator polynomial)G(x)。生成多项式的最高位和最低位必须为1。
第4页/共23页
CRC应用
CRC的主要特点
检错能力极强
开销很小
易于实现
ARJ,LHA,ZIP等压缩软件采用的是CRC-32;
GIF,TIFF等图像存储格式;
所有链路层或网络接口层协议中,例如HDLC、DDCMP等众多领域。
应用范围广
第5页/共23页
CRC原理
将待发送的位串看成系数为 0 或 1 的多项式;
收发双方约定一个生成多项式 G(x)(其最高阶和最低阶系数必须为1),发送方用位串及 G(x)进行某种运算得到校验和,并在帧的末尾加上校验和,使带校验和的帧的多项式能被 G(x) 整除; 接收方收到后,用 G(x) 除多项式,若有余数,则传输有错。
第6页/共23页
CRC校验和计算法
G(x) 为 r 阶(即r+1位位串),原帧为 m 位, 其多项式为 M(x),则在原帧后面添加 r 个 0,即循环左移r位,帧成为 m+r 位,相应多项式成为 xrM(x);
G(x)对应的位串去除对应于 xr M(x) 的位串, 得余数 R(x);
(即模2加)从对应于 xr M(x) 的位串中减去(加上)余数 R(x),结果即传送的带校验和的帧多项式T(x)。
T(x) = xrM(x) + R(x)
第7页/共23页
CRC验证
发送方
接收方
设 xr M(x) 除以 G(x) 的商和余数分别为 Q(x) 和 R(x)。则有:
xrM(x) = G(x) Q(x) + R(x)
即:
接收方收到带CRC校验和的帧多项式T(x) = xr M(x) + R(x)。
由于模2加减相当于异或运算,于是接收方模2除后商Q(x),!
第8页/共23页
举一个例子
(1)发送数据110011;
(2)生成多项式G(x)= x4 + x3 + 1;
(3)将要发送的数据系列左移4位,新的序列为 1100110000;
(4)按模2算法,将生成的新序列除以生成多项式序列;
(5)将余数多项式比特序列加到新的序列中即得发送端传送序列。
下面
。
1 0 0 0 0 1
1 1 0 0 1
1 1 0 0 1 1 0 0 0 0
1 1 0 0 1
1 0 0 0 0
1 0 0 1
1 1 0 0 1
110011
1001
第9页/共23页
接收方校验方案
方案二:提取接收到序列的信息码元,重复发送方的操作xrM(x) ,再除以生成多项式G(x),如果余数R’(x) = R(x),则证明传输正确。
方案一:直接用接收到的序列除以生成多项式G(x),如果余数R’(x) = 0,则证明传输正确。
接收方
校验方案
第10页/共23页