循环冗余校验（CRC）和FPGA实现_fpga crc4校验

1.简介

循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用模二除法及余数的原理来作错误侦测的。
在计算机网络通信中运用CRC校验时相对于其他校验方法就有一定的优势。CRC可以高比例的纠正信息传输过程中的错误，可以在极短的时间内完成数据校验码的计算，并迅速完成纠错过程，通过数据包自动重发的方式使得计算机的通信速度大幅提高，对通信效率和安全提供了保障。由于 CRC 算法检验的检错能力极强，且检测成本较低，因此在对于编码器和电路的检测中使用较为广泛。从检错的正确率与速度、成本等方面，都比奇偶校验等校验方式具有优势。因而，CRC 成为计算机信息通信领域最为普遍的校验方式。
CRC校验公式如下：

2.模二运算

先讲CRC编码的原理——模二运算

• 模二加法
  模2加法的规则是：0+0=0；1+1=0；0+1=1；1+0=1；（相同为0.相异为1）

• 模二减法
  模2减法的规则是：0-0=0；1-1=0；0-1=1；1-0=1； （相同为0.相异为1）
  模二加法和模二减法运算结果相同，可用异或逻辑实现

• 模二乘法
  模2乘法的规则是：0×0=0； 0×1=0；1×0=0；1×1=1； （有0结果0，与普通四则运算里的乘法一样）
  1001*1101的运算如下所示：
  

• 模二除法
  直接看例子，1111000÷1101
  

  模2除法具有下列三个性质：

1、当最后余数的位数小于除数位数时，除法停止。

2、当被除数的位数小于除数位数时，则商数为0，被除数就是余数。

3、只要被除数或部分余数的位数与除数一样多，且最高位为1，不管其他位是什么数，皆可商1。

3.生成多项式

多项式和二进制数有直接对应关系。如生成多项式为G(x)=x^4+x3+x+1， 可转换为二进制数码11011。生成多项式是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。
在发送方，利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
应满足以下条件：
a、生成多项式的最高位和最低位必须为1。
b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。
c、不同位发生错误时，应该使余数不同。
d、对余数继续做除，应使余数循环。
e、CRC校验码位数 = 生成多项式位数 - 1。

4.CRC算法

CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数模二除以另一个数。得到的余数作为校验数据附加到原数据后面。

实际应用时，发送方和接收方按以下方式通信：

1. 发送方和接收方在通信前，约定好一个预设整数作为除数。
2. 发送方在发送前根据原始数据和约定好的除数进行模二除法运算生成余数（即CRC码），然后将其附加到原始数据后面一起发送给接收方。
3. 接收方收到后将其模二除以约定好的除数，当且仅当余数为0时接收方认为没有差错。

example
1.信息字段：1011001;
2.选取生成多项式：CRC-4, 11001;（实际上就是除数）
3.对应的被除数代码： 10110010000；(低位补零，个数为生成多项式的阶数)
4.传输字段为：1011001|1010 （信息字段|检验字段） 需要注意，检验字段（余数）需要和生成多项式的阶数相同，如果余数位数少，需要在前面补零。

5.接收方采用传输字段除以相同的生成码CRC-4: 11001，即10110011010 / 11001 ,所得结果余数为0，证明传输正确。

5.常用CRC版本

6.FPGA实现

串行CRC
原理
参考博客https://blog.csdn.net/qq_42446721/article/details/127054205
LFSR实现上文例子CRC-4电路结构如下：

并行CRC
原理见论文http://outputlogic.com/?p=158
同时，有现成的工具可以生成并行CRC代码http://crctool.easics.be/

参考博客：https://blog.csdn.net/weixin_44256803/article/details/105805628