CRC算法原理及其Verilog實現

FPGA基礎知識（39） 

http://blog.163.com/fpga_ip/blog/static/2044430242012558747194/

一．CRC簡介

    CRC校驗是一種在數據通信系統和其它串行傳輸系統中廣泛使用的錯誤檢測手段。通用的CRC標準有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在網絡通信系統中應用最廣泛的是CRC-32標準。本文將以CRC-32為例，說明CRC編碼的實現方式以及如何用verilog語言對CRC編碼進行描述。

二．模2運算

   在說明CRC編碼方式之前，首先介紹一下模2運算法則，在CRC運算過程中會使用到模2除法運算。模2運算是一種二進制運算法則，與四則運算相同，模2運算也包括模2加、模2減、模2乘、模2除四種運算。模2運算用“+”表示加法運算，用“-”、“×”或“.”、“/”分別表示減法、乘法和除法運算。與普通四則運算法則不同的是，模2加法是不帶進位的二進制加法運算，模2減法是不帶借位的二進制減法運算。同時，模2乘法在累加中間結果時采用的是模2加法運算；模2除法求商過程中余數減除數采用的是模2減法運算。因此，兩個二進制數進行模2加減法運算時，相當于兩個二進制數進行按位異或運算，每一位的結果只與兩個數的當前位有關。模2除法在確定商時，與普通二進制除法也略有區別。普通二進制除法中，當余數小于除數時，當前位的商為0，當余數大于等于除數時，當前位的商為1。模2除法在確定當前位的商時，只關心余數的首位，首位為1則商為1，首位為0則商為0。

1.模2加法的定義：

     0+0=0，0+1=1，1+0=1，1+1=0。

  舉例如下：

     1010+0110=1100。

2.模2減法的定義：

     0-0=0，0-1=1，1-0=1，1-1=0。

  舉例如下：

     1010-0110=1100。

3.模2乘法的定義：

     0×0=0，0×1=0，1×0=0，1×1=1。

  舉例如下：

     1011×101=100111

  列豎式計算：

     1011

     × 101

——————

       1011

      0000

     1011

——————

     100111

  其中橫線之間的累加過程，采用的是2進制加法，不進位。

4.模2除法：就是異或

     0/1=0，1/1=1。

  舉例如下：

     1011/101=10，余數為100。

  列豎式計算：

            10  

        ————

      101  ）1011

          101

        ————

           001

           101

        ————

           001

三.CRC實現原理

    CRC校驗的基本思想是：利用線性編碼理論，在發送端根據要發送的k位二進制碼序列，以一定的規則產生一個校驗用的r位監督碼（即CRC碼），并附在信息碼后面，構成一個新的共k+r位的二進制碼序列，最后發送出去。在接受端，則根據信息碼和CRC碼之間所遵行的規則進行校驗，以確定傳輸過程中是否出錯，并糾錯。一般而言，監督碼的位寬r越大，糾錯能力就越能，例如，CRC32的糾錯能力比CRC16要強。CRC校驗獲得監督碼的方式是，將k位信息碼轉換成多項式，然后除以一個生成多項式，獲得余數即為監督碼。

在求解一個k位二進制信息碼的CRC之前，首先需要將二進制信息碼轉換成多項式。一個二進制數序列的各個位是它對應多項式的系數，例如，二進制序列1101011101對應的多項式為：

      M(x)= 1×X⁹+1×X⁸+0×X⁷+1×X⁶+0×X⁵+1×X⁴+1×X³+1×X²+0×X¹+1×X⁰

      M(x)= X⁹+X⁸+X⁶+X⁴+X³+X²+1

    通過這種轉換方式獲得的多項式稱為信息多項式。在進行CRC計算時，除了信息多項式之外，還需要有一個生成多項式G(x)。生成多項式G(x)要求次數大于0，并且要求0次冪的系數為1。根據以上約束，以及對糾錯能力的要求，人們提出了一些通用的CRC生成多項式，例如：CRC16和CRC32等。

 CRC16的生成多項式為：G(x)= X¹⁵+X¹⁰+X²+1

 CRC32的生成多項式為：G(x)= X³²+X²⁶+X²³+ X²²+X¹⁶+X¹²+ X¹¹+X¹⁰+X⁸+ X⁷+X⁵+ X⁴+ X²+X¹+1

CRC的值等于信息多項式M(x)乘以2ⁿ ，再除以生成多項式G(x)所得的余數，除法采用模2除法。其中，n表示的是生成多項式G（x）的最高次冪，CRC16中n為16，CRC32中n為32。

四．CRC-32串行計算公式推導

    根據二進制信息碼轉換成多項式的方法，對于任意一個長度為（m+1）的二進制信息碼，可以轉換成一個最高次冪為m的多項式：

        M(x)= M_m×X^m+ M_m-1×X^m-1+ … + M₁×X¹+ M₀×X⁰

 將以上公式中的X置換成2，表示是一個二進制的多項式，那么該多項式的系數只能是1和0。

        M(x)= M_m×2^m+ M_m-1×2^m-1+ … + M₁×2¹+ M₀×2⁰

 為求此二進制序列的CRC值，首先將M(x）乘以2³²，然后再除以生成多項式G（x），所得余數即為CRC32的值。G（x）亦為一個二進制多項式。設除法運算獲得的商為Q(x),余數為R（x），那么：

        M(x)×2³²/ G(x)= M_m×2^m×2³²/ G(x) + M_m-1×2^m-1×2³²/ G(x) + … + M₁×2¹×2³²/ G(x)

                        + M₀×2⁰×2³²/ G(x)

                              --------（公式一）

         M(x)×2³²/ G(x) = Q(x) + R(x)/ G(x)                                 --------（公式二）  

    將M(x)中最高次項的系數M_m作為一個特殊的M(x)即帶入公式二，即得到公式三：

         M_m×2³²/ G(x) = Q_m(x) + R_m(x)/ G(x)                                 --------（公式三）

其中，M_m是一個只有0次冪的多項式，M_m的值為1。R_m(x)是余數，是一個最高次冪為31的多項式。再將公式三代入公式一:

       M(x)×2³²/ G(x) = M_m×2^m×2³²/ G(x) + M_m-1×2^m-1×2³²/ G(x) + … + M₁×2¹×2³²/ G(x)           + M₀×2⁰×2³²/ G(x)

                      ={ Q_m(x)×2^m + R_m(x)/ G(x)×2^m} + M_m-1×2^m-1×2³²/

        G(x)+ … + M₁×2¹×2³²/ G(x) + M₀×2⁰×2³²/ G(x)

                      = Q_m(x)×2^m + {R_m(x)×2/G(x)×2^m-1 + M_m-1×2^m-1×2³²/

       G(x)} + … + M₁×2¹×2³²/ G(x) + M₀×2⁰×2³²/ G(x)

       = Q_m(x)×2^m + {(R_m(x)×2 + M_m-1×2³²)/ G(x)} ×2^m-1  + … + M₁×2¹×2³²/ G(x)

        + M₀×2⁰×2³²/ G(x)

                                                            --------（公式四）

公式四中，設

        {(R_m(x)×2 + M_m-1×2³²)/ G(x)}= Q_m-1(x) + R_m-1(x)/ G(x)           --------（公式五）

再代入到公式四中，那么公式四轉化為：

        M(x)×2³²/ G(x)= Q_m(x)×2^m + Q_m-1(x)×2^m-1 + {(R_m-1(x)×2 + M_m-2×2³²)/ G(x)} ×2^m-2 

                        + … + M₁×2¹×2³²/ G(x) +  M₀×2⁰×2³²/ G(x)

以此類推，最終獲得公式：

        M(x)×2³²/ G(x)= Q_m(x)×2^m + Q_m-1(x)×2^m-1 + Q_m-2(x)×2^m-2 + … + Q₁(x)×2¹

                       + Q₀(x) + R₀(x)/G(x) 

                                                                                  --------(公式六)

根據CRC的定義，多項式R₀(x)對應的系數即為我們的CRC32的值。

以上推導過程表明：一個m+1位的二進制序列，可以按位求取CRC32的值。運算時，首先從最高位(第m+1位，設最右邊的為第1位)開始計算，然后依次計算較低位。當輸入第n個位(n<m+1)時，首先將第n+1位運算后的結果乘以2，再將第n的值(0或1)乘以232，兩者相加后除以生成多項式G(x)。因此，每一位的CRC32運算就轉化成了一個最高次冪為32的多項式除以一個最高次冪為32的多項式（生成多項式），結果（余數）為一個最高次冪不超過31的多項式。 

五．CRC32串行計算的LFSR實現

    上一節已經推導出了CRC的串行實現方法，但如何將公式六用Verilog語言表示出來呢？用Verilog描述CRC32的串行計算方法時，使用到了一種叫做LFSR（Linear feedback shift register）的結構。下圖為該LFSR的結構圖，其中寄存器3到寄存器25沒有在圖中畫出。

                                        圖1.CRC32的串行移位寄存器實現

    如圖所示，各個寄存器儲存著上一次CRC32運算的結果，寄存器的輸出即為CRC32的值。讓我們回顧一下CRC32的生成多項式：

  G(x)= 2³²+2²⁶+2²³+ 2²²+2¹⁶+2¹²+2¹¹+2¹⁰+2⁸+ 2⁷+2⁵+ 2⁴+ 2²+2¹+1    當輸入新的位參與運算時，信息多項式為：

  M(x)= M_n×2³²    上一次CRC計算的結果為：

  R_n+1(x) = A₃₁×2³¹+ A₃₀×2³⁰+ A₂₉×2²⁹+ … + A₂×2²+ A₁×2¹+ A₀×1    根據上一節推導出的公式，新的CRC32值R_n(x)為{R_n+1(x)×2 + M(x)}/ G(x)的余數。設

  Q(x) = R_n+1(x)×2 + M(x),則：

  Q(x) = （A₃₁+ M_n）×2³²+ A₃₀×2³¹+ A₂₉×2³⁰+ … +A₁×2²+ A₀×2¹

在計算Q(x)/ G(x)的結果時，根據模2運算法則，如果A₃₁+ M_n的結果為1，則商為1，余數為Q(x)- G(x)；如果A₃₁+ M_n的結果為0，則商為0，余數為Q(x)本身。其中，A₃₁+ M_n是模2加法，不進位；Q(x)- G(x) 模2減法，不借位。

根據以上分析，上圖中的結構剛好能夠完成一位串行輸入的CRC32計算。當上一個CRC32結果的最高位A₃₁和輸入的數值M_n模2加法結果為1時，上一次CRC結果右移一位，完成乘2的過程，再與G(x)多項式的系數進行異或運算，完成減法。由于任何數與0異或保持不變，所以LFSR中只有在G(x)多項式為1的系數處才放置異或門。運算完畢以后把結果存入寄存器即為新的CRC32值。當上一個CRC32結果的最高位A₃₁和輸入的數值M_n模2加法結果為0時，Q(x)不夠除，Q(x)本身作為余數存入寄存器，獲得新的CRC32值。由于A₃₁+ M_n的結果為0，異或門不起作用，Q(x) = A₃₀×2³¹+ A₂₉×2³⁰+ … +A₁×2²+ A₀×2¹，由R_n+1(x) 右移一位獲得, Q(x)的0次冪為0，剛好把A₃₁+ M_n的結果作為輸入。

因此，以上LFSR結構能夠實現串行CRC32運算，且這種結構很容易在Verilog語言中描述。

六．CRC32串行計算的Verilog實現

        根據第五節中的描述，一位數據的CRC32值為：

               crc32_new = {crc32_old[30:0],1'b0} ^ ({32{(crc32_old[31] ^ datain)}} & POLYNOMIAL) ;

       求一個二進制序列的CRC32值時，可以讓二進制序列的各個位依次計算CRC32，最終的結果即為二進制序列的CRC32值。例如一個長度為8的二進制序列，它的CRC32值為： 

        always@( * )

              begin

                      for(i = 0 ,i<= 7,i = i +1)

                 crc32_new = {crc32_old[30:0],1'b0} ^ ({32{(crc32_old[31] ^ datain[i])}} & POLYNOMIAL) ;

            end