关于CRC的文章不胜枚举，在此，由于笔者能力有限不予置评，但笔者认为，若想彻底地了解并灵活地运用CRC，必须从物理现象出发（毕竟，认知一个新的事物往往始于它的现象），然后推导出其数学表达式，最后再讨论其软件实现的方法。在阅读本文之前希望大家建立一个宏观的概念：CRC如同一个比特（bit）数据流的加工厂，即每一比特的数据经过CRC处理后，将生成一个新的CRC运算结果，该运算结果又参与下一比特数据的CRC运算。
透过现象看本质，是琢磨问题的重要思想，琢磨CRC当然亦是如此。欲了解CRC的物理现象，必须明确CRC的硬件模型，即硬件是如何实现CRC运算的。CRC是由移位寄存器与异或单元组合而成，至于二者如何组合都只是一种约定而已（笔者认为，CRC水域最深的地方莫过于生成多项式的定义，该部分已超乎笔者能力，不予详述，本文笔者仅结合GICREN目前使用的生成多项式进行说阐述）。从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
图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-4/GICREN生成多项式系数10011的简式，至于完整的生成多项式系数最高位为何多一个“1”，这是出于数学表达的需要，同时探究异或与移位的组合运算如何与数学中的除法建立联系，都将在下文提及）。
若输入的比特数据与原CRC运算结果中最高位的异或值为0，新的CRC运算结果等于原CRC运算结果左移1位再按位异或0000。
接下来用一段具体的比特数据流来观察CRC-4/GICREN的运算过程（本文所讨论的CRC运算不涉及任何数据转置的处理，有些文章称之为“反射”，对于待校验的数据而言，从MSB即最高有效位开始进行CRC运算，不论采用那种方式，其本质均相同），如表1-2，数据流为10101110，CRC初值为1111（注意：若从软件实现的角度讨论，该值理论上可以是任意值，但结合硬件的需求，通常取各位全为0或1，因为移位寄存器是由触发器构成，统一初始状态便于硬件设计）。其表现形式与实际等效硬件模型的区别在于：全部保留每次移出的最高位，同时并未直接计算出每一时刻CRC的运算结果。这种完全展开的方式，便于横向与纵向直观地了解CRC的运算机理，同时也为下文逐渐引出的经典计算方法埋下伏笔。欲求某一时刻CRC某位的运算结果，只需将该位所在的列在该时刻及以上除输入的源数据外的所有比特数据相异或即可（背景色为灰色的未填数据为0，即左移后补进的位，这样操作以便观察CRC的实际有效位，同时背景色为白色的未填数据也为0），如第4个比特数据（即0）进入CRC-4/GICREN时，第4个比特数据与原CRC运算结果中的最高位的异或值 = 0 ^ (1 ^ 0 ^ 0 ^ 0) = 1，其中括号内的异或结果为原CRC运算结果中的最高位，此时运算结果为1，因此第4位输入时的00EE值为0011，其余不再赘述。
表1-2
在介绍CRC数学表达式之前，先介绍一种运算方法：模二运算，即一种二进制取模运算。应注意这种取模运算跟转换为十进制后的取模运算是完全不同的，也不是对2取模，这是一种人为定义的特殊运算。它与四则运算相同，亦包含加、减、乘及除，但区别在于模二运算不用进位与借位，仅根据待运算的两个位即可确定运算结果，不受前一次运算的影响，也不会对下一次运算造成影响。
模二加： 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
从CRC运算的硬件模型易知，每处理一位数据，需两次异或（一次异或0011或0000，另一次将输入的比特数据与原CRC运算结果中最高位进行异或）及一次移位，这是微观的视角。而数学表达式的建立，是从宏观的视角，以最终结果的准确性为准则，过程不求与硬件模型完全一致，对CRC的运算机理进行等效建模，揭开其内在的数学本质，为进一步的研究提供理论基础。
目前为止，仍然难以发现如何将CRC的运算过程与数学理论进行结合。只知道表1-2所展现的方法不便于软件的实现，因为求解CRC的运算结果，不仅需两次异或及一次移位，还需追溯历史数据。既然如此，可以尝试先从软件的高效性出发（尽可能地减少运算及避开历史数据的追溯），以最终结果的准确性为准则，试图去探究其中的数学本质。这种逻辑应该是科学的，笔者还有一个大胆的的猜想：CRC校验的发明者，一开始应该只是想设计一种牵一发而动全身的校验方法，于是设计了类似上述的硬件模型，在软件实现的过程中建立了数学理论，最后通过数学理论进一步优化了硬件模型及软件实现的方法。笔者的这一猜想，贯串着整篇文章。
既然表1-2所展现的方法需追溯历史数据，因此可以将需追溯历史数据的运算提前进行，力求从当前步骤的运算结果中即可得知下一步骤需进行的运算，将表1-2进行简单的等效后即可得到表1-3（其中红色字体部分的数据即表1-2中输入的比特数据与原CRC运算结果中最高位相异或的结果，Y为运算过程的中间量，未填数据为0），经过简单等效后的表1-3有一种似曾相识的感觉，与除法竖式中的一部分极其相似，同时从当前步骤的运算结果中的最高有效位即可得知下一步骤需进行的运算，并将异或减少为一次多位同时进行的异或，这更加符合实际软件的处理（单指令即可完成多位异或）。接下来，结合上述模二运算法则（异或运算亦等效于模二加或模二减）对表1-3做进一步的等效得到表1-4（背景色为黄色的数据是人为添加的，其中一个为商，一个为除数，未填数据为0）。
表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(x)表示源数据流对应的多项式（阶数为m-1），G(x)表示生成多项式（即除数，阶数为n），I(x)表示系数为CRC初值的多项式（阶数为n-1），D(x)表示被除数多项式（= X^n · F(x) + X^m · I(x)，此处的"^"为幂符号，可形象地描述为：X^n · F(x)表示在源数据流后补n个0，X^m · I(x)表示在CRC初值后补m个0，这与表1-4运算过程完全一致，即表1-4中的Y0）。根据代数编码理论中的表示法及表1-4的分析结果可知，CRC的运算结果等于D(x)除G(x)的余数，应注意所有运算均须遵循模二运算法则。为简化数学表达方式，下文笔者用MOD2(D(x)各项系数/ G(x)各项系数)来表示D(x)对G(x)模二取余的过程，上述的例子即可表示为：MOD2((10101110 0000 + 1111 00000000) / 10011)。
码1-1（CRC-4/GICREN经典计算方法）
表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（式1-1）。再处理后5位数据01110，注意此时的CRC初值是处理完前3位后的余数，即1110，可得处理完后5位的CRC终值为0011（式 1-2）。仔细观察式1-1与式1-2发现，倘若事先将指定位宽所有可能的源数据（如式1-1中背景色为白色模二运算中的源数据"010"，式1-2中背景色为白色模二运算中的源数据"10010"）对10011模二取余，并按源数据数值的大小顺序建立一个表格（如表1-5，表1-6），便可通过查表的方式快速获取模二取余的结果，这就是查表法中表的由来。
式1-1
式1-2
表1-5
表1-6
根据查表法可将码1-1转化为码1-3。由于示例中一次校验一个字节的数据，一次处理的数据大于CRC的位宽，因此码1-3展现的是式1-2的过程，下文将在码1-6中展现式1-1（一次处理的数据小于CRC位宽）的情况。对于码1-3与码1-6中的表格，无需手工计算，可通过程序自动生成，请参考码1-2与码1-5（仅需将0~255输入函数中，即可得到相应的数组，笔者未提供输出的代码，因不同平台操作方式不同）。
码1-2（CRC-4/GICREN查表法之表的生成）
码1-3（CRC-4/GICREN查表法）
码1-4（CRC-16/GICREN经典计算方法）
码1-5（CRC-16/GICREN查表法之表的生成）
码1-6（CRC-16/GICREN查表法）
为确保整个分析过程的严谨性，接下来对式1-1中的分解过程（背景色为绿色的部分）进行正确性证明。倘若仅需证明两式相等，其实从表1-2便可得出结论，当源数据流的宽度小于CRC位宽时，只有与源数据流宽度相等的那部分CRC初值参与00EE的生成。同时在分析表1-2时也提到，欲求某一时刻CRC某位的运算结果，只需将该位所在的列在该时刻及以上除输入的源数据外的所有比特数据相异或即可。由于生成的00EE均未发生变化，因此证明式1-1中的分解过程，其实就是证明：X1 ^ X2 ^ X3 ^ … ^ XN = (X1' ^ X2 ^ X3 ^ … ^ XN) ^ X1''（其中X1 = X1' ^ X1''，X2 ~ XN为生成的00EE）
根据异或运算法则的结合律可得：(X1' ^ X2 ^ X3 ^ … ^ XN) ^ X1'' = (X1' ^ X1'') ^ X2 ^ X3 ^ … ^ XN = X1 ^ X2 ^ X3 ^ … ^ XN。
式1-1中的分解形式仅是为查表法而构造的一种特殊分解形式，笔者发现，这种分解存在客观普遍性，即MOD2((X + Y) / Z) = MOD2(X / Z) + MOD2(Y / Z)。笔者通过穷举法证明了其正确性，但目前未想到其它合理的证明方法，待后续补充，若有读者证明出来，期待可以与笔者分享。
实际应用可能与上述有些差别，笔者写这篇文章，旨在帮助大家从根本上了解CRC的机理，对知识点有透彻的了解，做到知其然并真正知其所以然，应用是千变万化的，惟有内心的通透，才能游刃而有余。当然，笔者的水平也是有限，若有不妥的描述，请读者朋友批评指正。
联系客服
