首页 > 代码库 > 循环冗余检验CRC的原理

循环冗余检验CRC的原理

数据链路层的简介:数据链路层主要使用两种信道类型,一种是点对点信道,另一种是广播信道。其中点对点信道使用的协议是PPP协议,而广播信道使用的协议是CSMA/CD(半双工链路层协议)。

数据链路层需要解决的三个问题:

            1,封装成帧

            2,透明传输

            3,差错检测

目前在数据链路层广泛使用了循环冗余检验CRC的检错技术。

CRC实现算法分析:

                在发送端,先把数据分为组,假定每组K个比特。现假定待传输的数据 M = 101001(K=6)。CRC运算就是在数据M 的后面添加供差错检测用的 n 位冗余码,然后构成一个帧发送出去,一共发送(k+n)位。在所要发送数据后面增加n 位冗余码,虽然增大了数据传输的开销,但却可以进行差错检测。

                 n 位冗余码的计算方法:用二进制的模 2 运算进行2^n乘 M 的运算,这相当于在M 的后面添加 n 个0。得到的(k+n)位的数除以收发双方事先约定好的长度为(n+1)位的除数P ,得出商是Q 而余数是R(R的位数 n 可以根据P来确定,总是比P少一位,Q是计算出来的商并没什么用处,忽略)。


for example:

题目:要发送的数据为101110.采用CRC的生成多项式是P(X)= X^3+1。试求应添加在数据后面的余数(冗余码)。

           P = 1001     M = 101110   被除数 2^n M = 101110000 (在原来M的基础上后面加3 (n = P的位数-1)个0)

技术分享

在接受端把接收到的数据以帧为单位进行CRC检验:把收到的每一个帧都除以同样的除数P(模2运算),然后检查得到的余数R。如果在传输的过程中无差错,那么经过CRC检验后 得出的余数R 肯定是 0。

            被除数:101110011         P = 1001

技术分享

PS:接收端对收到的每一帧经过CRC检验后,有以下两种情况:

             1,若得出的余数R = 0 ,则判定这个帧没有差错,就接受。

             2,若得出的余数R != 0 ,则判定这个帧出错,就丢弃。

在数据链路层,发送端帧检验序列FCS的生成和接收端的CRC检验都是由硬件来完成的,处理速度快,不会延误数据的传输。还有如果要在数据链路层进行差错检测,就必须把数据划分为帧,每一帧都加上冗余码,一帧一帧地发送,然后在接受方逐帧进行差错检验。





本文出自 “珞辰的博客” 博客,谢绝转载!

循环冗余检验CRC的原理