levi 发布于 2007-5-20 0:45:18
 CRC算法原理及实现
CRC算法原理及实现 一、算法介绍 CRC算法主要是一个计算除法的过程。算法有两个输入值，第一个是输入的信号，这通常是一个很长的数据，作为被除数。第二个是一个与具体的CRC算法相关的多项式，称为生成多项式，用作除数。基本的计算过程是，两者作模2除法。余数就是CRC结果。
模2除法等价于异或运算，因此，实现起来非常简单。
下面用一个简单的例子来说明CRC算法的计算过程。输入信号是101111，生成多项式是1001。被除数后面需要补充3个0。这是一个3位CRC。 图1 模2除法 商数在CRC算法中是没有用处的，需要的仅仅是余数。在上例中，余数为010。将余数附加到输入信号后面，即101111010，这个数是可以被1001整除的。
生成多项式最高位总是1，通常不写。 二、简单算法 生成多项式为"1 1000 0000 0000 0101"(CRC-16)，简记作0x18005。 /* 主程序 */ ... crc = 0;
for(i = 0; i < MSG_LENGTH; i++)
{
get_crc(data[i], &crc);
}
for(i = 0; i < 2; i++)
{
get_crc(0, &crc);
} ... /* 模2除法 */ void get_crc(unsigned char data, unsigned short *crc)
{
unsigned short gen_poly = 0x8005;
int i;
for(i = 0; i < 8; i++)
{
if(*crc & 0x8000)
{
*crc = ((*crc << 1) | ((data >> (7 - i)) & 1)) ^ gen_poly;
}
else
{
*crc = (*crc << 1) | ((data >> (7 - i)) & 1);
}
}
}
三、算法优化 3.1 算法分析 分析上面提供的16位CRC的例子。可以发现两个地方不是很好。
(1) 数据结束之后，还需要输入16位全0。
(2) 最开始的16位数据只是简单的移位，并没有除法运算。
分析图1中的除法过程，注意到这是一个模2除法，没有进位。每次试商之后，需要减去的生成多项式，可以保留在最后再减
图2 模2除法分析 将红色字体部分相加，得到10111101，用被除数来减去这个数，注意位置按照图2不变，结果就是010。 3.2 改进的算法 /* 主程序 */ ... crc = 0;
for(i = 0; i < MSG_LENGTH; i++)
{
get_crc(data[i], &crc);
}
... /* 模2除法 */ void get_crc(unsigned char data, unsigned short *crc)
{
unsigned short gen_poly = 0x8005;
int i;
for(i = 0; i < 8; i++)
{
if((*crc >> 15) ^ ((data >> (7-i)) & 1))
{
*crc = (*crc << 1) ^ gen_poly;
}
else
{
*crc <<= 1;
}
}
}
四、实现方案 4.1 硬件实现方法 CRC算法硬件结构可以用下图来描述:
图3 1位硬件结构 缓冲区初始化为全0。逐位提取输入数据，与缓冲区最高位做异或运算，如果结果为1，则将缓冲区左移1位，然后与生成多项式作异或运算。如果结果是0，则只将缓冲区数据左移1位。结果保存到缓冲区中。
图3方案适用于逐比特处理输入数据的情形。而通常情况是一次需要处理4比特，8比特等等。此时，只需要将连续多个比特的数据处理放在一个电路中实现就可以了。
对于3.2中的16位CRC处理过程，一次处理8比特的硬件方案描述如下： crc(0) = crc(8) xor crc(9) xor crc(10) xor crc(11) xor crc(12) xor crc(13) xor crc(14) xor crc(15) xor data(0) xor data(1) xor data(2) xor data(3) xor data(4) xor data(5) xor data(6) xor data(7)
crc(1) = crc(9) xor crc(10) xor crc(11) xor crc(12) xor crc(13) xor crc(14) xor crc(15) xor data(0) xor data(1) xor data(2) xor data(3) xor data(4) xor data(5) xor data(6)
crc(2) = crc(8) xor crc(9) xor data(6) xor data(7)
crc(3) = crc(9) xor crc(10) xor data(5) xor data(6)
crc(4) = crc(10) xor crc(11) xor data(4) xor data(5)
crc(5) = crc(11) xor crc(12) xor data(3) xor data(4)
crc(6) = crc(12) xor crc(13) xor data(2) xor data(3)
crc(7) = crc(13) xor crc(14) xor data(1) xor data(2)
crc(8) = crc(0) xor crc(14) xor crc(15) xor data(0) xor data(1)
crc(9) = crc(1) xor crc(15) xor data(0)
crc(10) = crc(2)
crc(11) = crc(3)
crc(12) = crc(4)
crc(13) = crc(5)
crc(14) = crc(6)
crc(15) = crc(7) xor crc(8) xor crc(9) xor crc(10) xor crc(11) xor crc(12) xor crc(13) xor crc(14) xor crc(15) xor data(0) xor data(1) xor data(2) xor data(3) xor data(4) xor data(5) xor data(6) xor data(7) 实际使用时，还需要注意一些问题：
(1) 输入数据和CRC是否MSB先传输？
(2) 输入数据和CRC是否有取反要求?
这些问题会对逻辑方程式有一定的影响, 但逻辑方程式形式类似。
举个例子来说明：
输入数据：长度为1024字节，取值从00 ~ FF循环，即00 01 ... FF 00 01 ... FF ... 00 01 ... FF。数据高位先传。
CRC结果：5a12 上述方法可以并行计算CRC的每一位，因此，用可编程逻辑器件来实现是很高效的。 4.2 查表法 当使用微处理器或单片机来计算CRC时，4.1中描述的方法就不太合适了，因为这个方法涉及到了太多的位运算，需要耗费很多的指令周期。当然，这种情况下，可以用3.2中介绍的方法。当需要进一步提高速度时，则可以采用查表法。
分析4.1中描述的处理过程。每处理１位数据时，需要根据CRC缓冲区数据来计算新的CRC缓冲区内容。当处理多位数据时，也是类似的过程。都涉及到输入数据和CRC缓冲区。实际上可以简化。新的缓冲区内容实际上取决于当前缓冲区高位与数据的异或运算结果。例如，16位CRC，8位数据，新的缓冲区内容取决于当前缓冲区高8位与数据的异或运算结果。这样，就可以建立一个查找表，索引就是异或运算结果。
对于3.2中16位CRC算法，改用查找表方法，程序如下： /* 主程序 */ ... crc = 0;
for(i = 0; i < MSG_LENGTH; i++)
{
crc = (crc << DATA_LEN) ^ crc_tab[((crc >> (CRC_LEN - DATA_LEN)) ^ data[i]) & 0xff];
}
... /* 查找表 */ unsigned short crc_tab[] =
{0x0000, 0x8005, 0x800F, 0x000A, 0x801B, 0x001E, 0x0014, 0x8011, 0x8033, 0x0036, 0x003C, 0x8039, 0x0028, 0x802D, 0x8027, 0x0022,
0x8063, 0x0066, 0x006C, 0x8069, 0x0078, 0x807D, 0x8077, 0x0072, 0x0050, 0x8055, 0x805F, 0x005A, 0x804B, 0x004E, 0x0044, 0x8041,
0x80C3, 0x00C6, 0x00CC, 0x80C9, 0x00D8, 0x80DD, 0x80D7, 0x00D2, 0x00F0, 0x80F5, 0x80FF, 0x00FA, 0x80EB, 0x00EE, 0x00E4, 0x80E1,
0x00A0, 0x80A5, 0x80AF, 0x00AA, 0x80BB, 0x00BE, 0x00B4, 0x80B1, 0x8093, 0x0096, 0x009C, 0x8099, 0x0088, 0x808D, 0x8087, 0x0082,
0x8183, 0x0186, 0x018C, 0x8189, 0x0198, 0x819D, 0x8197, 0x0192, 0x01B0, 0x81B5, 0x81BF, 0x01BA, 0x81AB, 0x01AE, 0x01A4, 0x81A1,
0x01E0, 0x81E5, 0x81EF, 0x01EA, 0x81FB, 0x01FE, 0x01F4, 0x81F1, 0x81D3, 0x01D6, 0x01DC, 0x81D9, 0x01C8, 0x81CD, 0x81C7, 0x01C2,
0x0140, 0x8145, 0x814F, 0x014A, 0x815B, 0x015E, 0x0154, 0x8151, 0x8173, 0x0176, 0x017C, 0x8179, 0x0168, 0x816D, 0x8167, 0x0162,
0x8123, 0x0126, 0x012C, 0x8129, 0x0138, 0x813D, 0x8137, 0x0132, 0x0110, 0x8115, 0x811F, 0x011A, 0x810B, 0x010E, 0x0104, 0x8101,
0x8303, 0x0306, 0x030C, 0x8309, 0x0318, 0x831D, 0x8317, 0x0312, 0x0330, 0x8335, 0x833F, 0x033A, 0x832B, 0x032E, 0x0324, 0x8321,
0x0360, 0x8365, 0x836F, 0x036A, 0x837B, 0x037E, 0x0374, 0x8371, 0x8353, 0x0356, 0x035C, 0x8359, 0x0348, 0x834D, 0x8347, 0x0342,
0x03C0, 0x83C5, 0x83CF, 0x03CA, 0x83DB, 0x03DE, 0x03D4, 0x83D1, 0x83F3, 0x03F6, 0x03FC, 0x83F9, 0x03E8, 0x83ED, 0x83E7, 0x03E2,
0x83A3, 0x03A6, 0x03AC, 0x83A9, 0x03B8, 0x83BD, 0x83B7, 0x03B2, 0x0390, 0x8395, 0x839F, 0x039A, 0x838B, 0x038E, 0x0384, 0x8381,
0x0280, 0x8285, 0x828F, 0x028A, 0x829B, 0x029E, 0x0294, 0x8291, 0x82B3, 0x02B6, 0x02BC, 0x82B9, 0x02A8, 0x82AD, 0x82A7, 0x02A2,
0x82E3, 0x02E6, 0x02EC, 0x82E9, 0x02F8, 0x82FD, 0x82F7, 0x02F2, 0x02D0, 0x82D5, 0x82DF, 0x02DA, 0x82CB, 0x02CE, 0x02C4, 0x82C1,
0x8243, 0x0246, 0x024C, 0x8249, 0x0258, 0x825D, 0x8257, 0x0252, 0x0270, 0x8275, 0x827F, 0x027A, 0x826B, 0x026E, 0x0264, 0x8261,
0x0220, 0x8225, 0x822F, 0x022A, 0x823B, 0x023E, 0x0234, 0x8231, 0x8213, 0x0216, 0x021C, 0x8219, 0x0208, 0x820D, 0x8207, 0x0202}; 有时会用到反转的输入和反转的CRC，此时，对于3.2中16位CRC算法，查找表方法如下： /* 主程序 */ ... crc = 0;
for(i = 0; i < MSG_LENGTH; i++)
{
crc = (crc >> DATA_LEN) ^ m_crc_tab1[(crc ^ data[i]) & 0xff];
}
... /* 查找表 */ unsigned short crc_tab[] =
{0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40, 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40, 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641, 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240, 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41, 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41, 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640, 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240, 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41, 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41, 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640, 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241, 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40, 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40, 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641, 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040};
「该帖子被 levi 在 2007-5-20 15:41:18 编辑过」
levi 发布于 2007-5-20 0:50:03
如果需要实现自己的CRC算法，那么需要明确下列问题，才能得到正确的算法。 (1) 数据及CRC位数
(2) 生成多项式
(3) 输入是否MSB(高位)先传输?
「该帖子被 levi 在 2007-5-20 12:41:39 编辑过」
BG1 发布于 2007-5-20 23:05:48
  条理非常清楚！我本来不懂，看过后就明白大半了，谢谢！
levi 发布于 2007-5-22 20:09:30
对于硬件实现方法，这里再做一下详细的说明：
首先分析每次输入1位的情形，可以用下图来说明：
(1) 缓冲区初始化为全0，表示还没有开始做除法。
(2) 输入数据与缓冲区最高位(即crc(15))做异或运算，如果结果为1，则表示商需要添一个1；为0则表示商需要添一个0。
如果商添1,则表示需要从被除数当前位置减去生成多项式(即0x18005)，但生成多项式最高位总是1，而被除数当前位也是1，因此两者相消。这就是生成多项式中不用写最高位的原因。此时，只要将被除数低位减去0x8005即可。缓冲区左移一位就是为了将被除数低位与0x8005对齐。
如果商添0，则表示被除数太小，不够与生成多项式做减法，此时，只需考虑被除数低位，缓冲区左移一位即可。
假定当前输入数据为data，则
crc(15) = crc(14) xor ((data xor crc(15) and '1') = crc(14) xor crc(15) xor(data)
crc(14) = crc(13) xor ((data xor crc(15) and '0') = crc(13)
crc(13) = crc(12) xor ((data xor crc(15) and '0') = crc(12)
...
crc(1) = crc(0) xor ((data xor crc(15) and '0') = crc(0)
crc(0) = '0' xor ((data xor crc(15) and '1') = crc(15) xor data
至此，一位硬件结构已经实现了，详细结果为：crc(0) = crc(15) xor data
crc(1) = crc(0)
crc(2) = crc(1) xor crc(15) xor data
crc(3) = crc(2)
crc(4) = crc(3)
crc(5) = crc(4)
crc(6) = crc(5)
crc(7) = crc(6)
crc(8) = crc(7)
crc(9) = crc(8)
crc(10) = crc(9)
crc(11) = crc(10)
crc(12) = crc(11)
crc(13) = crc(12)
crc(14) = crc(13)
crc(15) = crc(14) xor crc(15) xor data 然后，考虑多位数据处理过程，只需要将上面16个逻辑方程式的右边作为缓冲区内容，重复上面的过程，逐步计算新的缓冲区内容即可。
|
