生成多項式

若一個循環碼的所有碼字多項式都是一個次數最低的非零首一多項式 g(x)的倍式，則稱g(x)生成該碼，並稱g(x)為該碼的生成元或生成多項式。

生成多項式是接受方和發送方的一個約定，也就是一個二進位數，在整個傳輸過程中，這個數始終保持不變。在發送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接收方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。

應滿足以下條件：

A、生成多項式的最高位和最低位必須為1。

B、當被傳送信息（CRC碼）任何一位發生錯誤時，被生成多項式做除后應該使餘數不為0。

C、不同位發生錯誤時，應該使餘數不同。

D、對餘數繼續做除，應使餘數循環。

生成多項式位數 =CRC校驗碼位數 +1。注意有些生成多項式的簡記式中將生成多項式的最高位1省略了。

（1）生成多項式的比特數越大，其差錯檢測能力越強；漏檢錯誤率越低。

（2）生成多項式比特數相同的情況下，差錯檢測能力相同；漏檢錯誤率範圍大致相同，但是對於不同的通道誤碼率，又有不同的漏檢錯誤率。

若設碼字長度為N，信息欄位為K位，校驗欄位為R位，則對於CRC碼集中的任一碼字，存在且僅存在一個R次多項式，使得

其中: m(x)為K次原始的信息多項式，為次校驗多項式（即CRC校驗和），

稱為生成多項式：

發送方通過指定的產生CRC碼字，接收方則通過該來驗證收到的CRC碼字。

結合系統的具體特點及要求，提出一種生成多項式的選取方法，其主要設計思想有以下兩個方面：

（1）首先，為了確保選取的生成多項式校驗性能是最優的，考察在具體嵌入式網路系統中傳輸數據幀最大長度的情況下，碼重最大，漏檢率最低的生成多項式。

（2）其次，為了確保選取的生成多項式有較廣的使用範圍和良好的可移植性，分別考察小於和大於最大數據幀長度的情況，生成多項式的碼重及漏檢率的情況。

在這裡要注意的是嚴格按照這兩個方面的優先次序考慮，在保證自身應用環境中最優檢錯性能的前提下考察其擴展性和可移植性。

對於最小距離相同的生成多項式，要首先選取可檢測數據長度最大的生成多項式；對於較短的數據幀，如果要提高生成多項式的最小距離，必須以不影響該生成多項式對於長數據幀的校驗性能為前提；對於一些現行的協議，隨著網路的不斷發展，也會對協議進行修正，同時也會要求增加傳輸數據幀的長度，因此在選擇生成多項式時要考慮將來的可擴展性，使生成多項式傳輸較長數據幀時也能有較好的校驗性能。

藉助於模2除法則，其餘數為校驗欄位。

例如：信息欄位代碼為: 1011001；對應

假設生成多項式為：；則對應g(x)的代碼為: 11001

對應的代碼記為：10110010000；

採用模2除法則: 得餘數為: 1010(即校驗欄位為：1010）

發送方：發出的傳輸欄位為: 1 0 1 1 0 0 1 1010

信息欄位 校驗欄位

接收方：使用相同的生成碼進行校驗：接收到的欄位/生成碼（二進位除法）

如果能夠除盡，則正確，

給出餘數（1010）的計算步驟：

除法沒有數學上的含義，而是採用計算機的模二除法，即除數和被除數做異或運算。進行異或運算時除數和被除數最高位對齊，按位異或。

10110010000

^11001

01111010000

1111010000

^11001

0011110000

11110000

^11001

00111000

111000

^11001

001010

則四位CRC校驗碼就為：1010。

利用CRC進行檢錯的過程可簡單描述為：在發送端根據要傳送的k位二進位碼序列，以一定的規則產生一個校驗用的r位監督碼(CRC碼)，附在原始信息後邊，構成一個新的二進位碼序列數共位，然後發送出去。在接收端，根據信息碼和CRC碼之間所遵循的規則進行檢驗，以確定傳送中是否出錯。這個規則，在差錯控制理論中稱為“生成多項式”。

1、將X的最高次冪為R的生成多項式 轉換成對應的位二進位數。

2、將信息碼左移R位，相當於對應的信息多項式 。

3、用生成多項式（二進位數）對信息碼做除，得到R位的餘數（注意：這裡的二進位做除法得到的餘數其實是模2除法得到的餘數，並不等於其對應十進位數做除法得到的餘數）。

4、將餘數拼到信息碼左移后空出的位置，得到完整的CRC碼。

【例】假設使用的生成多項式是 。4位的原始報文為1010，求編碼后的報文。

解：

1、將生成多項式 =轉換成對應的二進位除數1011。

2、此題生成多項式有4位（注意：4位的生成多項式計算所得的校驗碼為3位，R為校驗碼位數），要把原始報文 左移3（R）位變成1010 000

3、用生成多項式對應的二進位數對左移3位后的原始報文進行模2除（高位對齊），相當於按位異或：

1010000

1011

0001000

0001011

0000011

得到的余位011，所以最終編碼為：1010 011

名稱 生成多項式 簡記式* 應用舉例

生成多項式的最高冪次項係數是固定的1，故在簡記式中，將最高的1統一去掉了，如04C11DB7實際上是104C11DB7。

備註：

（1）生成多項式是標準規定的

（2）CRC校驗碼是基於將位串看作是係數為0或1的多項式，一個k位的數據流可以看作是關於x的從階到0階的次多項式的係數序列。採用此編碼，發送方和接收方必須事先商定一個生成多項式，其高位和低位必須是1。要計算m位的幀的校驗和，基本思想是將校驗和加在幀的末尾，使這個帶校驗和的幀的多項式能被 除盡。當接收方收到加有校驗和的幀時，用 去除它，如果有餘數，則CRC校驗錯誤，只有沒有餘數的校驗才是正確的。