IC君的第38篇原创文章

上一篇文章讲述了CRC 的数学原理和通项式选择，大家可以点击下面的链接阅读：

想知道数据传输的正确性？CRC算法来检查

这一篇文章聊一聊CRC算法的硬件电路实现：串行电路和并行电路。

下面的内容还是IC君的朋友文武写的，IC君稍微做了优化排版和少量的编辑工作提升大家的阅读体验。

1

 CRC硬件电路的实现很简单，下图给出教科书上任意生成多项式G(X)=gnXn+gn-1Xn-1+···+g1X+g0的电路结构：

为什么从右边输入data?

因为CRC是除余数，所以从右边输入数据，相当于把信息位data先左移位。

以简单的CRC8举例，多项式G(x)=X8 +X7 +X6 +X4 +X2 +1 的电路示意图如下：

对应的Verilog code代码如下：

上面的Verilog code上用了LFSR这种变量声明，有没有感到奇怪？

LFSR(线性移位寄存器)和CRC的算法很像的，有兴趣的可去看看LFSR的相关知识。

一位串行输入的CRC电路实现方法很简单，每周期的组合逻辑链路简单延时短。它的缺点是输入位宽只有一位，所以一个clock周期只能算一位，如果是64bit的信息位就要64个clock周期。如果需要传输的位数比较多，会对系统的性能产生比较大的影响。

假设要把输入位宽变成8位(byte)输入，电路将是什么样的呢？并行的CRC其实也简单，可以用提前抽取的概念来实现。

用下图来解释一下，CRCM有M个校验位就是有M个寄存器，现在把输入变成N位。

提前抽取就是通过关系函数得到下一个clock寄存器的输入nxt_crc[M-1:0]：

关系函数CN如下：

nxt_crc=CN(crc_out,data)，

crc_out是前一个clock的寄存器输出；

data是当前的输入数据；

函数CN就是一个组合逻辑网络，也可叫做所谓的scramble。怎样得出这个CN呢？如果数字信号处理学的好，可以去推导一下。网上有各种算法，很多很多。下面介绍一种方法。

2

以CRC8，G(x)=X8 +X7 +X6 +X4 +X2 +1为例子产生一个CRC8_8的CN，下面直接给出CRC8_8的Verilog code，后面讲怎么得到这个CN。

上面的Verilog code 的代码是由下面的矩阵得出的

把N_in作为数据，M_in作为CRC的上一个clock的值就有：

LFSR_S[0] =DATA[0]^DATA[1]^DATA[3]^DATA[6]^DATA[7]^LFSR_N[0]^LFSR_N[1]^LFSR_N[3]^LFSR_N[6]^LFSR_N[7];

怎么获得这个矩阵呢?

CRCM_N(M_in,N_in)= CRCM_N(M_in,0)+ CRCM_N(0,N_in)

可以用crc8_parallel(N_in)：输入data_in 的是8‘b00000001，得到crc8的值，就是H1的第一行8’hd5；输入data_in 的是8‘b00000010，得到crc8的值，就是H1的第二行8’h7f；以此类推。计算出上面矩阵H1=[]NxM。计算H2=[]MxM的方法和H1是一样的。

有上面的矩阵就有CN函数。有了CN就可很容易得出CRC硬件电路了。上面的方法其实可写成一个脚本，实现任意多项式任意位宽输入的并行CRC硬件电路。www.OutputLogic.com 有自动生成器，不过大家最好自己写一写。提醒：上面有LSB和MSB谁先输入到并行CRC里面去的问题？琢磨一下吧！

最后给出CRC8 ，G(x)=X8 +X7 +X6 +X4 +X2 +1的参考文献:

[1] A Practical Parallel CRC Generation Method, www.OutputLogic.com

[2] Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks ,Philip Koopman, Preprint: The International Conference on Dependable Systems and Networks, DSN-2004.

更多源代码可以在知识星球获得哦。

明天公众号可能要推一篇关于人工智能的广告，到时候感兴趣的同学可以点进去看一看，据说有一些免费课程。

广告费用于给IC君团队一些小小激励，激发大家的原创热情，也希望大家踊跃投稿(给稿费哦)，另外公众号以后也可以搞一些活动回馈给大家。

写一篇原创文章非常不容易，麻烦大家转发、分享、点“在看”哦，谢谢！

往期精彩回顾

想知道数据传输的正确性？CRC算法来检查

静态时序分析和动态时序分析的比较和转换

IC面试中常被问到——跨时钟域信号如何处理？