简析CRC循环冗余校验码

一、引言

因为最近需要用到CRC循环冗余校验码,所以上网查了一些资料,但是找了一圈没有说得比较明白的,不少文章都只说了一部分,看了让人摸不着头脑,在经过一番纸上列式计算后,yellowko算是搞清楚了这里面的道道,所以记录分享一下。

二、基础概念

       CRC码是一种校验码,具有一定的纠错能力,但是一般不用来纠错,想了解其纠错的可参考《一种改进的循环冗余校验纠错技术》这篇文章,本文仅讨论CRC的检错。操作就是对数据做模二除法,得到的余数就是CRC校验码,更详细的原理上的内容可以参考这篇文章,或者Wiki的相关页面

       在CRC中有几个参数或者是操作这里得说明一下:

       初始值(initial value):设定的CRC初值,在计算数据流第一个值时预先设定的CRC值,会在最初一次计算中与数据做异或。

       位宽(width):CRC的长度,例如8、16、32,比较特殊的1位其实也就是奇偶校验码

       生成多项式(generator polynomial):用于产生CRC校验码的多项式,需要满足一定的特征,以达到一定的检错性能,即使是相同位宽也有性能不分上下的多种,根据需要挑选现成的即可。例如X16+ X15+X2+1。生成多项式通常使用简化的记法,由于最高位都固定为1,所以省略掉,因此前面这个式子就可以用十六进制记为0x8005。

       输入输出数据反转(refin、refout):这个反转是倒序的意思,有一些协议要求对数据逆序计算,也就是0x01变为0x80来算,算出CRC值后再倒过来进行校验。为什么会有这种奇怪的要求呢,或许是为了编程方便,详细的后面会讲解。

       异或输出(xorout):计算完成后再与其进行异或得出最终的结果,大多数情况下为0x00。

三、过程分析

举个例子如果位宽为8,初始值为0x00,生成多项式为0x9B(那么除数为0x19B),不进行输入输出的反转,也不进行异或输出,输入值(被除数)为0x80,那么计算过程如下

看不见图片可以用下面的代码直接生成,虽然不带颜色,但是也有助于理解

正向计算和反向计算的示例

绿色是补的0,数量为位宽,这里是8个,蓝色的是被除数相对除数在左移,遇到1时需要做异或运算,本来应该是9位一起运算,但是由于最高位运算一定为0,所以实际上除数的最高位可以不参与运算,在编程时就可以忽略掉,遇到1也左移。所以最后红色的结果就是0x0B(00001011)。如果要做反转的操作呢,上面的式子就相当于0x01做了输入反转的计算,一般输入输出反转都是同时的,如果输出也需要反转,那结果就是0x0B的反转即0xD0(11010000),就像上面右图演示的。如果要有初始值怎么样,前面的式子就等效于输入时0x7F(01111111),初始值是0xFF(11111111),其余不变。这两个变式都可以在这个在线计算CRC的网站计算出来,选择hex输入输出,计算CRC-8就可以在下面的结果中找到。

四、编程实现

要实现CRC的计算,大方向有两种,一种是计算法,一种是查表法。计算CRC时一般一次计算一个字节,计算得到的结果作为下一次计算的初始值。

1.计算法求CRC值的实现

下面是分别列举了正常计算和输入输出反向的计算方法,两种方法的原理在前面都有。程序是用用Javascript写的,大家可以直接在浏览器里按F12粘贴到控制台里验证,要移植成其他的语言也很简单。

//正向计算
var inputData = [0x80];
function crc_8(data, len) {
    var crc = 0x00;
    var poly = 0x9B;
    var i, j;

    for (i = 0; i < len; i++) {
        crc ^= data[i];
        console.log(crc.toString(2).padStart(8, '0') + ('0').repeat(8));
        for (j = 0; j < 8; j++) {
            if ((crc & 0x80) != 0) {
                crc <<= 1;
                crc &= 0xFF;    //限制住数据长度为8bit
                console.log((' ').repeat(j + 1) + crc.toString(2).padStart(8, '0'));
                console.log((' ').repeat(j + 1) + poly.toString(2).padStart(8, '0'));
                crc ^= poly;
                console.log('---------------');
                console.log((' ').repeat(j + 1) + crc.toString(2).padStart(8, '0'));
            }
            else {
                crc <<= 1;
                crc &= 0xFF;    //限制住数据长度为8bit
            }
        }
        console.log((' ').repeat(8) + crc.toString(2).padStart(8, '0'));
    }
    return crc & 0xFF;  //限制住数据长度为8bit
}
crc_8(inputData, inputData.length).toString(16).padStart(2, '0');

//反向计算
var inputData = [0x01];
function crc_8(data, len) {
    var crc = 0x00;
    var poly = 0xD9;
    var i, j;

    for (i = 0; i < len; i++) {
        crc ^= data[i];
        console.log(('0').repeat(8) + crc.toString(2).padStart(8, '0'));
        for (j = 0; j < 8; j++) {
            if ((crc & 0x01) != 0) {
                crc >>= 1;
                console.log((' ').repeat(7 - j) + crc.toString(2).padStart(8, '0'));
                console.log((' ').repeat(7 - j) + poly.toString(2).padStart(8, '0'));
                crc ^= poly;
                console.log('---------------');
                console.log((' ').repeat(7 - j) + crc.toString(2).padStart(8, '0'));
            }
            else {
                crc >>= 1;
            }
        }
        console.log(crc.toString(2).padStart(8, '0'));
    }
    return crc;
}
crc_8(inputData, inputData.length).toString(16).padStart(2, '0');

可以看出,正向计算直接得出了前面举例的其实长除法式子,而输入输出的反转就是把式子做镜像翻转,但是反转计算直接右移即可,不用考虑移出去的数据还会有影响,而像Javascript这类语言,并没有办法卡死数据长度为8bit,在正向计算左移时高位不会被移出去,在最终输出时高位会有一定影响,需要丢弃掉。所以例如Modbus协议就会要求倒序输入倒序输出,也就是后一种方法。这在很多文章里都没说清楚,都是说一个正序的原理就开始贴倒序的代码,让人看不明白。

2.查表法求CRC值的实现

查表法就是把一个字节一共256种情况所对应的256种CRC码对应起来,要用时直接查询即可。

//查表法计算CRC
var inputData = [0x80];
var crcTable = [
    0x00, 0x9b, 0xad, 0x36, 0xc1, 0x5a, 0x6c, 0xf7, 0x19, 0x82, 0xb4, 0x2f, 0xd8, 0x43, 0x75, 0xee,
    0x32, 0xa9, 0x9f, 0x04, 0xf3, 0x68, 0x5e, 0xc5, 0x2b, 0xb0, 0x86, 0x1d, 0xea, 0x71, 0x47, 0xdc,
    0x64, 0xff, 0xc9, 0x52, 0xa5, 0x3e, 0x08, 0x93, 0x7d, 0xe6, 0xd0, 0x4b, 0xbc, 0x27, 0x11, 0x8a,
    0x56, 0xcd, 0xfb, 0x60, 0x97, 0x0c, 0x3a, 0xa1, 0x4f, 0xd4, 0xe2, 0x79, 0x8e, 0x15, 0x23, 0xb8,
    0xc8, 0x53, 0x65, 0xfe, 0x09, 0x92, 0xa4, 0x3f, 0xd1, 0x4a, 0x7c, 0xe7, 0x10, 0x8b, 0xbd, 0x26,
    0xfa, 0x61, 0x57, 0xcc, 0x3b, 0xa0, 0x96, 0x0d, 0xe3, 0x78, 0x4e, 0xd5, 0x22, 0xb9, 0x8f, 0x14,
    0xac, 0x37, 0x01, 0x9a, 0x6d, 0xf6, 0xc0, 0x5b, 0xb5, 0x2e, 0x18, 0x83, 0x74, 0xef, 0xd9, 0x42,
    0x9e, 0x05, 0x33, 0xa8, 0x5f, 0xc4, 0xf2, 0x69, 0x87, 0x1c, 0x2a, 0xb1, 0x46, 0xdd, 0xeb, 0x70,
    0x0b, 0x90, 0xa6, 0x3d, 0xca, 0x51, 0x67, 0xfc, 0x12, 0x89, 0xbf, 0x24, 0xd3, 0x48, 0x7e, 0xe5,
    0x39, 0xa2, 0x94, 0x0f, 0xf8, 0x63, 0x55, 0xce, 0x20, 0xbb, 0x8d, 0x16, 0xe1, 0x7a, 0x4c, 0xd7,
    0x6f, 0xf4, 0xc2, 0x59, 0xae, 0x35, 0x03, 0x98, 0x76, 0xed, 0xdb, 0x40, 0xb7, 0x2c, 0x1a, 0x81,
    0x5d, 0xc6, 0xf0, 0x6b, 0x9c, 0x07, 0x31, 0xaa, 0x44, 0xdf, 0xe9, 0x72, 0x85, 0x1e, 0x28, 0xb3,
    0xc3, 0x58, 0x6e, 0xf5, 0x02, 0x99, 0xaf, 0x34, 0xda, 0x41, 0x77, 0xec, 0x1b, 0x80, 0xb6, 0x2d,
    0xf1, 0x6a, 0x5c, 0xc7, 0x30, 0xab, 0x9d, 0x06, 0xe8, 0x73, 0x45, 0xde, 0x29, 0xb2, 0x84, 0x1f,
    0xa7, 0x3c, 0x0a, 0x91, 0x66, 0xfd, 0xcb, 0x50, 0xbe, 0x25, 0x13, 0x88, 0x7f, 0xe4, 0xd2, 0x49,
    0x95, 0x0e, 0x38, 0xa3, 0x54, 0xcf, 0xf9, 0x62, 0x8c, 0x17, 0x21, 0xba, 0x4d, 0xd6, 0xe0, 0x7b
];

function crc_8(data, len) {
    var crc = 0x00; //crc初值
    for (var i = 0; i < len; i++) {
        crc = crcTable[crc ^ data[i]];
    }
    return crc;
}
crc_8(inputData, inputData.length).toString(16).padStart(2, '0');

这个表的生成也不麻烦,稍微修改一下前面计算法的程序即可

//crc表的生成
function crcTableGen_8(data) {
    var crc = data;     //注意这里的crc寄存器是没有初值的
    var poly = 0x9B;
    var i, j;
    for (j = 0; j < 8; j++) {
        if ((crc & 0x80) != 0) {
            crc <<= 1;
            crc &= 0xFF;    //限制住数据长度为8bit
            crc ^= poly;
        }
        else {
            crc <<= 1;
            crc &= 0xFF;    //限制住数据长度为8bit
        }
    }
    return crc & 0xFF;  //限制住数据长度为8bit
}
var str = '';
for (var i = 0; i < 16; i++) {
    for (var j = 0; j < 16; j++) {
        str += '0x' + crcTableGen_8(i * 16 + j).toString(16).padStart(2, '0') + ',';
    }
    str += '\n';
}
console.log(str);

五、其余的参考链接

CRC-16校验原理与说明

CRC(循环冗余校验)在线计算(这个比较卡,经常点了没反应,虽然定制选项很强,但是不如文中链接那个稳定)

STM32开发 -- CRC校验码

循环冗余校验(CRC)算法入门引导


知识共享许可协议

本作品由yellowko采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据