聊一聊CRC并行計算

CRC簡單算法和一種并行計算請參考《CRC原理與快速verilog仿真》
LFSR的定義請參考《多項式乘除法的LFSR實現(xiàn)》

1 單一寬度的并行CRC計算；

所謂單一寬度，比如每次要傳輸64bit數(shù)據(jù)，需要做一次獨(dú)立的CRC計算冗尤；那么就適合本節(jié)的內(nèi)容。本節(jié)內(nèi)容僅僅提供一種解決思路，屬于思路拓展类嗤，通用方法參考第二節(jié)；

首先我們看一下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的數(shù)黄伊，而任意一個8bit的數(shù)都可以表示為：

$\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，不參與整體的異或運(yùn)算毡惜；
如 $b_i=1$ ,則 $cell_i$ 計算的CRC值為固定值拓轻，參與整體的異或運(yùn)算；

所有 $b_i=1$ 時经伙， $cell_i$ 根據(jù)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

從上圖也可以從另個角度推導(dǎo)出：
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計算帕膜，關(guān)于連續(xù)未知寬度的算法枣氧，下一節(jié)將給出推導(dǎo)過程。

2 不定寬度的CRC計算

所謂不定寬度垮刹，如網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)达吞，是可以變換的，沒有固定的一個長度限制荒典；
對于這個問題酪劫，我還是喜歡從CRC定義的源頭來找答案

2.1 CRC的LFSR實現(xiàn)

通常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多項式；
還以第一節(jié)例子為例（POLY=0b10011）：
根據(jù)多項式乘除法的LFSR實現(xiàn)一文得到如下LFSR：

crc_lfsr.jpg

2.2 python推導(dǎo)出并行verilog代碼

其思路很簡單：

實現(xiàn)單bit輸入的LFSR寺董；
循環(huán)并行數(shù)據(jù)位寬覆糟；
消除冗余異或；

代碼如下：

#-------------------------------------------------------------------------
# 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：

發(fā)送端：
- 發(fā)送數(shù)據(jù)按byte翻轉(zhuǎn)滩字，bit7和bit0，bit6和bit1，以此類推麦箍；
- CRC的初始值定位32'hFFFF_FFFF;
- 計算出32bit CRC后漓藕，每個字節(jié)按字節(jié)翻轉(zhuǎn)，注意高低byte不需要換位置内列，各byte內(nèi)部翻轉(zhuǎn)撵术；
- 上一步驟完成后整體和32'hFFFF_FFFF異或；
- 數(shù)據(jù)附加在報文后面發(fā)送话瞧；
接收端校驗器設(shè)置
- POLY和發(fā)送端一致嫩与；
- 初值為32’hFFFF_FFFF;
- 接收字節(jié)翻轉(zhuǎn)；
接收端校驗值1
- 接收到FCS字段后交排，將FCS與32’hFFFF_FFFF異或后送入CRC校驗校驗器划滋，校驗結(jié)果為32'hFFFF_FFFF;
接收端校驗值2
- 接收到FCS字段后，不處理直接送入校驗器埃篓，得到32'hC704_DD7D為正確处坪；

4 小結(jié)

本文給出了固定寬度的CRC計算和不定寬度的CRC計算推導(dǎo)，中間難免有差錯架专，歡迎大家指正同窘；