图解CRC校验码的逻辑电路实现

• 由需求驱动

平时在软件领域能知道CRC的原理和用途，但不会考察其实现细节，能保证用对即可，需求是快速交付。可以在很多地方找到可拆卸的独立CRC代码模块，拿过来直接用就行了。

软件领域对CRC的计算分为2种，查表法和计算法，查表法其实是计算法得到的所有可能结果存成表，所有可能的数据就是表的下标。当计算数据来了，用计算数据当作下标取得表中的结果即可，省掉了计算时间，但多耗费了一个表大小的内存。一般数据都是按字节粒度来的，所以表的大小是2^8=256个表项。

现在需要用FPGA做一个项目定制的MAC控制器，实现标准以太网帧的CRC32，当然可以用多周期的方式模仿软件计算的算法，用FPGA时序逻辑实现得到同样结果，但是MAC是通信控制器，在以太网帧开始发送的时候就要随着数据流一起计算，数据流结束后立即无缝地附加CRC码发送出去，这里的时钟是和数据流是同步的，一个时钟节拍一小节数据流，每发送一小节数据，时序逻辑只有一个时钟节拍可用，模仿软件的方式是无解的。

必须使用实时在线的组合逻辑，即直接搭接门电路来实现。在网上能找到的verilog代码思路差异较大，直接拿过来用都不太合适，需要彻底弄清楚所有细节来自己定制一个。网上介绍原理和实现的文章有很多，要么太粗，难以作为参考实际落地，要么太数学，一大堆周旋的数学式子，实际使用门电路做落地实现的话，参考价值并不高。

其实在通信领域，很多编码和加密，都是设计为使用门电路实现的，包括像CRC这样的检错码。

 

• 原理讲解

循环冗余校验码CRC是一种检错码，基本原理是这样的：将需要校验的原数据，除以一个约定的常量值，得到一个余数，这个余数就是校验码。

把原数据和这个校验码一起提供给使用方，然后使用方也对原数据进行相同的计算，除以相同的那个常量值，最后得到了相同的余数，即视为数据完好无损。因为是校验码是余数，使用方也可对包括校验码在内的所有数据进行计算，检查最终余数是否为0来判定数据的完好，效果是一样的。

除数的这个常量值就是实际标准中的多项式，

CRC-8: X^8 + X^2 + X^1 + X^0 = X^8 + X^2 + X + 1 = b100000111 = h107

CRC-12: X^12 + X^11 + X^3 + X^2 + X^1 + X^0 = b1100000001111 = h180F

CRC-CCITT: X^16 + X^12 + X^5 + X^0 = b10001000000100001 = h11021

CRC-32: X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 + X^7 + X^5 + X^4 + X^2 + X^1 + X^0 = b100000100110000010001110110110111 = h104C11DB7

实际的除计算采用二进制异或计算，不进行进位和借位。因为是二进制，所以余数的位数肯定不大于这个除数常量的位数。比如CRC-32的多项式除数（h104C11DB7）为33位，则计算余数最多32位，因此多项式的选取，比相应的校验码位数都多1位。

以CRC-8为例，计算形式可表示为：

最终的余数rrrrrrrr即为原数据关于CRC-8标准多项式的循环冗余校验码。其他位数较多的标准CRC多项式原理是相同的。原理清楚之后，接下来考虑如何使用逻辑电路实现。

• 落地实现

首先简化需求，为了样例讲解，假设原数据分多次到来，1次来1bit，来1次计算1次，则计算形式可表示为：

标绿色的bit为新到的原数据，标橙色的8bit为上次的计算余数结果，用异或逻辑门即可简单实现，得到计算结果后，将本次的计算结果替换至橙色区域等待下次新到来的数据即可。如果之前从未有数据来过，第1个bit新数据来时的情况标橙色的部分为什么值呢？这就是相关CRC标准里要求的初始化值的情况，比如CRC-32要求初始化为0xFFFFFFFF。

这里有个问题，异或门的输入数据根据商的不同会有所不同，比如本次商1则如图所示一致，如商0则标蓝的部分会全是0，商0或1只和最高位有关。另外，与0的异或相当于就是自己，所以可以简化掉一部分总是和0做异或的逻辑门。

经过调整，实际落地的计算形式和相应的verilog代码表示为：

然后考虑1次来4bit，来一次算一次的情况，可将4bit情况扩展表示为：


其他形式或位数的CRC多项式和每次来多个bit原数据的情况，原理是相同的。这里我们使用的是新来的数据从左向右推，也是小学就习惯的高低位做法，有的计算实现是从右向左推，这种情况下多项式是左右颠倒的，最终结果的效果是一样的。另外，有的CRC标准，如CRC-32要求最终的CRC结果再和0xFFFFFFFF做一次异或（也就是取反）。