CRC循环冗余校验 (Cyclic Redundancy Check) 原理/电路实现/Verilog实现

1 什么是CRC循环冗余校验？

循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。CRC有以下特性：

多项式表示：把所有二进制位字符串视为变量 (x) 的多项式方程；
多项式除法：使用“多项式除法” (模2算术运算) 进行校验；
在检测单bit和多bit错误时极其可靠；
可以简单地通过反馈移位寄存器和XOR门高效地实现。

2 CRC校验的原理

2.1 多项式表示

对如下二进制bit字符串：

可以将其表示为一个虚拟变量 (x) 的多项式方程 (二进制加权形式)：

例：字符串 (1100101) 可以表示为：

这样做的目的是，方便之后进行数学编码和对二进制数据串的操作 (如：模二运算)。

2.2 模二多项式除法

通常一个多项式B(x)除以另一个多项式G(x)会产生一个商多项式Q(x)和一个余数多项式R(x)：

由于模二减法=模二加法，上式可重写为：

$B(x)+R(x)=Q(x)\cdot G(x)$

这表明可以可以通过添加一个特定的二进制组合R(x)到原原数据串，来产生一个刚好能被多项式G(x)整除的新的多项式。

2.3 传输端

$T(x)=B(x)+R(x)=Q(x)\cdot G(x)$

2.4 接收端

$\frac{T'(x)}{G(x)}=Q(x)+R'(x)$

$where T'(x) = T(x) + E(x) and R'(x) = \frac{E(x)}{G(x)}$

T'(x) 是接收端的接收到的二进制bit串对应的多项式，E(x) 是错误的二进制bit构成的多项式。

如果余数多项式R'(x)=0，则表明接收到的数据没有错误。否则，在传输过程中存在单bit或多bit的错误，需要重新传输。G(x)为选定的能够检测出几乎所有单bit和多bit错（突发错误）误的生成多项式。

3 CRC码的产生

3.1 产生CRC码步骤

第一步：对r次的生成多项式 $G(x)=g_{r}x^{r}+g_{r-1}x^{r-1}+...+g_{1}x+g_{0}$ ，在原二进制bit串后方增加r个“0”，形成新的数据多项式B'(x)：

第二步：用B'(x)除以生成多项式G(x)，得到余数多项式R'(x)：

第三步：传输。此时，T(x) 等于 Q'(x)·R'(x) 且正好能被G(x)整除。

3.2 Verilog实现

module CRC_Gen(
input clk,
input rst_n,
input [7:0] data,
input data_valid,
output reg [15:0] crc
);
reg [23:0] temp;
parameter polynomial=17'b1_0001_0000_0010_0001;
always@(posedge clk or negedge rst_n)
begin
    if(~rst_n)
    begin
        crc <= 0;
        temp <= {data,16'd0}; //复位时，将初始数据放入寄存器
    end
    else if(data_valid)
    begin
        if(temp[23]) temp[23:7] <= temp[23:7]^polynomial;
        else if(temp[22]) temp[22:6] <= temp[22:6]^polynomial;
        else if(temp[21]) temp[21:5] <= temp[21:5]^polynomial;
        else if(temp[20]) temp[20:4] <= temp[20:4]^polynomial;
        else if(temp[19]) temp[19:3] <= temp[19:3]^polynomial;
        else if(temp[18]) temp[18:2] <= temp[18:2]^polynomial;
        else if(temp[17]) temp[17:1] <= temp[17:1]^polynomial;
        else if(temp[16]) temp[16:0] <= temp[16:0]^polynomial;
        else crc <= temp[15:0];
    end
end
endmodule

4 电路实现原理—线性反馈移位寄存器

4.1 循环移位寄存器结构

数据通寄存器循环，输出被反馈到输入。例：一个下图所示的4-bit移位寄存器初始载入0001，则可以得到四种不同的bit pattern，但这并不是所有可能的4-bit pattern（ $2_{}^{n}$ 种）。

4.2 最大长度移位寄存器

当XOR门（执行模二和运算）被加在反馈路径上时，可能得到的bit patterns的数量增加了。

最大长度移位寄存器定义为：一个在不同时钟下能产生 $(2_{}^{n}-1)$ 种bit patterns 的 n-bit 反馈移位寄存器。

最大长度寄存器对任意输入序列都拥有除法器的作用。其他任何不能产生最大序列的电路都不能执行除法操作。

例：如下图所示的最大序列产生器是一个含有XOR门的3-bit移位寄存器，假设起始值为001。

例：如上图所示（由移位寄存器和XOR门构成的除法器电路）（该电路表示的 $G(x)=x^{3}+x^{2}+1$ ）：使用最大序列移位寄存器结构，假设寄存器中初始值均为0并且有一个四位的输入(1110 MSB先入）。在四次移位后，留在寄存器R3 R2 R1中的bit pattern就是余数，可以看到在周期4，我们得到余数R(x) = 011(R3 R2 R1)。

验证得到的余数是否准确：

4.3 多项式除法电路（线性反馈移位寄存器）

$V(x)=v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+...+v_{1}x+v_{0}$

$G(x)=g_{r}x^{r}+g_{r-1}x^{r-1}+...+g_{1}x+g_{0}$

用下图电路执行 $\frac{V(x)}{G(x)}=Q(x)+\frac{R(x)}{G(x)}$ ：

可以看出，对一个n次多项式，最多使用n-1个移位寄存器和最多n-2个异或门可以构成一个线性移位寄存器。线性移位寄存器可以实现模二除法。

重新编排多项式后的编码电路如下，由于当移位开始时，输入可以直接在输出得到，这节省了k个Cycle的时间：

在开始的k次移位，开关打开 (选择下端)。k位信号bits同时移入寄存器和移到输出。
在之后的n-k次移位，开关关闭 (选择上端)。剩下的寄存器中的 (n-k)位check bit移动到输出。

4.4 Verilog实现

// CRC = x16+x12+x5+1
module CRC_GenSerial(
    input clk,
    input rst_n,
    output reg [15:0] crc
);
reg [31:0] data_parallel;
reg data_serial;
reg [5:0] cnt;
parameter source_data = 32'h96E32077;
always@(posedge clk or negedge rst_n)
begin
    if(~rst_n)
    begin
        cnt <= 0;
        data_parallel <= source_data;
        data_serial <= 0;
    end
    else if(cnt < 32)
	begin
		cnt <= cnt+1;
        data_serial <= data_parallel[31];
        data_parallel <= data_parallel<<1;
	end
	else
    begin
        cnt <= 33;
        data_serial <= 0;
        data_parallel <= 0;
    end
end
always@(posedge clk or negedge rst_n)
begin
    if(~rst_n)
    begin
        crc <= 0;
    end
    else if(cnt <= 32)
    begin
        crc[0] <= crc[15]^data_serial;
        crc[4:1] <= crc[3:0];
        crc[5] <= crc[4]^crc[15]^data_serial;
        crc[11:6] <= crc[10:5];
        crc[12] <= crc[11]^crc[15]^data_serial;
        crc[15:13] <= crc[14:12];
    end
    else
    begin
        crc <= crc;
    end
end
endmodule

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/80784.html