CRC简单算法和一种并行计算请参考《CRC原理与快速verilog仿真》
LFSR的定义请参考《多项式乘除法的LFSR实现》
1 单一宽度的并行CRC计算；
所谓单一宽度，比如每次要传输64bit数据，需要做一次独立的CRC计算；那么就适合本节的内容。本节内容仅仅提供一种解决思路，属于思路拓展，通用方法参考第二节；
首先我们看一下GF(2)的一个定理：
可以被看作是输入的序列，
则是POLY多项式；
以DATA=8'hE6，POLY=5’b10011为例；
因输入为8bit的数，而任意一个8bit的数都可以表示为：
把上面每一项记做，所以：
即：DATA的CRC计算可以看作是各个cell分别对POLY做CRC计算，然后再按位异或在一起。
每个cell对POLY对CRC计算取决于的值:
- 如
,则
计算的CRC值为0，不参与整体的异或运算；
- 如
,则
所有时，
根据POLY=5'b10011计算的cell_crc如下表：
| bit index | cell | cell_crc | cell_crc_hex |
|---|---|---|---|
| 7 | 1000_0000 | 1110 | E |
| 6 | 0100_0000 | 0111 | 7 |
| 5 | 0010_0000 | 1010 | A |
| 4 | 0001_0000 | 0101 | 5 |
| 3 | 0000_1000 | 1011 | B |
| 2 | 0000_0100 | 1100 | C |
| 1 | 0000_0010 | 0110 | 6 |
| 0 | 0000_0001 | 0011 | 3 |
可以画出CRC的计算图如下：
CRC并行计算图1.png
从上图也可以从另个角度推导出：
crc[3]=(bit7&1)\^(bit6&0)\^(bit5&1)\^(bit4&0)\^(bit3&1)\^(bit2&1)\^(bit1&0)\^(bit0&0) = bit7 ^ bit5 ^ bit3 ^ bit2;
以此类推CRC其他bit位，可以得到：
crc[3]=data[7]^data[5]^data[3]^data[2];
crc[2]=data[7]^data[6]^data[4]^data[2]^data[1];
crc[1]=data[7]^data[6]^data[5]^data[3]^data[1]^data[0];
crc[0]=data[6]^data[4]^data[3]^data[0];
注意此式只适合固定长度CRC计算，本文称之为单一宽度的CRC计算，关于连续未知宽度的算法，下一节将给出推导过程。
2 不定宽度的CRC计算
所谓不定宽度，如网络传输的数据，是可以变换的，没有固定的一个长度限制；
对于这个问题，我还是喜欢从CRC定义的源头来找答案
2.1 CRC的LFSR实现
通常CRC的多项式定义为：
也被称为POLY多项式；
还以第一节例子为例（POLY=0b10011）：
根据多项式乘除法的LFSR实现一文得到如下LFSR：
crc_lfsr.jpg
2.2 python推导出并行verilog代码
其思路很简单：
- 实现单bit输入的LFSR；
- 循环并行数据位宽；
- 消除冗余异或；
代码如下：
#-------------------------------------------------------------------------
# user define parameter
POLY_W=32 #POLY WIDTH
POLY='0x04C11DB7' #POLY in hex
DATA_W=8 #parallel data width
#-------------------------------------------------------------------------
#1 bit xor caculation
def xor(a,b):
if a==b or str(a)==str(b):
return('0')
elif a=='0' and b=='1' or a==0 and b==1:
return('1')
elif a=='1' and b=='0' or a==1 and b==0:
return('1')
elif a=='0' or a==0:
return(str(b))
elif b=='0' or b==0:
return(str(a))
elif a!=b:
return(str(a)+"^"+str(b))
#implement crc caculation w/ serial bit input
def crc_s(c,d):
e=[0 for x in range(POLY_W)] #e store the next crc value
bfmt="{:0%sb}"%POLY_W #binary format
poly_b=bfmt.format(int(POLY,16)) #poly to binary w/ width of POLY_W
t=xor(c[POLY_W-1],d) #bit0 input
idx=POLY_W-1
for i in poly_b:
if(idx==0):
e[idx]=t
elif(i=='1'):
e[idx]=xor(c[idx-1],t)
else:
e[idx]=c[idx-1]
idx=idx-1
return e
#reduce the xor caculation in an array element;
def mparse(tmp):
t=tmp.split("^")
t.sort()
t_new=[]
tag="fill only 1 element"
for ti in t:
if t.count(ti)%2==0:
pass
elif ti!=tag:
t_new.append(ti)
tag=ti
return "^".join(t_new)
#create the simbol array for data and crc
c=["c[%d]"%x for x in range(POLY_W)] #crc index same as the array, from left to right lsb->msb
d=["d[%d]"%x for x in range(DATA_W-1,-1,-1)] #data index, invertion of the crc, from left to right msb->lsb
#parallel caculation
for di in d:
c=crc_s(c,di)
#reduce the xor simbol
c_new=[]
for ci in c:
c_new.append(mparse(ci))
#print the each fucntion
i=0
for cni in c_new:
print("crc_cal[%d]=%s;"%(i,cni))
i=i+1
3 FCS校验
802.3给出了FCS校验的定义，CRC的POLY多项式位32'h04CB_11D7：
-
发送端：
- 发送数据按byte翻转，bit7和bit0，bit6和bit1，以此类推；
- CRC的初始值定位32'hFFFF_FFFF;
- 计算出32bit CRC后，每个字节按字节翻转，注意高低byte不需要换位置，各byte内部翻转；
- 上一步骤完成后整体和32'hFFFF_FFFF异或；
- 数据附加在报文后面发送；
-
接收端校验器设置
- POLY和发送端一致；
- 初值为32’hFFFF_FFFF;
- 接收字节翻转；
-
接收端校验值1
- 接收到FCS字段后，将FCS与32’hFFFF_FFFF异或后送入CRC校验校验器，校验结果为32'hFFFF_FFFF;
-
接收端校验值2
- 接收到FCS字段后，不处理直接送入校验器，得到32'hC704_DD7D为正确；
4 小结
本文给出了固定宽度的CRC计算和不定宽度的CRC计算推导，中间难免有差错，欢迎大家指正；
网友评论