循环冗余校验
循环冗余校验(英语:Cyclic redundancy check,通称“CRC”)是一种根据网上数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面,然后接收方进行检验确定数据是否发生变化。一般来说,循环冗余校验的值都是32位的整数。由于本函数易于用二进制的计算机硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误,因此获得广泛应用。此方法是由W. Wesley Peterson于1961年发表。
CRC为校验和的一种,是两个字节数据流采用二进制除法(没有进位,使用XOR来代替减法)相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示;除数是一个长度为的预定义(短)的二进制数,通常用多项式的系数来表示。在做除法之前,要在信息数据之后先加上个0.
CRC是基于有限域GF(2)(即除以2的同余)的多项式环。简单的来说,就是所有系数都为0或1(又叫做二进制)的多项式系数的集合,并且集合对于所有的代数操作都是封闭的。例如:
2会变成0,因为对系数的加法运算都会再取2的模数。乘法也是类似的:
我们同样可以对多项式作除法并且得到商和余数。例如,如果我们用x+x+x除以x+ 1。我们会得到:
也就是说:
等价于:
这里除法得到了商x^2+ 1和余数-1,因为是奇数所以最后一位是1。
字符串中的每一位其实就对应了这样类型的多项式的系数。为了得到CRC,我们首先将其乘以,这里n是一个固定多项式的阶数,然后再将其除以这个固定的多项式,余数的系数就是CRC。
在上面的等式中,表示了本来的信息位是111, 是所谓的钥匙,而余数1(也就是)就是CRC. key的最高次为1,所以我们将原来的信息乘上来得到,也可视为原来的信息位补1个零成为1110。
一般来说,其形式为:
这里M(x)是原始的信息多项式。K(x)是阶的“钥匙”多项式。表示了将原始信息后面加上个0。R(x)是余数多项式,即是CRC“校验和”。在通信中,发送者在原始的信息数据M后附加上n位的R(替换本来附加的0)再发送。接收者收到M和R后,检查是否能被整除(此处整除计算规则为模二运算)。如果是,那么接收者认为该信息是正确的。值得注意的是就是发送者所想要发送的数据。这个串又叫做codeword.
CRCs经常被叫做“校验和”,但是这样的说法严格来说并不是准确的,因为技术上来说,校验“和”是通过加法来计算的,而不是CRC这里的除法。
“错误纠正编码”(Error–Correcting Codes,简称ECC)常常和CRCs紧密相关,其语序纠正在传输过程中所产生的错误。这些编码方式常常和数学原理紧密相关。例如常见于通信或信息传递上BCH码、前向错误更正、Error detection and correction等。
//Module Name:CRC4_D11//Author Name:Yang Cheng Yu 杨成煜//Project Name:DSHOT600//UniversityNanJing University or Information Science & Technology//南京信息工程大学 电子与信息工程学院//Xi An University of Technology//西安理工大学 自动化与信息工程学院//DATE:/5/4//Describe://用于DSHOT600协议中,11位数据循环冗余码//的生成。其中包含3级流水线,数据输入有效//位置1后的第2个时钟周期CRC数据建立//module CRC4_D11(inputi_sys_clk,inputi_sys_rst_n,input[10:0]i_data,input[3:0]i_crc,outputreg[3:0]o_crc_new,inputi_valid,outputrego_valid);// polynomial: x^4 + x^3 + x^2 + x^1 + 1// data width: 11// convention: the first serial bit is D[10]reg[1:0]cnt_flow;//流水线计数器reg[10:0]r_data;reg[3:0]r_crc;reg[1:0]r_i_valid;wirew_i_valid_pedge;assign w_i_valid_pedge = r_i_valid[0]&(~r_i_valid[1]);always@(posedge i_sys_clk or negedge i_sys_rst_n)beginif(~i_sys_rst_n)r_i_valid <= 2'd0;elser_i_valid <= {r_i_valid[0],i_valid};endalways@(posedge i_sys_clk or negedge i_sys_rst_n)beginif(~i_sys_rst_n)begincnt_flow <= 2'd0;r_crc <= 4'd0;r_data <= 11'd0;o_crc_new <= 4'd0;o_valid <= 1'b0;endelse case(cnt_flow)2'd0:begino_valid <= 1'b0;if(w_i_valid_pedge==1'b1)begin//数据有效位,读取一帧数据cnt_flow <= cnt_flow + 1'b1;r_data <= i_data;r_crc <= i_crc;endend2'd1:begino_crc_new[0] <= r_data[10] ^ r_data[6] ^ r_data[5] ^ r_data[1] ^ r_data[0] ^ r_crc[3];o_crc_new[1] <= r_data[10] ^ r_data[7] ^ r_data[5] ^ r_data[2] ^ r_data[0] ^ r_crc[0] ^ r_crc[3];o_crc_new[2] <= r_data[10] ^ r_data[8] ^ r_data[5] ^ r_data[3] ^ r_data[0] ^ r_crc[1] ^ r_crc[3];o_crc_new[3] <= r_data[10] ^ r_data[9] ^ r_data[5] ^ r_data[4] ^ r_data[0] ^ r_crc[2] ^ r_crc[3];cnt_flow <= cnt_flow + 1'b1;end2'd2:begino_valid <= 1'b1;cnt_flow <= 2'd0;endendcaseendendmodule
简单测试文件
`timescale1ns/1ns//时间精度`define clock_period 20//时钟周期module tb_crc4_11;//实体名称//=====================<系统端口>=============================regi_sys_clk;regi_sys_rst_n;reg[10:0]i_data;reg[3:0]i_crc;wire[3:0]o_crc_new;regi_valid;wireo_valid;integeri;CRC4_D11 CRC4_D11_inst(.i_sys_clk(i_sys_clk),.i_sys_rst_n(i_sys_rst_n),.i_data(i_data),.i_crc(i_crc),.o_crc_new(o_crc_new),.i_valid(i_valid),.o_valid(o_valid));task crc_gen;input[10:0]data;begin#(`clock_period);i_data = data;i_crc = o_crc_new;#(`clock_period);i_valid = 1'b1;#(`clock_period);i_valid = 1'b0;#(`clock_period*10);endendtask//=====================<时钟信号>=============================initial begini_sys_clk = 1;forever#(`clock_period/2)i_sys_clk = ~i_sys_clk;end//=====================<复位信号>=============================initial begini_sys_rst_n = 0;#(`clock_period*20+1);i_sys_rst_n = 1;end//=====================<激励信号>=============================initial begini_data = 11'd0;i_crc = 4'd0;i_valid = 1'b0;i = 0;#(`clock_period*20+1);//初始化i_data = 11'd1456;for(i=0;i<10;i=i+1)begincrc_gen(i_data);#(`clock_period*2);endendendmodule