一文搞懂 CRC 的并行实现

✎ 编者按
关于 CRC 算法，在网上有不少网站支持填充 CRC 参数后自动生成 CRC 算法的并行 SystemVeriolg 代码实现。之前秉承着拿来主义，对其中的实现不求甚解。然而知其然，更要知其所以然，比如说想要实现一个多项式可配置的 rtl 电路该如何去做，这是线上网站是所不能解决的。

CRC 算法的串行实现

对于 crc 算法，其一般有一个多项式定义，以 CRC32 for 802.3 为例，其多项式定义为：

crc[31:0]=1+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32;

在实现 CRC 算法时，关于其串行实现，在网络上有不少的资料介绍。其实现基本以现行反馈移位寄存器 LSFR 来进行实现：

data_in 串行输入比特 m，多项式为 g，计算结果为 c，其计算方式为：

关于 CRC 算法的并行实现，感兴趣的读者可以去阅读 pdf《CRC 校验一探究竟》，这里不做过多展开。

CRC 算法并行实现

对于硬件电路设计，相比软件设计而言，其最大的变化无非是引入了时序的概念。这里先把时序的概念抛到一边，所谓并行实现，无非是将原本的计算逻辑压缩到一拍之中，采用空间换取时间的方式。这里以一个 CRC5 的计算来举例：

其实现逻辑无非是以组合逻辑的形式将 crc 的串行之行展开。那么对于一个多项式可配置的 CRC 算法，其串行实现的逻辑可以整理为如下的格式：

case class CrcCore(polynomial:Bits,init_value:Bits,data_in:Bool,result_value:Bits) extends Area {
  require(polynomial.getBitsWidth==init_value.getBitsWidth)
  require(polynomial.getBitsWidth==result_value.getBitsWidth)
  val data_in_xor=data_in ^ init_value.msb
  //bit 0 result
  result_value(0):=data_in_xor
  //the other bits
  for(index<- 1 until polynomial.getWidth){
    result_value(index):=(data_in_xor&& polynomial(index)) ^ init_value(index-1)
  }
}

这里面 polynomial 为多项式的系数，init_value 为初始值，data_in 为对应的输入数据(单比特)，result_value 为计算结果。

参照上面的 LSFR 电路可知，如果 g0 为 0，那么 CRC 是无法工作的。故对 result_value(0)直接进行 data_in_xor 赋值即可。而对于其他比特，按照 LSFR 电路进行赋值即可。

那么所谓的串行无非是将串行电路进行迭代。对于 N 比特输入，就将 N 轮循环进行展开：

case class CrcCal(dataWidth:Int,crcWidth:Int) extends Component{
  val io=new Bundle{
    val data_in=inBits(dataWidth bits)
    val crc_ploy=inBits(crcWidth bits)
    val crc_init=inBits(crcWidth bits)
    val crc_result=outBits(crcWidth bits)
  }
  noIoPrefix()
  val crc_tmp_result=Vec(Bits(crcWidth bits),dataWidth)
  for(index <- 0 until dataWidth) {
    val crc_core=CrcCore(polynomial = io.crc_ploy, init_value = if(index==0) io.crc_init else crc_tmp_result(index - 1), data_in = io.data_in(dataWidth - 1 - index), result_value = crc_tmp_result(index))
  }
  io.crc_result:=crc_tmp_result.last
}

对于指定的位宽 dataWidth，这里建立一个数组，crc_tmp_result 用于存储中间结果。对于 CrcCore，在进行调用时，对于第一轮迭代，init_value 为 crc 算法的初始值，对于其他轮，则采用上一轮计算的结果 crc_tmp_result(index-1)，而最终的计算结果，则为最后一轮 crc 计算值。

至此，一个支持多项式 crc_ploy、初始值 crc_init 可配置的电路即完成。

CRC 算法的串行实现

CRC 算法并行实现

相关参考

推荐阅读

目录