【強烈建議在PC端查看本文，否則將無法顯示完整的排版格式】
（版權(quán)說明：基啟人|Gicren保留所有權(quán)利，允許轉(zhuǎn)發(fā)本文鏈接，禁止轉(zhuǎn)載本文內(nèi)容）
概述
關(guān)于CRC的文章數(shù)不勝數(shù)，在此，由于筆者能力有限不予置評，但筆者認(rèn)為，若想徹底地了解并靈活地應(yīng)用CRC，必須從物理現(xiàn)象出發(fā)（畢竟，認(rèn)知一個新的事物往往始于它的現(xiàn)象），再推導(dǎo)出其數(shù)學(xué)表達(dá)式，最后再討論其軟件實現(xiàn)的方法。在閱讀本文之前希望大家建立一個宏觀的概念：CRC如同一個比特（bit）數(shù)據(jù)流的加工廠，即每一比特的數(shù)據(jù)經(jīng)過CRC處理后，將生成一個新的CRC運算結(jié)果，該運算結(jié)果又參與下一比特數(shù)據(jù)的CRC運算。
物理現(xiàn)象
透過現(xiàn)象看本質(zhì)，是琢磨問題的重要思想，琢磨CRC當(dāng)然亦是如此。欲了解CRC的物理現(xiàn)象，必須明確CRC的硬件模型，即硬件是如何實現(xiàn)CRC運算的。CRC是由移位寄存器與異或單元組合而成（一旦數(shù)據(jù)流中一個比特數(shù)據(jù)發(fā)生變化，后續(xù)的運算全部受到影響，這將在下文分析過程的表格中會有非常直觀的體現(xiàn)。當(dāng)然，任何一種校驗，都無法保證百分之百可靠，畢竟校驗都是通過一個指定位寬的數(shù)據(jù)作為判定正確與否的依據(jù)），至于二者如何組合都只是一種約定而已（筆者認(rèn)為，CRC水域最深的地方莫過于生成多項式的定義，該部分已超乎筆者能力，不予詳述）。
由于二進制是分析CRC最直觀的形式，下文數(shù)據(jù)若無特殊修飾，均為二進制表示形式，不添加二進制的修飾符（如1011，即表示1011B）。CRC-4/GICREN的生成多項式為X^4+X+1（此處的"^"為冪符號，該式等于1*X^4+0*X^3+0*X^2+1*X^1+1*X^0，為數(shù)學(xué)角度的表現(xiàn)形式，將在下文的數(shù)學(xué)表達(dá)式中提及），二進制表示形式為1 0011（即，取各項系數(shù)），其硬件模型如圖1-1。CRC-16/GICREN的生成多項式為X^16+X^15+X^2+1（此處的"^"為冪符號），二進制表示形式為1 1000 0000 0000 0101，其硬件模型如圖1-2。
圖 1-1
psb.jpg (20.36 KB, 下載次數(shù): 79)
下載附件
2017-8-21 22:55 上傳
用文字表達(dá)上述等效模型為：
1.若輸入的比特數(shù)據(jù)與原CRC運算結(jié)果中最高位的異或值為1，新的CRC運算結(jié)果等于原CRC運算結(jié)果左移1位再按位異或0011（即CRC-4/GICREN生成多項式10011的簡式，至于完整的生成多項式最高位為何多一個“1”，這是出于數(shù)學(xué)表達(dá)的需要，將在下文提及）。
2.若輸入的比特數(shù)據(jù)與原CRC運算結(jié)果中最高位的異或值為0，新的CRC運算結(jié)果等于原CRC運算結(jié)果左移1位再按位異或0000。
接下來用一段具體的比特數(shù)據(jù)流來觀察CRC-4/GICREN的工作過程，數(shù)據(jù)流為10101110，CRC初值為1111（注意：若從軟件實現(xiàn)的角度討論，該值理論上可以是2^4（此處的"^"為冪符號）種取值中的任意值，但結(jié)合硬件的需求，通常取各位全為0或1，因為移位寄存器是由觸發(fā)器構(gòu)成，統(tǒng)一初始狀態(tài)便于硬件設(shè)計），如表1-2。其表現(xiàn)形式與實際等效硬件模型的區(qū)別在于：全部保留每次移出的最高位，同時并未直接計算出每一時刻CRC的運算結(jié)果。這種完全展開的方式，便于橫向與縱向直觀地了解CRC的工作機理，同時也為下文逐漸引出的經(jīng)典計算方法埋下伏筆。欲求某一時刻CRC某位的運算結(jié)果，只需將某列該時刻及以上所有背景色為灰色的比特數(shù)據(jù)相異或即可（未填數(shù)據(jù)的部分為0，即左移后補進的位），如第4個比特數(shù)據(jù)（即0）進入CRC-4/GICREN時，第4個比特數(shù)據(jù)與原CRC運算結(jié)果中的最高位的異或值 = 0 ^ (1 ^ 0 ^ 0 ^ 0) = 1（此處的"^"為異或符號），其余不再贅述。
表1-2
圖片
數(shù)學(xué)表達(dá)式
在介紹CRC數(shù)學(xué)表達(dá)式之前，先介紹一種二進制運算方法，即模二運算。它與四則運算相同，亦包含加、減、乘及除，但區(qū)別在于模二運算不用進位與借位，僅根據(jù)待運算的兩個位即可確定運算結(jié)果，不受前一次運算的影響，也不會對下一次運算造成影響。
模二加：1 ＋ 1 = 0 0 ＋ 0 = 0 1 ＋ 0 = 1 0 ＋ 1 = 1
模二減：1 － 1 = 0 0 － 0 = 0 1 － 0 = 1 0 － 1 = 1
模二乘：1 × 1 = 1 0 × 0 = 0 1 × 0 = 0 0 × 1 = 0
模二除：0 ÷ 1 = 0 1 ÷ 1 = 1
若將表1-2中的X0~X9均視為12位的數(shù)據(jù)（未填數(shù)據(jù)的部分均為0），同時在每項前面添加處理每一位數(shù)據(jù)時輸入的比特數(shù)據(jù)與原CRC運算結(jié)果中最高位的異或值，CRC終值亦等于X0~X9各列中的數(shù)據(jù)全部異或后再取其低4位（該結(jié)果與上述通過硬件模型得到的結(jié)果完全等效，因決定CRC終值的數(shù)據(jù)均未發(fā)生改變）。結(jié)合上述模二運算法則（異或運算亦等效于模二加或模二減），同時列出所有運算過程中的中間量Y，表1-2則等效于表1-3（即經(jīng)典計算方法）。仔細(xì)觀測表1-3，從Y0開始到運算結(jié)束，整個過程與除法的豎式完全一致，且除數(shù)為10011（即CRC-4/GICREN完整的生成多項式的二進制表示形式，同時印證了前文提到的最高位多一個“1”的觀點），最終得到的0011為Y0除10011的余數(shù)，即CRC運算終值。
細(xì)剖表1-1的結(jié)論，不難發(fā)現(xiàn)，每處理一位數(shù)據(jù)，需要兩次異或（一次異或0011或0000，另一次將輸入的比特數(shù)據(jù)與原CRC運算結(jié)果中最高位進行異或）及一次移位。然而，表1-3第一次進行多位異或，之后進行一次異或及一次移位即可，這更加符合實際軟硬件的處理，因為雖然從硬件角度，存儲數(shù)據(jù)的最小單元是位，但對數(shù)據(jù)的操作，一條指令便可實現(xiàn)多個位的同時操作。
表1-3
圖片
在代數(shù)編碼理論中，將一組信息碼（簡稱碼組）表示為一個多項式，碼組中各碼元作為多項式的系數(shù)，如 10101110 表示為1•X^7 + 0 • X^6 + 1 • X^5 + 0 • X^4 + 1 • X^3 + 1 • X^2 + 1 • X^1 + 0 • X^0（此處的"^"為冪符號），接下來用數(shù)學(xué)語言表達(dá)上述過程如下：設(shè)源數(shù)據(jù)流位寬為m，CRC的位寬為n，F(xiàn)(x)表示源數(shù)據(jù)流對應(yīng)的多項式（階數(shù)為m-1），G(x)表示生成多項式（即除數(shù)，階數(shù)為n），L(X)表示系數(shù)為CRC初值的多項式（階數(shù)為n-1），D(x)表示被除數(shù)多項式（= X^n • F(x) + X^m • L(x)，此處的"^"為冪符號）。根據(jù)代數(shù)編碼理論中的表示法及表1-3的分析結(jié)果可知，CRC的運算結(jié)果等于D(x)除G(x)的余數(shù)，應(yīng)注意所有運算均須遵循模二運算法則。
軟件實現(xiàn)（查表法）
經(jīng)典計算方法雖然減少了異或的次數(shù)，但仍是一種基于位判別的方法，一次僅處理一個位。然而從實際應(yīng)用的角度出發(fā)，我們希望一次可處理幾個位（即塊判別），這將會極大程度地提升軟件的效率。至于一次處理幾個位根據(jù)實際情況自行設(shè)定，且與CRC位寬無關(guān)，僅是軟件上時間復(fù)雜度與空間復(fù)雜度權(quán)衡的問題。例如上述的例子，可以2位為一個數(shù)據(jù)塊，抑或先以3位為一個數(shù)據(jù)塊再以2位為一個數(shù)據(jù)塊。接下來將上述的例子分3位和5位兩個數(shù)據(jù)塊進行處理，分析數(shù)據(jù)塊小于或大于CRC位寬的情況，以便洞察查表法的本質(zhì)。
先處理前3位數(shù)據(jù)101，此時的CRC初值為1111，根據(jù)經(jīng)典計算方法及模二運算法則可得：
圖片
再處理后5位數(shù)據(jù)01110，注意此時的CRC初值是處理完前3位后的余數(shù)，即1110。
圖片
由上述兩個過程可以發(fā)現(xiàn)，假設(shè)一次處理k位，其CRC運算結(jié)果等于這k位數(shù)據(jù)與CRC原值的異或（注意高位對齊，當(dāng)k大于CRC位寬時，應(yīng)在CRC原值后補k-4個0；當(dāng)k小于或等于CRC位寬時，僅取CRC原值的k位）再補四個0后對10011取余，該余數(shù)再與CRC原值左移k位后的值進行異或（注意移位時應(yīng)保持CRC位寬不變）。
由上述的分析可知查表法的表即預(yù)先計算出2^3種MOD(xxx0000/10011)及2^5種MOD(yyyyy0000/10011)的結(jié)果，如表1-4及表1-5（表中的待查數(shù)據(jù)僅顯示xxx及yyyyy）：
表1-4 表1-5
圖片
修正+補充中……
余下內(nèi)容詳見作者博客：
http://user.qzone.qq.com/2294515665/blog/1491534995
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
