單片機CRC快速算法

3.2 三字節序列計算 提到簡單快捷，人們自然會想到采用查表的辦法，例如事先把三字節序列的所有余式計算出來，置于一個稱為“余式表”的表格中，供隨時讀取。不過，這樣的表格太大，需要224個單元，也就是要占用225個字節的存儲空間，這對單片機來說是絕對無法接受的，因此，需要想辦法減少所占用的存儲空間。

　　　　　　　　　　　　　　　　 圖1

遞推計算步驟 設一個三字節序列Tabc ＝[ a b c ] 、一個 Ta00＝[ 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個機器周期即可完成，這將比傳統的軟件算法快十幾倍。