[讨论] 应用技巧/简单实用的单片机CRC快速算法

摘 要： 提供两个实用的、能够在单片机上通过软件来实现的CRC快速算法，其中一个适用于51系列等单片机，另一个适用于pic单片机，这两种算法十分简单快捷。

（1）

    其中，x^rD(x)表示将数据序列D左移r位（即在D的末尾再增加r个0位），Q(x)代表这一除法所得的商，R(x)就是所需的余式。这一运算关系还可以用式（2）来表达

（2）

    其中，Re[ ]表示对括号内的式子进行取余式运算。

    检验码的编码计算如上所述，而检验过程则是对M序列直接进行除法取余式运算，即

（3）

    或表示为

（4）

    所得到的余式R(x)若为零则表示数据正确，否则认为发生错误。

    这里仅以CRC-CCITT标准生成多项式为例进行说明。CRC-CCITT是一个17位生成多项式G＝[1 0001 0000 0010 0001]，用多项式形式表示为G(x)＝x¹⁶＋x¹²＋x⁵＋1，由它产生的检验码R的二进制位数是16位（2字节）。

    单片机的操作是以字节形式进行的，所以，算法应以字节为单位进行运算。这里将把用字节构成的二进制序列称为“字节序列”，显然，单片机的数据序列、检验码以及它俩组成的序列M都是字节序列，或者说是“多字节序列”。

    实际上，这种算法所要解决的问题就是如何对多字节序列进行除法取余式运算的问题。

    首先设一个由i个字节 m₁、m₂、......、m_i-1、m_i 构成的8×i位二进制序列，并用字节形式表示它为M_i ＝[ m₁ m₂ ...... m_i-1 m_i ]，然后再截取M_i的前（i-1）个字节构成一个M_i-1序列，M_i-1＝[ m₁ m₂ ...... m_i-1 ]，这两个序列之间的关系可以用多项式表示为M_i(x)＝x ⁸M_i-1(x)＋m_i(x)，其中，m_i(x)是字节m_i的二进制多项式表示形式，而x⁸M_i-1(x)表示将M_i-1序列左移一个字节。

    对于序列M_i-1来说，

(5)

    其中，二字节序列余式R_i-1＝［h_i-1 l_i-1］。

     而对于M_i序列来说，可得

(6)

    这一结果的前一项为一整数，所以它与余式无关，这样，余式只可能出现在后一项中。因此，对x⁸R_i-1(x)＋m_i(x)取余式运算就等价于对M_i(x)的取余式运算,用式（4）的形式表示为

(7)

    x⁸R_i-1(x)+m_i(x)代表一个由R_i-1和m_i共同组成的三字节序列[ h_i-1 l_i-1 m_i]，而且对这个三字节序列的取余式运算就等于对M_i序列的取余式运算，其结果就是M_i序列的余式R_i＝[ h_i l_i ]。同理可得，对于一个M_i+１序列（它比M_i序列多一个字节m_i+1）来说，对三字节序列[ h_i l_i m_i+1]的运算就等价于对M_i+1序列的运算，其结果就是M_i+1序列的余式R_i+1＝[ h_i+1 l_i+1 ]。

    显然，这反映出一种如图1所示的递推运算的规律。可见，每一次递推运算都是对一个三字节序列的计算，所以，如何简单快捷地对三字节序列进行计算是这种算法的又一个关键。

    提到简单快捷，人们自然会想到采用查表的办法，例如事先把三字节序列的所有余式计算出来，置于一个称为“余式表”的表格中，供随时读取。不过，这样的表格太大，需要2²⁴个单元，也就是要占用2²⁵个字节的存储空间，这对单片机来说是绝对无法接受的，因此，需要想办法减少所占用的存储空间。

　图1 递推计算步骤

    设一个三字节序列T_abc ＝[ a b c ] 、一个 T_a00＝[ a 0 0 ]和一个二字节序列 T_bc＝[ b c ]。可以用多项式形式表示它们之间的关系为 T_abc(x)＝T_a00(x)＋T_bc(x)，因此，对T_a00来说，

（8）

    而对T_abc来说，

    其中，Q_a00是整数，与余式无关；而R_a00和T_bc都是二字节序列，因而，它们的和（模2加法，即异或运算）仍然是二字节序列（二进制16位，小于生成多项式的17位），因此，它就是 T_abc的余式R_abc，即

（9）

    这说明，可以把三字节序列T_abc＝[ a b c ]的运算分解成两个步骤来进行，如图2所示。

    1. 通过查余式表（表1），读取T_a00＝[a 0 0 ]的余式R_a00＝[ h_a00 l_a00 ]；

    2. 将R_a00与[ b c ]进行异或运算，从而得到[ a b c ]的余式R_abc＝[ h_abc l_abc ]，即h_abc＝h_{a00 ?} b，l_abc＝l_{a00 ?} c。

    由于[a 0 0 ]中只有一个字节不为零，因此，[a 0 0 ]余式表仅需要256个单元，即占用512个字节。

图２ 三字节序列的计算办法[ a b c ]

    前面所述的办法可以直接用于51系列等单片机，因为512字节的余式表对它们的程序存储容量来说是完全不成问题的。

    计算直接通过上述的递推过程来进行，每一次递推都是对一个三字节序列进行的计算：第一次是[ m₁ m₂ m₃ ]，结果是[ h₃ l₃ ]；第二次是[ h₃ l₃ m₄ ]，结果是[ h₄ l₄ ]；......，第i次是[ h_i+1 l_i+1 m_i+2 ]，结果是[ h_i+2 l_i+2 ]；......；最后是[ h_k+1 l_k+1 m_k+2 ]，最终结果是[ h l ]。如果有k个数据字节，则递推k次。下面给出一个三字节序列计算子程序，供每一次递推运算时调用。注意，在第一次被调用之前，先将m₁、 m₂和m₃分别存入R0、R1和R2中（子程序返回时，计算结果将存放在R0和R1中）。从第二次调用时开始，每次在调用之前只需先将参与本次运算的字节存入R2即可（第二次是m₄，第三次是m₅，...，第i次是m_i+2，...）。当最后一次调用返回后，R0和R1分别存放的就是最终结果h和l 。

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