基于查表法CRC檢錯碼改進算法的研究與實現

周凱, 田楓, 李愛國

(1. 東北石油大學 計算機與信息技術學院,大慶 163318； 2.大慶油田工程有限公司,大慶 163712)

基于查表法CRC檢錯碼改進算法的研究與實現

周凱1, 田楓1, 李愛國2

(1. 東北石油大學 計算機與信息技術學院,大慶 163318； 2.大慶油田工程有限公司,大慶 163712)

在工業現場通信過程中為保證數據傳輸的正確性，采用了CRC校驗碼，并且選擇了基于查表法來提高生成CRC碼的效率。通用查表法中每次計算出1個字節的CRC碼，處理效率不高，所以提出了一種基于通用查表法的一種改進算法。改進后的算法每次處理2個字節，即計算出2個字節的CRC校驗碼，并且需要分別保留這2個字節的CRC碼。下一組的2個字節信息輸入后，借助前面兩個字節的CRC校驗碼計算出后面兩個字節的CRC校驗碼。以此類推，每一組的2個字節的CRC碼都是在上一組2個字節的CRC碼的基礎上計算獲得，直到所有信息輸入完畢。在進行實驗驗證后，結果表明該算法運行時間相對有所減少。

基金會現場總線； CRC； 查表法； 校驗碼

0 引言

工業現場中，儀器儀表及各種自動化裝置間的聯網通訊已非常普遍，由于信道本身的原因及環境干擾因素，數據傳輸過程中出現差錯幾乎不可避免，誤碼的產生影響系統正常工作甚至引發災難性后果，因此，數據接收方必須對數據的正確性進行判斷以決定是否可用[1]。鑒于上述原因，在實際的通信過程中，多種校驗算法不斷發展，循環冗余校驗(Cyclic Redundancy Check, CRC)作為一種特殊的線性分組編碼被廣泛應用于相關領域，最主要的原因就是查表法的計算速度快，糾錯能力強[2][3]。

1 CRC校驗碼的原理及算法

CRC碼的原理為將要發送的數據作為多項式F(x)的系數，這里系數的取值只能為0或1；多項式G(x)作為雙方預先約定好的多項式，發送方用多項式F(x)除以G(x)，得到余數多項式CRC(x)；將CRC(x)附加到多項式F(x)后，發送到接收方；接收方將接收到的多項式除以G(x)，判斷運算結果：如果最后的余數為0，則表示傳輸正確，如果余數不為0，則表示傳輸錯誤，請求重新發送。算法實現過程如下：

步驟1：設要發送的m位信息作為多項式F(x)的系數，則多項式為m階多項式，最高階為m-1，可表示為：

步驟2：設G(x)為發送方和接收方約定好的生成多項式，設G(x)為k階，表示為：

步驟3：將要發送的數據向左移動K位，則變為M+K位的多項式，則為：

步驟4：用G(x)除多項式F’(x)運算，則求出余數CRC(x)，如式(1)。

(1)

步驟5：將余數CRC(x)直接附加到多項式F’(x)最后，則要發送的數據就變為F′(x)+CRC(x)，然后進行發送。

步驟6：接收端受到信息后，用G(x)對接收到的信息再進行模2除[4]運算，如式(2)。

(2)

步驟7：將式(1)代入式(2)中，得到式(3)。

(3)

步驟8：根據相同的序列按位異或的結果為0，所以式(3)可化為式(4)。

(4)

步驟9：根據式(4)可以看出，判斷接收端是否正確，只需要看最后的運算結果是否有余數，如果無余數，則表示無差錯，如果有余數，則說明有差錯，重新發送。

根據上述步驟，計算出00-FFH所有的CRC校驗碼，計算過程中采用的生成多項式為國際標準CRC-16(即G(x)=x16+x15+x2+1，形成CRC-16校驗碼表[5]。

2 CRC查表法的基本理論

CRC查表法中是以單字節為單位，每個字節有28=256種情況，所以對應的CRC校驗碼也有256種。將這些校驗碼(256*2=512字節)存儲于一個表中，根據輸入的信息可直接在表中查找到相對應的CRC校驗碼。

2.1 通用查表法的實現

通用查表法的算法為設要輸入的信息為F(1)，F(2)，F(3)，……，如圖1所示。

圖1 輸入信息圖

對F(1)進行查表，得到F(1)的CRC校驗碼CF(1)，取校驗碼CF(1)的高8位和F(2)進行異或運算得到F’(2)，取CF(1)的低8位和F(3)進行異或運算得到F’(3)，則輸入信息變為F’(2)，F’(3)，……，以此類推，直到所有的信息全部執行完。具體過程如圖1所示。在通用查表法中，每次僅處理一個字節的信息，直到所有的信息處理完畢，最后得到的就是此信息的CRC校驗碼。

2.2 CRC查表法的改進算法

通用查表法中，每次僅處理一個字節，改進后的算法與通用查表法最大的不同是一次處理2個字節。根據要發送的信息，首先處理第1個和第2個字節，即通過異或運算分別求出他們的CRC校驗碼，并且對這兩個校驗碼分別進行保存，不進行合并處理；接下來讀入下一組的2個字節信息，這2個字節的CRC碼的計算需要借助于第一組中2個字節的CRC校驗碼才能計算出來，所以要求整個計算過程中不能對每組中的2個字節的CRC碼進行合并；以此類推，每一組的2個字節的CRC碼都是在上一組2個字節的CRC碼的基礎上計算獲得，直到所有信息輸入完畢；最后根據最后一個字節的CRC校驗碼計算出整個信息的CRC校驗碼。

改進的查表法的算法：設要輸入的信息為F(1)，F(2)，F(3)，F(4)……，根據F(1)的數據查出所對應的16位校驗碼，命名為CRC(1)，那么它就是F(1)的校驗碼；F(2)的校驗碼CRC(2)的值是將F(2)與CRC(1)的高8位異或運算，得到的值進行查表得出；F(3)的CRC校驗碼CRC(3)的計算是用F(3)、CRC(1)的低8位和CRC(2)的高8位進行異或運算后，查表得出；同理F(4)的CRC校驗碼CRC(4)是用F(4)、CRC(2)的低8位和CRC(3)的高8位進行異或運算后，查表得出；以此類推，CRC(n)的值應為F(n)和CRC(n-2)的低8位和CRC(n-1)的高8位進行異或運算后查表所得。具體實現過程,如圖2所示。

圖2中，先計算出F(1)、F(2)的CRC碼CRC(1)、CRC(2)，且沒有進行合并處理。當F(3)、F(4)在同時讀入時，根據改進的查表算法，分別算出F(3)、F(4)的CRC碼，代替原來的CRC(1)、CRC(2)，保留至下次輸入信息。整個發送信息的CRC碼用最后一個字節的CRC碼的高8位和上一個字節CRC碼的低8位異或運算，得到的結果左移8位后加上最后字節的低8位。

3 實驗設計與分析

實驗系統中采用主/從結構的通信方式，即網絡中制定一個站作為主站，負責控制所有的通信，主站采用輪詢的方式進行通信，從站要在主站的啟動下才能進行通信，負責接收信息。在保證數據傳輸正確性的同時，更重要的是進行傳輸后對比兩種算法的時間效率。將要傳送的數據存儲在一個文件名為b.TXT文件中，然后根據兩種不同的算法對該TXT文件進行讀入，最終計算出該文檔中數據的CRC碼所花費的時間。

實驗步驟如下：

步驟1：創建傳送數據文本文件b.TXT，文件中包含若干字節的待傳輸數據。

步驟2：分別編寫通用查表算法和改進的查表算法的程序，兩種算法的流程圖(假設傳輸數據的字節數大于2)如圖3，圖4所示。

步驟3：將要傳送的數據文件導入兩種算法中，分別計算出CRC碼所花費的時間。為了解決其他軟件可能占用時間，時間不穩定的問題，實驗中將兩種算法的程序運行不同的次數進行比較。

圖2 改進的查表法的計算過程

圖3 通用查法算法流程圖

圖4 改進查表法算法流程圖

步驟4：對比運行結果，得出結論。

實驗結果,如表1所示。

表1 計算同一文件兩種算法的時間對比

從表1中的統計結果可以看出，運用改進的查表法計算CRC校驗碼所花費的時間較短，所以改進的查表法的算法是優于通用查表法的算法的。

4 總結

由于CRC校驗碼便于實現、糾錯能力強，已經得到廣泛的應用。工業現場通信系統中采用CRC校驗能夠提高數據傳輸的質量以及差錯控制能力。本文提出的CRC校驗碼的改進算法，經過實驗證明，改進的查表法不但能夠保證傳輸的正確性，而且相對于通用查表法來說，縮短了生成CRC碼的時間。

[1] 陽憲惠.現場總線技術及其應用[M].北京:清華大學出版社,2005:41-43.

[2] 王月琴,楊恒新. CRC碼串并結合算法的研究與實現[J].計算機技術與發展 2014(6):103-106.

[3] 周趙斌,許力,李世唐.基于CRC的防污染網絡編碼方案[J].計算機系統應用.2016(25):101-106.

[4] 藺冰.關于同余式2n≡4(modn)[J].安徽師范大學學報:自然科學版,2010,33(5)：425-427.

[5] 鹿玲杰.CRC檢錯碼在基金會現場總線通信中的應用[J].南方冶金學院學報,2005,(8):22-26.

Research and Implementation of the CRC Improved Algorithm Based on Check Look-Up Table Algorithm

Zhou Kai1, Tian Feng1, Li Aiguo2

(1. School of Computer and Information Technology, Northeast Petroleum University, Daqing, 163318, China;2. Daqing Oilfield Engineer CO., Daqing, 163712, China)

In order to judge the correctness of data transmission in Industrial field, the Cyclic Redundancy Check look-up table algorithm is adopted in the CRC code. An improved algorithm is proposed based on general look-up table algorithm. It could read 2 bytes once, and calculate the CRC code of 2 bytes, but the two CRC codes does not been merged in the improved algorithm. After reading a group of 2 bytes information, according to the previous two bytes CRC code to calculate the following 2 bytes CRC code, until all the information input is completed. After the experimental verification, the results show that the running time of the algorithm is relatively reduced.

FF; CRC; look-up table; check code

國家自然科學基金項目(61502094)，黑龍江省自然科學基金項目(F2016002)

周凱(1979-)，女，黑龍江肇源，講師，碩士研究生，研究方向：工業控制。 田楓(1980-)，男，黑龍江安達，副教授，博士研究生，研究方向：數據挖掘、圖像處理。 李愛國(1979-)，男，山東菏澤，高級工程師，碩士研究生，研究方向：供配電。

1007-757X(2017)08-0012-03

TP311

A

2000.00.00)