单片机CRC快速算法

a 0 0 ]和一个二字节序列 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. 通过查余式表（表1），读取Ta00＝[a 0 0 ]的余式Ra00＝[ ha00 la00 ]； 2. 将Ra00与[ b c ]进行异或运算，从而得到[ a b c ]的余式Rabc＝[ habc labc ]，即habc＝ha00 ＆ b，labc＝la00 ＆ c。 由于[a 0 0 ]中只有一个字节不为零，因此，[a 0 0 ]余式表仅需要256个单元，即占用512个字节。

4　适用于51系列等单片机的算法 前面所述的办法可以直接用于51系列等单片机，因为512字节的余式表对它们的程序存储容量来说是完全不成问题的。 计算直接通过上述的递推过程来进行，每一次递推都是对一个三字节序列进行的计算：第一次是[ m1 m2 m3 ]，结果是[ h3 l3 ]；第二次是[ h3 l3 m4 ]，结果是[ h4 l4 ]；......，第i次是[ hi+1 li+1 mi+2 ]，结果是[ hi+2 li+2 ]；......；最后是[ hk+1 lk+1 mk+2 ]，最终结果是[ h l ]。如果有k个数据字节，则递推k次。下面给出一个三字节序列计算子程序，供每一次递推运算时调用。注意，在第一次被调用之前，先将m1、 m2和m3分别存入R0、R1和R2中（子程序返回时，计算结果将存放在R0和R1中）。从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入R2即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。当最后一次调用返回后，R0和R1分别存放的就是最终结果h和l 。

CRC MOV DPH, #table ; 指向余式表下半区


　　MOVC A, @A+DPTR ; 读余式的高字节

　　XRL A, R1 ; 计算余式的高字节

　　MOV R0, A ; 存入R0

　　INC DPH ; 指向余式表上半区

　　CLR A ;

　　MOVC A, @A+DPTR ; 读余式的低字节

　　XRL A, R2 ; 计算余式的低字节

　　MOV R1, A ; 存入R1

　　 RET

这一子程序只有12条指令，因此十分简捷，而且只占用16个机器周期，也就是说，相当于计算每一个字节只需16个机器周期即可完成，这将比传统的软件算法快十几倍。

表1 [ a 0 0 ] 余式表

a 0 1 2 3 4 5 6 7 8 9 A B C D E F
0× 0000 1021 2042 3063 4084 50A5 60C6 70E7 8108 9129 A14A B16B C18C D1AD E1CE F1EF
1× 1231 0210 3273 2252 52B5 4294 72F7 62D6 9339 8318 B37B A35A D3BD C39C F3FF E3DE
2× 2462 3443 0420 1401 64E6 74C7 44A4 5485 A56A B54B 8528 9509 E5EE F5CF C5AC D58D
3× 3653 2672 1611 0630 76D7 66F6 5695 46B4 B75B A77A 9719 8738 F7DF E7FE D79D C7BC
4× 48C4 58E5 6886 78A7 0840 1861 2802 3823 C9CC D9ED E98E F9AF 8948 9969 A90A B92B
5× 5AF5 4AD4 7AB7 6A96 1A71 0A50 3A33 2A12 DBFD CBDC FBBF EB9E 9B79 8B58 BB3B AB1A
6× 6CA6 7C87 4CE4 5CC5 2C22 3C03 0C60 1C41 EDAE FD8F CDEC DDCD AD2A BD0B 8D68 9D49
7× 7E97 6EB6 5ED5 4EF4 3E13 2E32 1E51 0E70 FF9F EFBE DFDD CFFC BF1B AF3A 9F59 8F78
8× 9188 81A9 B1CA A1EB D10C C12D F14E E16F 1080 00A1 30C2 20E3 5004 4025 7046 6067
9× 83B9 9398 A3FB B3DA C33D D31C E37F F35E 02B1 1290 22F3 32D2 4235 5214 6277 7256
A× B5EA A5CB 95A8 8589 F56E E54F D52C C50D 34E2 24C3 14A0 0481 7466 6447 5424 4405
B× A7DB B7FA 8799 97B8 E75F F77E C71D D73C 26D3 36F2 0691 16B0 6657 7676 4615 5634
C× D94C C96D F90E E92F 99C8 89E9 B98A A9AB 5844 4865 7806 6827 18C0 08E1 3882 28A3
D× CB7D DB5C EB3F FB1E 8BF9 9BD8 ABBB BB9A 4A75 5A54 6A37 7A16 0AF1 1AD0 2AB3 3A92
E× FD2E ED0F DD6C CD4D BDAA AD8B 9DE8 8DC9 7C26 6C07 5C64 4C45 3CA2 2C83 1CE0 0CC1
F× EF1F FF3E CF5D DF7C AF9B BFBA 8FD9 9FF8 6E17 7E36 4E55 5E74 2E93 3EB2 0ED1 1EF0

5 适用于PIC单片机的算法 表1所示的余式表虽然只占用512个字节的程序存储空间，但对于PIC单片机来说还是太大了，需要再进行压缩。思路是这样的： 将Ta00＝[a 0 0 ]分解成Te00＝[e 0 0 ]和Tf00＝[f 0 0 ]，并使字节e的上半字节内容与a的上半字节相同但下半字节为零，同时使字节f的下半字节内容与a的下半字节相同但上半字节为零，然后用Te00和Tf00生成余式表来代替Ta00余