在了解CRC16之前，我们可以参观一下Koopman的网站，这位老师对CRC研究的非常深入，也通过网站的形式列举了他找到的比较好的二项式。当然CRC的长度越大，寻找的代价也就越高，这样是为什么库老师目前在CRC64附近就停住了，估计下一波要等到量子计算机上市了，：）
我们今天来研究一下CRC16。在网站的第一个Block，列举了不少CRC16的二项式，二项式的写法与我们之前介绍的还不太一样，例如在16列：
0x8d95
0xd175
0xac9a
等等
0x8d95也可以写成：
1 0001 1011 0010 1011b (需要在最后面补一个1b)
或：
X16+X12+X11+X9+X8+X5+X3+X+1
Note：
只有除数是17位的才能产生16位的CRC。
下面我们来了解一下CRC16的计算方法。假设我们准备传送Helo! (比Hello！少一个l节约原始数据长度)这一串字符。首先我们将字符通过ASCII编码转换成16进制的数：
Helo！
0x48 0x65 0x6C 0x6F 0x21
转换成二进制数：
0100 1000 0110 0101 0110 1100 0010 0001b
按照第一篇文章中介绍的长除我们将这一串二进制进行长除：
最后得到16-bit的CRC值：
1000 0010 1110 1011b
当发送端发送数据的时候，将原数据左移16位然后进行二进制长除，得到的16-bit CRC将代替原本左移后补0的16-bit位置。发送端将组合后的数据一起发送给接收端。这时候接收端可以直接对组合后的数据进行二进制长除，当然双方要约定好相同的二项式，即‘除数’。如果余数是0，说明数据和CRC很大可能没有出现反转。CRC一般都有一定的漏检概率，随着保护数据长度的增加而增加。如果余数不是0，那么说明组合后的数据一定有bit反转了。
接下来我们来看看如何设计一个电路来产生CRC16。我们再来观察一下二进制长除的过程，基本上就是二项式从左到右进行移动，当二进制最左侧的1和数据的1重合的时候，将数据中与二项式中对应1的位置进行反转。然后二项式继续向右运动，当再次遇到数据中的1的时候停下来，再将与二项式中1对齐的位置的数据bit进行反转，一直到二项式的最右侧bit与数据的最右侧bit重合的时候停止。这时候保留在数据最右侧的16-bit内容就是CRC16了。如下面动画所示：
整个过程中组合数据左向移动我们可以通过一个16-bit移位寄存器来模拟（关于线性移位寄存器的相关内容可以关注–手把手教你伪随机一文），如下面动画所示：
伴随Clock的跳动，组合数据中的数据bit会依次进入到整个16-bit移位寄存器中，直到组合数据的最右边bit进入Q0，我们停止Clock的跳动。
我们再回顾一下长除的过程，首先二项式有17位，而移位寄存器有16位。移位寄存器和除数二项式的关系如下图所示：
二进制长除在组合数据左移过程中，需要做以下操作：
- 当组合数据的bit从Q15管脚Q出来的时候是1b时，启动异或操作。
- 具体操作是将二项式中1所对应的组合数据位置进行反转。具体过程请参考前面的动画。
需要注意的是我们没有采用17位的寄存器主要是因为，Q15输出是1b的时候，再与二项式的最左边的1b进行异或，所得到的结果是0b，所以我们不需要记录该信息，因为永远这个第17bit处的操作结果都是0b。
因此，CRC16的整个操作流程如下：
- 组合数据需要按照Clock的上升沿进行持续左移
- 当Q15的Q管脚输出1b的时候启动整个二项式与16位寄存器间的异或操作
- 当Q15的Q管脚输出0b的时候不做异或操作，而只是按照clock进行左移
- 当组合数据的最后一个bit进入Q0的管脚D后，停止Clock
- 这时候存放在16位移位寄存器中的内容即CRC16结果
为了满足上述流程，我们可以利用Q15的管脚Q输出作为条件，来控制某个具体位置的异或操作。拿Q0来说，当Q15.Q是1b的时候，Q0.Q = Q0.D xor 1；当Q15.Q是0b的时候，Q0.Q = Q0.D xor 0。
实际上上面的逻辑与下面逻辑等效：
Q0.Q = Q0.D xor Q15.Q
整个电路的设计如下：
我们将Q15.Q作为异或门的一个输入，用来控制什么时候需要反转组合数据的bit。而在剩下二项式为1b的位置，我们放置一个异或门用来反转组合数据的bit。
整个过程将会和我们上面希望达成的操作一致：
-
所有移位寄存器中初始化0b
-
组合数据根据clock开始有节奏的一个bit，一个bit的进入Q0
-
这时，由于Q15.Q输出的还是0b，所以所有的异或门的上面的输入端都是0b，异或门的输出和异或门下面的输入端的值保持一致，即没有反转。
-
这个时候组合数据持续进入Q0，一直到组合数据中从左侧开始的第一个1b出现在Q15.Q的时候，所有的异或门开始反转组合数据相应位置的bit。
-
当Q15.Q是0b的时候，所有的异或门不反转组合数据的bit。
-
这样直到组合数据最后一个bit经过异或门进入Q0，clock停止，保留在Q15到Q1的管脚Q上的值即为CRC16的值。
下面是使用Python语言计算CRC16的代码：
def crc16_8d95(data=0x48656C6F21, debug=1):
“””
crc16_8d95 will help to calculate CRC16 based on original data
and the polynominal is 0x8d95
0x8d95 equals to 1 0001 1011 0010 1011b
input:
data – input data
“””
print ‘This is crc16_8d95 scripts’
crc_o = 16*[0]
crc16 = 16*[0]
#Add 16 zero on right:
data = data << 16
datain, bits = getbit(data, reverse = 1)
for i in range(bits):
crc16[15] = crc_o[14]
crc16[14] = crc_o[13]
crc16[13] = crc_o[12]
crc16[12] = crc_o[11] ^ crc_o[15]
crc16[11] = crc_o[10] ^ crc_o[15]
crc16[10] = crc_o[9]
crc16[9] = crc_o[8] ^ crc_o[15]
crc16[8] = crc_o[7] ^ crc_o[15]
crc16[7] = crc_o[6]
crc16[6] = crc_o[5]
crc16[5] = crc_o[4] ^ crc_o[15]
crc16[4] = crc_o[3]
crc16[3] = crc_o[2] ^ crc_o[15]
crc16[2] = crc_o[1]
crc16[1] = crc_o[0] ^ crc_o[15]
crc16[0] = datain[i] ^ crc_o[15]
crc_o[15] = crc16[15]
crc_o[14] = crc16[14]
crc_o[13] = crc16[13]
crc_o[12] = crc16[12]
crc_o[11] = crc16[11]
crc_o[10] = crc16[10]
crc_o[9] = crc16[9]
crc_o[8] = crc16[8]
crc_o[7] = crc16[7]
crc_o[6] = crc16[6]
crc_o[5] = crc16[5]
crc_o[4] = crc16[4]
crc_o[3] = crc16[3]
crc_o[2] = crc16[2]
crc_o[1] = crc16[1]
crc_o[0] = crc16[0]
if debug:
print “#%d —- “%i, crc_o
#put bit15 on left and bit0 on right
crc16.reverse()
return crc16
def getbit(data = 0, reverse = 0, debug = 0):
“””
getbit() will help to convert data to a bit list.
Inputs:
data : Input data (integer)
reverse : If reverse==1, then the most significant bit of data is output[0]
Outputs:
output : a list to store bit0 to bit(n-1)
data length in binary
“””
output = list()
#get data length in binary
datalen = len(bin(data))-2
for i in range(datalen):
output.append((data>>i) & 1)
if reverse:
output.reverse()
if debug:
print (output)
return output, datalen
下面是使用System Verilog语言实现CRC16的代码：
module crc16_8d95(
input clk,
input reset_b,
input datain
);
reg [15:0] Q;
integer counter;
always @(posedge clk) begin
if(!reset_b) begin
Q = 16’h0;
counter = 0;
end
else begin
if (counter <= 64) begin
Q[15] <= Q[14];
Q[14] <= Q[13];
Q[13] <= Q[12];
Q[12] <= Q[11] ^ Q[15];
Q[11] <= Q[10] ^ Q[15];
Q[10] <= Q[9] ;
Q[9] <= Q[8] ^ Q[15];
Q[8] <= Q[7] ^ Q[15];
Q[7] <= Q[6] ;
Q[6] <= Q[5] ;
Q[5] <= Q[4] ^ Q[15];
Q[4] <= Q[3] ;
Q[3] <= Q[2] ^ Q[15];
Q[2] <= Q[1] ;
Q[1] <= Q[0] ^ Q[15];
Q[0] <= datain ^ Q[15];
counter = counter + 1;
end
end
end
endmodule
测试用例：
`timescale 1ns/1ns
module crc16_8d95_tb();
reg clk;
reg reset_b;
reg datain;
reg [63:0] p_data;
integer i;
crc16_8d95 crc16_8d95(
.clk (clk),
.reset_b (reset_b),
.datain (datain)
);
//initial block
initial begin
reset_b = 0;
#50
reset_b = 1;
end
//clock generator
initial begin
clk = 0;
#5 forever #5 clk = !clk;
end
always @(negedge clk or negedge reset_b) begin
if (!reset_b) begin
datain = 0;
i = 0;
p_data = 64’h48656C6F210000;
end
else begin
if(i < 64) begin
datain = p_data[63-i];
i = i + 1;
end
end
end
endmodule
Waveform：
Reference：