crc算法
文语通-幼儿园家长委员会会议记录
2023年2月22日发(作者：无铬)cr-32校验算法c语⾔,CRC校验的快速算法的C语⾔实现
摘要：CRC循环冗余校验算法，是⼀种在数据存储和数据通讯领域中使⽤⼗分⼴泛的编码算法，具有强⼒的检错和纠错能⼒，并且开销⽐较
⼩。本⽂从CRC基本原理出发，介绍了CRC快速算法的原理，以C语⾔为实现⼿段，实现了该算法。
1.引⾔在数据存储和数据通讯领域，为了保证数据的正确，就不得不采⽤检错或者纠错的编码⼿段。在诸编码⽅式中，CRC是其中著名的
⼀种，其特点是，检错能⼒极强，开销⼩，易于⽤编码器及检测电路实现；从其检错能⼒来看，它所不能发现的错误的⼏率仅为0.0047%
以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等⽅式。因⽽，在数据存储和数据通讯领域，CRC都被⼴泛运⽤，例如，
通讯协议X.25的FCS(帧检错序列)采⽤的是CRC-CCITT，ARJ、LHA等压缩⼯具软件采⽤的是CRC32，磁盘驱动器的读写采⽤了
CRC16，通⽤的图像存储格式GIF、TIFF等也都使⽤CRC作为检错⼿段。
原理
CRC校验是⼀种线性编码理论，对于要传输n位⼆进制码序列，在发送端，根据已定的⽣成多项式，按照⼀定的规则，产⽣⼀段k位的校验
码(即CRC码)，附在要发送的信息后，构成⼀个新的长为(n+k)位的⼆进制码序列，再发送给接收端。在接收端，则根据接收的数据部分和
CRC之间是否预定的关系，从⽽判定在传输过程中是否出现传输错误。
CRC的计算是⼀种模2的除法，与普通的除法主要的差别是在计算过程中减法，使⽤的不借位/进位的模2加运算，等同于按位异或。
⼆进制序列数据流，可以⽤模2多项式表⽰，多项式的系数就是序列的值。如101011可以表⽰为:。
假设要传输的n位长度的⼆进制序列，表⽰为：，
使⽤的CRC⽣成多项式，记为：
如果将⼆进制序列和⽣成多项式，进⾏下⾯的计算：
(2-1)
得到的就是CRC校验码，它的长度应该是⽐⽣成多项式少⼀位，要发送的数据就是：。
在接收端，对数据进⾏校验就是将接收到数据和已定的CRC⽣成多项式进⾏模2除，即：(2-2)
根据式2-1，可以得到：
(2-3)
根据，根据相同的序列按位异或的结果为0，因此，式2-3的就可以化为：
(2-4)
从中就可以看出，接收端计算的结果是整除的，没有余数，这也就是CRC在接收端判断数据是否正确的标准。
因此整个CRC计算过程就是将要发送的信息左移k位，然后将与⽣成多项式进⾏模2除法，等到的k位长的余数就是CRC校验信息。
CRC的标准时多种多样的，⼀般是依据⽣成多项式的长度分为CRC-8，CRC16等，以下就是⼏种典型的⽣成多项式：
-16快速算法原理在⼯程运⽤中，基于上⾯介绍的按照模2除法，计算CRC校验算法的⼯作量是很⼤的，特别是对于越长的序列，因
为没1为数据就要进⾏⼀个计算。例如⼀个以太⽹数据包的包长最⼤为1518byte，计算这样的⼀个数据包需要的时间和计算量的花费很
多，找到⼀种快速的CRC计算⽅法(也成并⾏CRC算法)，对于⼯程应⽤是⼗分有必要的。
可以采⽤增加每次CRC的输⼊的数据长度来简化运算需要的时间和运算量，⼀般使⽤1byte输⼊数据代替1bit的输⼊。
以CRC-8为例，如果要计算⼀个16bit的数据的CRC-8。
16bit数据,记为：，其中就是第1byte的数据，是第2byte的数据。
那么按照前⾯介绍的CRC原理，计算过程：
(3-1)
假定,
(3-2)
那么,
(3-3)
由式3-3可以看到，最后的CRC编码结果，是由数据的第1byte数据单独的CRC编码的结果，与第2byte的按位异或得到的结果，再⼀次进
⾏CRC编码的结果。
以此类推，任何长度的数据，从第1byte数据起，前1byte的数据的CRC-8校验的结果与后1byte的数据按位异或后得到的数据，再⼀次进
⾏CRC-8校验，直⾄整个数据结束。
在此过程中，每次CRC-8校验的结果都是以被除数是⼀⼀对应的，如果将这些结果预先存储下来，然后通过查表的⽅式进⾏计算，就⼤⼤
减少了计算的时间和⼯作量。对于CRC-8来说，将上次计算的结果，作为查表的依据，将查表得结果与输⼊的1byte数据进⾏按位异或的结
果，就是本次计算的结果，以此进⾏数据结束。
对于CRC-16,CRC-32等也可以按照上⾯类似的⽅法，进⾏改进来完成。
对于CRC-16来说，每次计算的过程是，拿上次的结果的⾼字节为查表的依据，查余项表得到的结果的⾼字节与上次结果的低字节的按位异
或的结果就是本次计算结果的⾼字节，查余项表得到的结果的低字节与输⼊字节的按位异或的结果就是本次计算结果的低字节。在整个过程
中，需要计算的数据，除信息数据外，还有两byte的全0数据。
在实际计算的过程中，为了省去最后16位填充0的计算，那么可以将输⼊的数据左移16位后再进⾏查表就能达到这个⽬的。那么查表过程
就变为，将上次的结果和⾼字节与输⼊的结果进⾏按位异或作为查表的依据，查表结果的⾼字节与上次结果的低字节进⾏按位异或得到本次
计算结果的⾼字节，查表结果的低字节就是本次计算结果的低字节。
余项表CRC余项表是快速算法的核⼼，CRC余项表的每个表项的数据，是该数据的标号，进⾏对应的CRC校验，所得到的结果。
下⾯就是⼀个CRC-16的余项表：
unsignedshortCRC_table[256]=
{
0x0000,0x1189,0x2312,0x329b,0x4624,0x57ad,0x6536,0x74bf,
0x8c48,0x9dc1,0xaf5a,0xbed3,0xca6c,0xdbe5,0xe97e,0xf8f7,
0x1081,0x0108,0x3393,0x221a,0x56a5,0x472c,0x75b7,0x643e,
0x9cc9,0x8d40,0xbfdb,0xae52,0xdaed,0xcb64,0xf9ff,0xe876,
0x2102,0x308b,0x0210,0x1399,0x6726,0x76af,0x4434,0x55bd,
0xad4a,0xbcc3,0x8e58,0x9fd1,0xeb6e,0xfae7,0xc87c,0xd9f5,
0x3183,0x200a,0x1291,0x0318,0x77a7,0x662e,0x54b5,0x453c,
0xbdcb,0xac42,0x9ed9,0x8f50,0xfbef,0xea66,0xd8fd,0xc974,
0x4204,0x538d,0x6116,0x709f,0x0420,0x15a9,0x2732,0x36bb,
0xce4c,0xdfc5,0xed5e,0xfcd7,0x8868,0x99e1,0xab7a,0xbaf3,
0x5285,0x430c,0x7197,0x601e,0x14a1,0x0528,0x37b3,0x263a,
0xdecd,0xcf44,0xfddf,0xec56,0x98e9,0x8960,0xbbfb,0xaa72,
0x6306,0x728f,0x4014,0x519d,0x2522,0x34ab,0x0630,0x17b9,
0xef4e,0xfec7,0xcc5c,0xddd5,0xa96a,0xb8e3,0x8a78,0x9bf1,
0x7387,0x620e,0x5095,0x411c,0x35a3,0x242a,0x16b1,0x0738,
0xffcf,0xee46,0xdcdd,0xcd54,0xb9eb,0xa862,0x9af9,0x8b70,
0x8408,0x9581,0xa71a,0xb693,0xc22c,0xd3a5,0xe13e,0xf0b7,
0x0840,0x19c9,0x2b52,0x3adb,0x4e64,0x5fed,0x6d76,0x7cff,
0x9489,0x8500,0xb79b,0xa612,0xd2ad,0xc324,0xf1bf,0xe036,
0x18c1,0x0948,0x3bd3,0x2a5a,0x5ee5,0x4f6c,0x7df7,0x6c7e,
0xa50a,0xb483,0x8618,0x9791,0xe32e,0xf2a7,0xc03c,0xd1b5,
0x2942,0x38cb,0x0a50,0x1bd9,0x6f66,0x7eef,0x4c74,0x5dfd,
0xb58b,0xa402,0x9699,0x8710,0xf3af,0xe226,0xd0bd,0xc134,
0x39c3,0x284a,0x1ad1,0x0b58,0x7fe7,0x6e6e,0x5cf5,0x4d7c,
0xc60c,0xd785,0xe51e,0xf497,0x8028,0x91a1,0xa33a,0xb2b3,
0x4a44,0x5bcd,0x6956,0x78df,0x0c60,0x1de9,0x2f72,0x3efb,
0xd68d,0xc704,0xf59f,0xe416,0x90a9,0x8120,0xb3bb,0xa232,
0x5ac5,0x4b4c,0x79d7,0x685e,0x1ce1,0x0d68,0x3ff3,0x2e7a,
0xe70e,0xf687,0xc41c,0xd595,0xa12a,0xb0a3,0x8238,0x93b1,
0x6b46,0x7acf,0x4854,0x59dd,0x2d62,0x3ceb,0x0e70,0x1ff9,
0xf78f,0xe606,0xd49d,0xc514,0xb1ab,0xa022,0x92b9,0x8330,
0x7bc7,0x6a4e,0x58d5,0x495c,0x3de3,0x2c6a,0x1ef1,0x0f78,
};
快速算法
使⽤C语⾔实现CRC-16快速算法。
unsignedshortdo_crc_table_1(unsignedchar*data,intlength)
{
unsignedshortfcs=0x0000;//初始化
while(length>0)
{
fcs=fcs<<8;
fcs=fcs^CRC_table(fcs>>8^*data;);
length--;
data++;
}
returnfcs;
}
6.⼩结本⽂介绍了CRC校验算法的原理，进⼀步介绍了CRC快速算法的原理，以及CRC余项表的计算⽅法，最后使⽤C语⾔实现该算法。