关于CRC的文章不胜枚举，在此，由于笔者能力有限不予置评，但笔者认为，若想彻底地了解并灵活地运用CRC，必须从物理现象出发，然后推导出其数学表达式，最后再讨论其软件实现的方法。在阅读本文之前希望大家建立一个宏观的概念：CRC如同一个比特数据流的加工厂，即每一比特的数据经过CRC处理后，将生成一个新的CRC运算结果，该运算结果又参与下一比特数据的CRC运算。
物 理 现 象透过现象看本质，是琢磨问题的重要思想，琢磨CRC当然亦是如此。欲了解CRC的物理现象，必须明确CRC的硬件模型，即硬件是如何实现CRC运算的。CRC是由移位寄存器与异或单元组合而成，至于二者如何组合都只是一种约定而已。从CRC的硬件模型可知，一旦数据流中一个比特数据发生变化，后续的运算将全部受到影响，这在下文分析过程的表格中会有非常直观的体现，也是CRC的灵魂所在，即牵一发而动全身。当然，任何一种校验，都无法保证百分之百可靠，毕竟校验都是通过一个指定位宽的数据作为判定正确与否的依据。
由于二进制是分析CRC最直观的形式，下文数据若无特殊修饰，均为二进制表示形式，不添加二进制的修饰符。CRC-4/GICREN的生成多项式为X^4+X+1，二进制表示形式为1 0011，其硬件模型为图1-1。CRC-16/GICREN的生成多项式为X^16+X^15+X^2+1，二进制表示形式为1 1000 0000 0000 0101，其硬件模型为图1-2。
图1-1
图1-2
为便于分析，接下来仅以CRC-4/GICREN的硬件模型剖析CRC的物理现象。假设即将输入CRC-4/GICREN的比特数据为X，当前CRC的运算结果为ABCD以及X ^ A = E，注意：A、B、C、D、E及X均为二进制数，通过上述的硬件模型可得新的CRC运算结果。为便于表达，采用表格形式体现整个运算及变换的过程，如表1-1：
表1-1
用文字描述上述等效模型为：
若输入的比特数据与原CRC运算结果中最高位的异或值为1，新的CRC运算结果等于原CRC运算结果左移1位再按位异或0011。
若输入的比特数据与原CRC运算结果中最高位的异或值为0，新的CRC运算结果等于原CRC运算结果左移1位再按位异或0000。
接下来用一段具体的比特数据流来观察CRC-4/GICREN的运算过程，如表1-2，数据流为10101110，CRC初值为1111。其表现形式与实际等效硬件模型的区别在于：全部保留每次移出的最高位，同时并未直接计算出每一时刻CRC的运算结果。这种完全展开的方式，便于横向与纵向直观地了解CRC的运算机理，同时也为下文逐渐引出的经典计算方法埋下伏笔。欲求某一时刻CRC某位的运算结果，只需将该位所在的列在该时刻及以上除输入的源数据外的所有比特数据相异或即可，如第4个比特数据进入CRC-4/GICREN时，第4个比特数据与原CRC运算结果中的最高位的异或值 = 0 ^ = 1，其中括号内的异或结果为原CRC运算结果中的最高位，此时运算结果为1，因此第4位输入时的00EE值为0011，其余不再赘述。
表1-2
数学表达式在介绍CRC数学表达式之前，先介绍一种运算方法：模二运算，即一种二进制取模运算。应注意这种取模运算跟转换为十进制后的取模运算是完全不同的，也不是对2取模，这是一种人为定义的特殊运算。它与四则运算相同，亦包含加、减、乘及除，但区别在于模二运算不用进位与借位，仅根据待运算的两个位即可确定运算结果，不受前一次运算的影响，也不会对下一次运算造成影响。
模二加：1＋1=00＋0=01＋0=10＋1=1
模二减：1－1=00－0=01－0=10－1=1
模二乘：1×1=1 0×0=01×0=0 0×1=0
模二除：0÷1=0 1÷1=1
从CRC运算的硬件模型易知，每处理一位数据，需两次异或及一次移位，这是微观的视角。而数学表达式的建立，是从宏观的视角，以最终结果的准确性为准则，过程不求与硬件模型完全一致，对CRC的运算机理进行等效建模，揭开其内在的数学本质，为进一步的研究提供理论基础。
目前为止，仍然难以发现如何将CRC的运算过程与数学理论进行结合。只知道表1-2所展现的方法不便于软件的实现，因为求解CRC的运算结果，不仅需两次异或及一次移位，还需追溯历史数据。既然如此，可以尝试先从软件的高效性出发，以最终结果的准确性为准则，试图去探究其中的数学本质。这种逻辑应该是科学的，笔者还有一个大胆的的猜想：CRC校验的发明者，一开始应该只是想设计一种牵一发而动全身的校验方法，于是设计了类似上述的硬件模型，在软件实现的过程中建立了数学理论，最后通过数学理论进一步优化了硬件模型及软件实现的方法。笔者的这一猜想，贯串着整篇文章。
既然表1-2所展现的方法需追溯历史数据，因此可以将需追溯历史数据的运算提前进行，力求从当前步骤的运算结果中即可得知下一步骤需进行的运算，将表1-2进行简单的等效后即可得到表1-3，经过简单等效后的表1-3有一种似曾相识的感觉，与除法竖式中的一部分极其相似，同时从当前步骤的运算结果中的最高有效位即可得知下一步骤需进行的运算，并将异或减少为一次多位同时进行的异或，这更加符合实际软件的处理。接下来，结合上述模二运算法则对表1-3做进一步的等效得到表1-4。
表1-3
表1-4
至此，表1-4已形象地印证了CRC运算的数学本质是除法取余，同时也印证了前文提到的最高位多一个“1”是出于数学表达需要的观点。但笔者认为，这个除法并不是真正意义上的除法，因为添加了人为设定的前提条件，如模二运算。不过，数学本身也不完全是纯粹直接地用于揭示事物本质的，有时也可以是一种工具，如矩阵。
上述皆是通过表格的形式进行描述，接下来通过数学符号进行表达。在代数编码理论中，将一组信息码表示为一个多项式，码组中各码元作为多项式的系数，如 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表示源数据流对应的多项式，G表示生成多项式，I表示系数为CRC初值的多项式，D表示被除数多项式。根据代数编码理论中的表示法及表1-4的分析结果可知，CRC的运算结果等于D除G的余数，应注意所有运算均须遵循模二运算法则。为简化数学表达方式，下文笔者用MOD2各项系数/ G各项系数)来表示D对G模二取余的过程，上述的例子即可表示为：MOD2 / 10011)。
软 件 实 现码1-1
表1-4所述的经典计算方法用C语言实现的参考代码为码1-1，代码实现的过程与表1-4所述的方法略微有些不同，但完全等效。源数据流后补0的操作通过程序中的移位实现，虽移动了8位，多补了4个0，但CRC的初值放在一个字节的高4位，等效于表1-4中C0列的右侧补上4列全为0的列，对实际的有效位没有影响。
经典计算方法虽然对硬件模型进行等效简化，但仍是一种基于位判别的方法，一次仅处理一个位。然而从实际应用的角度出发，希望一次能处理多个位，这将会极大程度地提升软件的效率，就是下文着重阐述的查表法。至于一次处理几个位根据实际情况自行设定，且与CRC位宽无关，仅是软件上时间复杂度与空间复杂度权衡以及与实际应用相结合的问题。例如上述的例子，可以2位为一个数据块，抑或先以3位为一个数据块再以2位为一个数据块。接下来将上述的例子分3位和5位两个数据块进行处理，分析数据块小于或大于CRC位宽的情况，以便洞察查表法的本质。
先处理前3位数据101，此时CRC的初值为1111，根据经典计算方法及模二运算法则，可得处理完前3位数据后的CRC终值为1110。再处理后5位数据01110，注意此时的CRC初值是处理完前3位后的余数，即1110，可得处理完后5位的CRC终值为0011。仔细观察式1-1与式1-2发现，倘若事先将指定位宽所有可能的源数据对10011模二取余，并按源数据数值的大小顺序建立一个表格，便可通过查表的方式快速获取模二取余的结果，这就是查表法中表的由来。
式1-1
式1-2
表1-5
表1-6
根据查表法可将码1-1转化为码1-3。由于示例中一次校验一个字节的数据，一次处理的数据大于CRC的位宽，因此码1-3展现的是式1-2的过程，下文将在码1-6中展现式1-1的情况。对于码1-3与码1-6中的表格，无需手工计算，可通过程序自动生成，请参考码1-2与码1-5。
码1-2
码1-3
码1-4
码1-5
码1-6
为确保整个分析过程的严谨性，接下来对式1-1中的分解过程进行正确性证明。倘若仅需证明两式相等，其实从表1-2便可得出结论，当源数据流的宽度小于CRC位宽时，只有与源数据流宽度相等的那部分CRC初值参与00EE的生成。同时在分析表1-2时也提到，欲求某一时刻CRC某位的运算结果，只需将该位所在的列在该时刻及以上除输入的源数据外的所有比特数据相异或即可。由于生成的00EE均未发生变化，因此证明式1-1中的分解过程，其实就是证明：X1 ^ X2 ^ X3 ^ … ^ XN = ^ X1""
根据异或运算法则的结合律可得： ^ X1"" = ^ X2 ^ X3 ^ … ^ XN = X1 ^ X2 ^ X3 ^ … ^ XN。
式1-1中的分解形式仅是为查表法而构造的一种特殊分解形式，笔者发现，这种分解存在客观普遍性，即MOD2 / Z) = MOD2 + MOD2。笔者通过穷举法证明了其正确性，但目前未想到其它合理的证明方法，待后续补充，若有读者证明出来，期待可以与笔者分享。
附 言实际应用可能与上述有些差别，笔者写这篇文章，旨在帮助大家从根本上了解CRC的机理，对知识点有透彻的了解，做到知其然并真正知其所以然，应用是千变万化的，惟有内心的通透，才能游刃而有余。当然，笔者的水平也是有限，若有不妥的描述，请读者朋友批评指正。
