聊一聊CRC并行计算

2020-08-17 本文已影响0人 sarai_c7eb

CRC简单算法和一种并行计算请参考《CRC原理与快速verilog仿真》
LFSR的定义请参考《多项式乘除法的LFSR实现》

1 单一宽度的并行CRC计算；

所谓单一宽度，比如每次要传输64bit数据，需要做一次独立的CRC计算；那么就适合本节的内容。本节内容仅仅提供一种解决思路，属于思路拓展，通用方法参考第二节；

首先我们看一下GF(2)的一个定理：

$\begin{align} F(x) &= M(x) \oplus N(x) \\ \Rightarrow F(x)\% g(x) &=[M(x)\% g(x) ]\oplus [N(x)\% g(x)] \end{align}$

$F(X)$ 可以被看作是输入的序列， $g(x)$ 则是POLY多项式；

以DATA=8'hE6，POLY=5’b10011为例；
因输入为8bit的数，而任意一个8bit的数都可以表示为：

$\begin{align} b_70000000 &\oplus 0b_6000000\oplus 00b_500000\oplus 000b_40000\oplus \\ 0000b_3000&\oplus 00000b_200\oplus 000000b_10 \oplus 0000000b_0; \end{align}$

把上面每一项记做 $cell_i,i\in(7,6,5,4,3,2,1,0)$ ，所以：
$\begin{align} F(x)\%g(x)=cell_7\%g(x)\oplus cell_6\%g(x)\oplus ... \oplus cell_1\%g(x)\oplus cell_0\%g(x) \end{align}$

即：DATA的CRC计算可以看作是各个cell分别对POLY做CRC计算，然后再按位异或在一起。

每个cell对POLY对CRC计算取决于 $b_i$ 的值:

如 $b_i=0$ ,则 $cell_i$ 计算的CRC值为0，不参与整体的异或运算；
如 $b_i=1$ ,则 $cell_i$ 计算的CRC值为固定值，参与整体的异或运算；

所有 $b_i=1$ 时， $cell_i$ 根据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的多项式定义为：
$\begin{align} crc(x)&=(m(x)*x^{r-1})\%g(x) \\ g(x)&= g_rx^r+g_{r-1}x^{r-1}+...+g_2x^2+g1_x^1+g0 \end{align}$
$g(x)$ 也被称为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计算推导，中间难免有差错，欢迎大家指正；