[技术栈]CRC校验原理及C#代码实现CRC16、CRC32计算FCS校验码

时间:2021-11-28 00:58:03

标签:

1.CRC、FCS是什么

CRC,全称Cyclic Redundancy Check,中文名称为循环冗余校验,是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术,主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

FCS,全称Frame Check Sequence,中文名称为帧校验序列,俗称帧尾,即计算机网络数据链路层的协议数据单元(帧)的尾部字段,是一段4个字节的循环冗余校验码。

注:CRC循环冗余校验和FCS帧校验序列是单独的概念,CRC是一种错误校验方法,FCS是帧尾校验码,FCS可以采用CRC校验方法,也可以采用其他校验方法。

2.CRC算法原理

我们可以把任意的一串二进制数据表示为一个与之对应的多项式。比如:

二进制数据:1100101
多项式:$x^6 + x^5 + x^2+1$

多项式: $x^6 + x^4+x^3 + x^2+1$
二进制数据:1011101

有了这样的对应关系,对二进制数据的CRC校验就可以利用多项式运算规则进行校验计算。
CRC校验算法正是采用了模2除法,在数据处理里的具体表现为异或运算。

CRC的具体运算规则为:假设要传输的二进制数据为:10010110,对应的m阶多项式为:$M =x^7+x^4+x^2+x^1$,除数为h阶的多项式为:$H=x^4+x$,对应的二进制码为:10010,先将M乘以$x^h$,即将M对应的二进制数据后面加h个0,然后除以h阶的多项式H,得到的h-1阶的余数项R对应的二进制数据即为数据10010110的CRC校验码。

3.计算CRC校验 3.1.手工计算CRC校验码

MH的多项式除法运算,可以用模2除法运算计算。下面为以生成多项式为H求10010110的CRC校验码运算过程:

[技术栈]CRC校验原理及C#代码实现CRC16、CRC32计算FCS校验码

对应到异或运算:

通过示例即其他自定义的一些数据运算后,根据运算现象总结可以得到一些规律:

1.每次异或运算,当从左到右首位为1的时候,就与生成多项式H异或运算,然后再左移1位;当首位为0的时候只将数据左移1位。

2.每次异或运算后的数据,首位必定为0,因为首位为1的时候进行异或运算,而生成多项式的首位也必定为1。所以当需要进行异或运算时,可以舍弃H的首位,舍弃后为H‘,直接将数据左移一位后再与H‘异或。

[技术栈]CRC校验原理及C#代码实现CRC16、CRC32计算FCS校验码


3.每次运算,参与运算的是数据的前h位,可以用一个存储h位二进制数据的寄存器S,将数据的前h位存储到这个寄存器中。每次运算先将寄存器的首位移除,然后将二进制数据后一位移入,然后再参与运算,最后寄存器中的值即为CRC校验码。 3.2.C#代码计算CRC校验码 //代码验证如下: static void Main(string[] args) { int data = 0b10010110; int ploy = 0b0010; ploy <<= 4; Console.WriteLine($"第0次运算结果:"+Convert.ToString(data, 2)); for (int i = 0; i < 8; i++) { if ((data & 0b10000000) == 0b10000000) { data = (data << 1) ^ ploy; } else { data <<= 1; } Console.WriteLine($"第{i+1}次运算结果:"+Convert.ToString(data, 2)); } Console.WriteLine($" 最终运算结果:"+Convert.ToString(data, 2)); Console.ReadKey(); }

这里用int的第5位到第8位作为一个四位寄存器,可以看到与手算一致,最后算得校验位1100。

4.查表法

[技术栈]CRC校验原理及C#代码实现CRC16、CRC32计算FCS校验码

可以看到,参与运算的始终只有4位,所以在移位D1数据时,参与运算的数据只有D1D2,经过四次移位运算,D1被移除寄存器,这个时候受到影响的只有D2。而将D2的初值经过四次异或运算后的值就可以获得四次移位后的新数据$D2‘=D2\bigoplus H1 \bigoplus H2\bigoplus H3\bigoplus H4 = D2 \bigoplus \sum{h}$。

每一次D2是异或0还是异或生成多项式H‘,与D2本身的值无关,仅与D1中被移除的数据有关(首位为0还是1),所以这里引入了一个查表法,即先将所有可能的D1组合都计算出对应的$\sum{h}$,一次性移除四位,然后以$D2\bigoplus{\sum{h}}$即可以获得D2‘