《简单实用的单片机CRC快速算法》由会员分享，可在线阅读，更多相关《简单实用的单片机CRC快速算法（9页珍藏版）》请在金锄头文库上搜索。
1、摘要提供两个实用的、能够在单片机上通过软件来实现的 CRC 快速算法，其中一个适用于 51 系列等单片机，另一个适用于 PIC 单片机，这两种算法十分简单快捷。关键词CRC 算法 单片机1 引言CRC（循环冗余码）检验技术广泛应用于测控及通信领域。在很多情况下，CRC 计算是靠专用的硬件来实现的，但是对于小型低成本的单片机系统来说，若要在没有这些硬件的支持下实现 CRC 检验，首先要解决的就是如何通过软件高效快速地完成 CRC计算的问题，也就是 CRC 算法的问题。这里将提供两种算法，它们稍有不同，一种适用于程序空间大一些的 51 系列等单片机，另一种适用于程序空间的使用条件十分苛刻的 PIC
2、 单片机。这些算法按字节进行计算，仅使用查表和简单的异或运算等操作，所以，计算过程相当简捷，而计算速度却很快。下面先简述一下 CRC 原理，然后再以 CRC-CCITT 标准生成多项式为例对算法进行说明，并给出一个 51 系列单片机子程序和一个 PIC 单片机子程序。2CRC 原理CRC 检验原理实际上就是在一个 p 位二进制数据序列之后附加一个 r 位二进制检验码(序列),从而构成一个总长为 n p r 位的二进制序列，例如， p 位二进制数据序列D dp-1dp-2.d1d0， r 位二进制检验码 R rr-1rr-2.r1r0，所得到的这个 n 位二进制序列就是 M dp-1dp-2.d
3、1d0rr-1rr-2.r1r0；附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏,因此,通过检查这一关系,就可以实现对数据正确性的检验。校验码 R 是通过对数据序列 D 进行二进制除法取余式运算得到的，它被一个称为生成多项式的（ r1）位二进制序列 G grgr-1.g1g0来除，用多项式形式表示为（1）其中， xrD(x)表示将数据序列 D 左移 r 位（即在 D 的末尾再增加 r 个 0 位）， Q(x)代表这一除法所得的商， R(x)就是所需的余式。这一运算关系还可以用式（2）来表达（2
4、）其中，Re表示对括号内的式子进行取余式运算。广告： 检验码的编码计算如上所述，而检验过程则是对 M 序列直接进行除法取余式运算，即（3）或表示为（4）所得到的余式 R(x)若为零则表示数据正确，否则认为发生错误。3 快速算法的基本思路这里仅以 CRC-CCITT 标准生成多项式为例进行说明。CRC-CCITT 是一个 17 位生成多项式 G10001000000100001，用多项式形式表示为 G(x) x16 x12 x51，由它产生的检验码 R 的二进制位数是 16 位（2 字节）。单片机的操作是以字节形式进行的，所以，算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节
5、序列”，显然，单片机的数据序列、检验码以及它俩组成的序列 M 都是字节序列，或者说是“多字节序列”。实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。3.1 多字节序列运算规律首先设一个由 i 个字节 m1、 m2、.、 mi-1、 mi构成的 8i 位二进制序列，并用字节形式表示它为 Mi m1m2.mi-1mi，然后再截取 Mi的前（ i-1）个字节构成一个 Mi-1序列， Mi-1 m1m2.mi-1，这两个序列之间的关系可以用多项式表示为 Mi(x) x8Mi-1(x) mi(x)，其中， mi(x)是字节 mi的二进制多项式表示形式，而 x8Mi-1(x)表
6、示将 Mi-1序列左移一个字节。对于序列 Mi-1来说，(5)其中，二字节序列余式 Ri-1 hi-1li-1。而对于 Mi序列来说，可得(6) 这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中。因此，对 x8Ri-1(x) mi(x)取余式运算就等价于对 Mi(x)的取余式运算,用式（4）的形式表示为(7)x8Ri-1(x)+mi(x)代表一个由 Ri-1和 mi共同组成的三字节序列 hi-1li-1mi，而且对这个三字节序列的取余式运算就等于对 Mi序列的取余式运算，其结果就是 Mi序列的余式Ri hili。同理可得，对于一个 Mi+ 序列（它比 Mi序列多一个字
7、节 mi+1）来说，对三字节序列 hilimi+1的运算就等价于对 Mi+1序列的运算，其结果就是 Mi+1序列的余式Ri+1 hi+1li+1。显然，这反映出一种如图 1 所示的递推运算的规律。可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。3.2 三字节序列计算提到简单快捷，人们自然会想到采用查表的办法，例如事先把三字节序列的所有余式计算出来，置于一个称为“余式表”的表格中，供随时读取。不过，这样的表格太大，需要 224个单元，也就是要占用 225个字节的存储空间，这对单片机来说是绝对无法接受的，因此，需要想办法减少所占用的存
8、储空间。图 1 递推计算步骤设一个三字节序列 Tabc a b c、一个 Ta00 a00和一个二字节序列 Tbc b c。可以用多项式形式表示它们之间的关系为 Tabc(x) Ta00(x) Tbc(x)，因此，对 Ta00来说，（8）而对 Tabc来说， 其中， Qa00是整数，与余式无关；而 Ra00和 Tbc都是二字节序列，因而，它们的和（模 2 加法，即异或运算）仍然是二字节序列（二进制 16 位，小于生成多项式的 17位），因此，它就是 Tabc的余式 Rabc，即（9）这说明，可以把三字节序列 Tabc a b c 的运算分解成两个步骤来进行，如图 2所示。1.通过查余式表（表
9、1），读取 Ta00 a00的余式 Ra00 ha00la00；2.将 Ra00与 b c 进行异或运算，从而得到 a b c 的余式 Rabc habclabc，即habc ha00b， labc la00c。由于 a00中只有一个字节不为零，因此， a00余式表仅需要 256 个单元，即占用 512 个字节。图三字节序列 a b c的计算办法4适用于 51 系列等单片机的算法前面所述的办法可以直接用于 51 系列等单片机，因为 512 字节的余式表对它们的程序存储容量来说是完全不成问题的。 计算直接通过上述的递推过程来进行，每一次递推都是对一个三字节序列进行的计算：第一次是 m1m2m3，
10、结果是 h3l3；第二次是 h3l3m4，结果是 h4l4；.，第 i 次是 hi+1li+1mi+2，结果是 hi+2li+2；.；最后是 hk+1lk+1mk+2，最终结果是hl。如果有 k 个数据字节，则递推 k 次。下面给出一个三字节序列计算子程序，供每一次递推运算时调用。注意，在第一次被调用之前，先将 m1、 m2和 m3分别存入R0、R1 和 R2 中（子程序返回时，计算结果将存放在 R0 和 R1 中）。从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入 R2 即可（第二次是 m4，第三次是 m5，.，第 i 次是 mi+2，.）。当最后一次调用返回后，R0 和 R
11、1 分别存放的就是最终结果 h 和 l。CRC MOV DPH,#table ;指向余式表下半区MOV DPL,R0 ;指向对应单元CLR A ;MOVC A,A+DPTR ;读余式的高字节XRL A,R1 ;计算余式的高字节MOV R0,A ;存入 R0INC DPH ;指向余式表上半区CLR A ;MOVC A,A+DPTR ;读余式的低字节XRL A,R2 ;计算余式的低字节MOV R1,A ;存入 R1RET这一子程序只有 12 条指令，因此十分简捷，而且只占用 16 个机器周期，也就是说，相当于计算每一个字节只需 16 个机器周期即可完成，这将比传统的软件算法快十几倍。表 1a00余
12、式表a 0 1 2 3 4 5 6 7 8 9 A B C D E F0 0000 1021 2042 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1AD E1CE F1EF1 1231 0210 3273 2252 52B5 4294 72F7 62D6 9339 8318 B37B A35A D3BD C39C F3FF E3DE2 2462 3443 0420 1401 64E6 74C7 44A4 5485 A56A B54B 8528 9509 E5EE F5CF C5AC D58D3 3653 2672 1611 0630
13、76D7 66F6 5695 46B4 B75B A77A 9719 8738 F7DF E7FE D79D C7BC4 48C4 58E5 6886 78A7 0840 1861 2802 3823 C9CC D9ED E98E F9AF 8948 9969 A90A B92B5 5AF5 4AD4 7AB7 6A96 1A71 0A50 3A33 2A12 DBFD CBDC FBBF EB9E 9B79 8B58 BB3B AB1A6 6CA6 7C87 4CE4 5CC5 2C22 3C03 0C60 1C41 EDAE FD8F CDEC DDCD AD2A BD0B 8D68 9D
14、497 7E97 6EB6 5ED5 4EF4 3E13 2E32 1E51 0E70 FF9F EFBE DFDD CFFC BF1B AF3A 9F59 8F788 9188 81A9 B1CA A1EB D10C C12D F14E E16F 1080 00A1 30C2 20E3 5004 4025 7046 60679 83B9 9398 A3FB B3DA C33D D31C E37F F35E 02B1 1290 22F3 32D2 4235 5214 6277 7256A B5EA A5CB 95A8 8589 F56E E54F D52C C50D 34E2 24C3 14A
15、0 0481 7466 6447 5424 4405B A7DB B7FA 8799 97B8 E75F F77E C71D D73C 26D3 36F2 0691 16B0 6657 7676 4615 5634C D94C C96D F90E E92F 99C8 89E9 B98A A9AB 5844 4865 7806 6827 18C0 08E1 3882 28A3D CB7D DB5C EB3F FB1E 8BF9 9BD8 ABBB BB9A 4A75 5A54 6A37 7A16 0AF1 1AD0 2AB3 3A92E FD2E ED0F DD6C CD4D BDAA AD8B 9DE8 8DC9 7C26 6C07 5C64 4C45 3CA2 2C83 1CE0 0CC1F EF1F FF3E CF5D DF7C AF9B BFBA 8FD9 9FF8 6E17 7E36 4E55 5E74 2E93 3EB2 0ED1 1EF0sss 5 适用于 PIC 单片机的算法表 1 所示的余式表虽然只占用 512 个字节的程序存储空间，但对于 PIC 单片机来说还是太大了，需要再进行压缩。思路是这样的：将 Ta00 a00分解成 Te00 e00和 Tf00 f 00，并使字节 e 的上半字节内容与a 的上
