[發(fā)明專利]一種非整字節(jié)數(shù)據(jù)的循環(huán)冗余校驗算法

有效

• 申請?zhí)枺?/td>: 201310246949.5
• 申請日: 2013-06-20
• 公開（公告）號: CN103297196A
• 公開（公告）日: 2013-09-11
• 發(fā)明（設(shè)計）人: 楊尚勝
• 申請（專利權(quán)）人: 成都國星通信有限公司
• 主分類號: H04L1/00
• 分類號: H04L1/00
• 代理公司: 成都金英專利代理事務(wù)所(普通合伙) 51218
• 代理人: 袁英

1.一種非整字節(jié)數(shù)據(jù)的循環(huán)冗余校驗算法，CRC數(shù)學(xué)本質(zhì)是對傳輸信息多項式對CRC生成多項式求余，CRC16的生成多項式為:G(x)=x¹⁶+x¹²+x⁵+1，其計算方法為：將16個0添加到S(x)的后面，也就是S(x)=r¹⁶×S(x)，其中r=2為二進(jìn)制多項式操作的基，然后S(x)對生成多項式G(x)做除法運(yùn)算，即進(jìn)行邏輯異或操作，最后得到除法的余數(shù)部分，即為CRC16，簡稱為C_reg，而商部分簡稱M(x)，其特征在于：其包括以下步驟：

S1：假設(shè)S_m對應(yīng)的CRC16值為C_reg，由定義，則：

CRCSm=(R2*Sm)Mod(G(x))=Greg=Crc16_Table[Sm]]]>????(式1)

R²*S_m=M(x)*G(x)+C_reg??????????????????(式2)

S2：在S_m后增加n位不足一個字節(jié)信息位，組成一個新的二進(jìn)制多項式S'_m，計算S'_m的CRC16，其包括以下步驟：

S201：在S_m后增加n位不足一個字節(jié)信息位，組成一個新的二進(jìn)制多項式S'_m，

S'_m=rⁿ*S_m+B_n??????????????????????????????(式3)

B_n表示n位二進(jìn)制多項式，其中高位在前，低位在后。

S202：對S'_m進(jìn)行增加16個0操作保證余數(shù)直接就是數(shù)據(jù)流的CRC16結(jié)果，得：

R²*S'_m=R²*(rⁿ*S_m+B_n)=rⁿ*(R²*S_m)+R²*B_n??????????(式4)

將式2替代進(jìn)式4得：

R²*S'_m=rn*(M(x)*G(x)+C_reg)+R²*B_n

=(rⁿ*M(x)*G(x))+rⁿ*C_reg+R²*B_n??????????(式5)

令C_H表示C_reg的高n位，C_L表示C_reg低(16-n)位，

C_reg=r^(16-n)*C_H+C_L?????????????????????????????(式6)

將式6代入式5得：

R²*S'_m=(rⁿ*M(x)*G(x))+R²*C_H+rⁿ*C_L+R²*B_n?????????(式7)

=(rⁿ*M(x)*G(x))+R²*(C_H+B_n)+rⁿ*C_L

由CRC定義知：(rⁿ*M(x)*G(x))Mod(G(x))≡0????????????????(式8)

(R2*(CH+Bn))Mod(G(x))=CRCCH+Bn=Crc16_Table[CH+Bn]]]>

(rn*CL)Mod(G(x))=rn*CL]]>

由邏輯抑或操作的結(jié)合性，式7以及式8得：

(R²*S'_m)Mod(G(x))=Crc16_Table[C_H+B_n]+rⁿ*C_L????????????(式9)

即：

CRCSm′=Crc16_Table[(CH+Bn)]+rn*CL.]]>????????????????????(式10)

S3：由式10可知，計算當(dāng)前數(shù)據(jù)的CRC16分兩步完成，具體步驟如下；

S301:將上一字節(jié)的CRC16值的高n位C_H和B_n相異或，異或結(jié)果作為下標(biāo)查表得到Crc16_Table[(C_H+B_n)]；

S302:將上一字節(jié)的CRC16的低（16-n）位左移n位后與查表值Crc16_Table[(C_H+B_n)]相異或。

S4：計算任意長度字節(jié)的CRC16，其包括以下步驟：

S401：取數(shù)據(jù)流的第一字節(jié)S₀作為下標(biāo)查表Crc16_Table[S₀]得到S₀的當(dāng)前CRC16值；

S402：按照順序?qū)⑺锌梢园醋止?jié)處理的部分按照字節(jié)完成CRC16計算；

S403:取n為剩余數(shù)據(jù)的實際比特數(shù)代入式10，完成剩余不足字節(jié)部分CRC16的計算；

S404：結(jié)合S401、S402和S403得到的當(dāng)前CRC16值、按照字節(jié)計算的CRC結(jié)果和不足字節(jié)部分CRC結(jié)果得到整個數(shù)據(jù)的CRC16結(jié)果。