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