CRC 循环冗余校验

2017年6月20日15:32:28 发表评论 137

 

什么是CRC校验

现实的通信链路都不会是理想的,比特在传输中可能会产生差错,1可能变成0,0可能变成1,这就叫做比特差错。比特差错是传输差错中的一种,还有帧丢失帧重复,帧失序。CRC校验只能够实现无比特差错的传输,但这还不是可靠传输。可靠传输现在一般交给传输层TCP协议来完成。但是对于通信质量较差无线传输链路,数据链路层协议使用确认和重传机制,数据链路层向上提供可靠传输服务

传输错误的比特占所传输比特总数的比率称为误码率。如果设法提高信噪比,就可以使误码率减小,但不可能使误码率下降到0。

为了保证数据传输的可靠性,必须才用各种差错检测措施,目前在数据链路层广泛使用循环冗余校验(Cyclic Redundancy Check)。

如何校验

在发送端,先把数据划分为组(帧),现假定每组 k 个比特,要传输的数据 M=101001(k=6)。CRC 运算就是在数据M的后面添加供差错检测的n位冗余码(冗余码常称为帧检验序列FCS),然后构成一个帧发出去,一共发送 k+n 位。

n位冗余码怎么得到?

  1. 进行 2ⁿ 乘M的运算,相当于在M后面添加 n 个0
  2. 得到(k+n)位的数除以收发方事先商定好的长度为(n+1)位的除数P,得到余数R(n位,比P少一位)。
  3. 假定除数P=1101(n=3),经模2除法运算后余数 R=001,这个余数R就作为冗余码拼接在数据M的后面封装成帧发出去。发送的帧为101001001(即2ⁿM+FCS)共 k+n 位。
  4. 在接收端把收到的每一个帧都除以相同的除数P,然后检查得到的余数R。
  5. 如果传输中无差错,余数R肯定是0,但如果出现误码,那么余数为0的概率非常小。所以若得到余数为0则判定这个帧没有差错,就接受;若余数不等于0,则判定这个帧有差错(但无法知道哪一位或哪几位出现差错)就丢弃。

除数是多少?

用多项式 P(X) = X³ + X² + 1 表示上面的除数 P = 1101,称为生成多项式,现在广泛使用的生成多项式有:

  • CRC-16 = Xˆ16 + Xˆ15 + Xˆ2 + 1
  • CRC-CCITT = Xˆ16 + Xˆ12 + Xˆ5 + 1
  • CRC-32 = Xˆ32 + Xˆ26 + Xˆ23 + Xˆ22 + Xˆ16 + Xˆ12 + Xˆ11 + Xˆ10 + Xˆ8 + Xˆ7 + Xˆ5 + Xˆ4 + Xˆ2 + X + 1

注:以上所有运算都是用二进制的模2运算,即运算时不进位,不借位,也就是进行加法和减法是异或运算

在数据链路层,发送端帧检验序列FCS的生成和接收端的CRC检验都是硬件完成的,处理速度很快,因此并不会延误数据传输。

在数据链路层仅仅使用循环冗余CRC差错检验,只能做到对帧的接近于1概率的无差错接收。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: