單片機CRC快速算法

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

　　　　　　　　　　　　　　　　 圖1

遞推計算步驟 設(shè)一個三字節(jié)序列Tabc ＝[ a b c ] 、一個 Ta00＝[ a 0 0 ]和一個二字節(jié)序列 Tbc＝[ b c ]?？梢杂枚囗検叫问奖硎舅鼈冎g的關(guān)系為 Tabc(x)＝Ta00(x)＋Tbc(x)，因此，對Ta00來說，
　

（8） 而對Tabc來說，

?其中，Qa00是整數(shù)，與余式無關(guān)；而Ra00和Tbc都是二字節(jié)序列，因而，它們的和（模2加法，即異或運算）仍然是二字節(jié)序列（二進(jìn)制16位，小于生成多項式的17位），因此，它就是 Tabc的余式Rabc，即

（9） 這說明，可以把三字節(jié)序列Tabc＝[ a b c ]的運算分解成兩個步驟來進(jìn)行，如圖2所示。 1. 通過查余式表（表1），讀取Ta00＝[a 0 0 ]的余式Ra00＝[ ha00 la00 ]； 2. 將Ra00與[ b c ]進(jìn)行異或運算，從而得到[ a b c ]的余式Rabc＝[ habc labc ]，即habc＝ha00 ＆ b，labc＝la00 ＆ c。 由于[a 0 0 ]中只有一個字節(jié)不為零，因此，[a 0 0 ]余式表僅需要256個單元，即占用512個字節(jié)。

4　適用于51系列等單片機的算法 前面所述的辦法可以直接用于51系列等單片機，因為512字節(jié)的余式表對它們的程序存儲容量來說是完全不成問題的。 計算直接通過上述的遞推過程來進(jìn)行，每一次遞推都是對一個三字節(jié)序列進(jìn)行的計算：第一次是[ m1 m2 m3 ]，結(jié)果是[ h3 l3 ]；第二次是[ h3 l3 m4 ]，結(jié)果是[ h4 l4 ]；......，第i次是[ hi+1 li+1 mi+2 ]，結(jié)果是[ hi+2 li+2 ]；......；最后是[ hk+1 lk+1 mk+2 ]，最終結(jié)果是[ h l ]。如果有k個數(shù)據(jù)字節(jié)，則遞推k次。下面給出一個三字節(jié)序列計算子程序，供每一次遞推運算時調(diào)用。注意，在第一次被調(diào)用之前，先將m1、 m2和m3分別存入R0、R1和R2中（子程序返回時，計算結(jié)果將存放在R0和R1中）。從第二次調(diào)用時開始，每次在調(diào)用之前只需先將參與本次運算的字節(jié)存入R2即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。當(dāng)最后一次調(diào)用返回后，R0和R1分別存放的就是最終結(jié)果h和l 。

CRC MOV DPH, #table ; 指向余式表下半?yún)^(qū)


　　MOVC A, @A+DPTR ; 讀余式的高字節(jié)

　　XRL A, R1 ; 計算余式的高字節(jié)

　　MOV R0, A ; 存入R0

　　INC DPH ; 指向余式表上半?yún)^(qū)

　　CLR A ;

　　MOVC A, @A+DPTR ; 讀余式的低字節(jié)

　　XRL A, R2 ; 計算余式的低字節(jié)

　　MOV R1, A ; 存入R1

　　 RET

這一子程序只有12條指令，因此十分簡捷，而且只占用16個機器周期，也就是說，相當(dāng)于計算每一個字節(jié)只需16個機器周期即可完成，這將比傳統(tǒng)的軟件算法快十幾倍。