【强烈建议在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
| 
