基于查表法CRC檢錯(cuò)碼改進(jìn)算法的研究與實(shí)現(xiàn)

周凱, 田楓, 李愛國(guó)

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

基于查表法CRC檢錯(cuò)碼改進(jìn)算法的研究與實(shí)現(xiàn)

周凱1, 田楓1, 李愛國(guó)2

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

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

基金會(huì)現(xiàn)場(chǎng)總線； CRC； 查表法； 校驗(yàn)碼

0 引言

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

1 CRC校驗(yàn)碼的原理及算法

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

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

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

步驟3：將要發(fā)送的數(shù)據(jù)向左移動(dòng)K位，則變?yōu)镸+K位的多項(xiàng)式，則為：

步驟4：用G(x)除多項(xiàng)式F’(x)運(yùn)算，則求出余數(shù)CRC(x)，如式(1)。

(1)

步驟5：將余數(shù)CRC(x)直接附加到多項(xiàng)式F’(x)最后，則要發(fā)送的數(shù)據(jù)就變?yōu)镕′(x)+CRC(x)，然后進(jìn)行發(fā)送。

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

(2)

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

(3)

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

(4)

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

根據(jù)上述步驟，計(jì)算出00-FFH所有的CRC校驗(yàn)碼，計(jì)算過程中采用的生成多項(xiàng)式為國(guó)際標(biāo)準(zhǔn)CRC-16(即G(x)=x16+x15+x2+1，形成CRC-16校驗(yàn)碼表[5]。

2 CRC查表法的基本理論

CRC查表法中是以單字節(jié)為單位，每個(gè)字節(jié)有28=256種情況，所以對(duì)應(yīng)的CRC校驗(yàn)碼也有256種。將這些校驗(yàn)碼(256*2=512字節(jié))存儲(chǔ)于一個(gè)表中，根據(jù)輸入的信息可直接在表中查找到相對(duì)應(yīng)的CRC校驗(yàn)碼。

2.1 通用查表法的實(shí)現(xiàn)

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

圖1 輸入信息圖

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

2.2 CRC查表法的改進(jìn)算法

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與分析

實(shí)驗(yàn)系統(tǒng)中采用主/從結(jié)構(gòu)的通信方式，即網(wǎng)絡(luò)中制定一個(gè)站作為主站，負(fù)責(zé)控制所有的通信，主站采用輪詢的方式進(jìn)行通信，從站要在主站的啟動(dòng)下才能進(jìn)行通信，負(fù)責(zé)接收信息。在保證數(shù)據(jù)傳輸正確性的同時(shí)，更重要的是進(jìn)行傳輸后對(duì)比兩種算法的時(shí)間效率。將要傳送的數(shù)據(jù)存儲(chǔ)在一個(gè)文件名為b.TXT文件中，然后根據(jù)兩種不同的算法對(duì)該TXT文件進(jìn)行讀入，最終計(jì)算出該文檔中數(shù)據(jù)的CRC碼所花費(fèi)的時(shí)間。

實(shí)驗(yàn)步驟如下：

步驟1：創(chuàng)建傳送數(shù)據(jù)文本文件b.TXT，文件中包含若干字節(jié)的待傳輸數(shù)據(jù)。

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

步驟3：將要傳送的數(shù)據(jù)文件導(dǎo)入兩種算法中，分別計(jì)算出CRC碼所花費(fèi)的時(shí)間。為了解決其他軟件可能占用時(shí)間，時(shí)間不穩(wěn)定的問題，實(shí)驗(yàn)中將兩種算法的程序運(yùn)行不同的次數(shù)進(jìn)行比較。

圖2 改進(jìn)的查表法的計(jì)算過程

圖3 通用查法算法流程圖

圖4 改進(jìn)查表法算法流程圖

步驟4：對(duì)比運(yùn)行結(jié)果，得出結(jié)論。

實(shí)驗(yàn)結(jié)果,如表1所示。

表1 計(jì)算同一文件兩種算法的時(shí)間對(duì)比

從表1中的統(tǒng)計(jì)結(jié)果可以看出，運(yùn)用改進(jìn)的查表法計(jì)算CRC校驗(yàn)碼所花費(fèi)的時(shí)間較短，所以改進(jìn)的查表法的算法是優(yōu)于通用查表法的算法的。

4 總結(jié)

由于CRC校驗(yàn)碼便于實(shí)現(xiàn)、糾錯(cuò)能力強(qiáng)，已經(jīng)得到廣泛的應(yīng)用。工業(yè)現(xiàn)場(chǎng)通信系統(tǒng)中采用CRC校驗(yàn)?zāi)軌蛱岣邤?shù)據(jù)傳輸?shù)馁|(zhì)量以及差錯(cuò)控制能力。本文提出的CRC校驗(yàn)碼的改進(jìn)算法，經(jīng)過實(shí)驗(yàn)證明，改進(jìn)的查表法不但能夠保證傳輸?shù)恼_性，而且相對(duì)于通用查表法來說，縮短了生成CRC碼的時(shí)間。

[1] 陽(yáng)憲惠.現(xiàn)場(chǎng)總線技術(shù)及其應(yīng)用[M].北京:清華大學(xué)出版社,2005:41-43.

[2] 王月琴,楊恒新. CRC碼串并結(jié)合算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展 2014(6):103-106.

[3] 周趙斌,許力,李世唐.基于CRC的防污染網(wǎng)絡(luò)編碼方案[J].計(jì)算機(jī)系統(tǒng)應(yīng)用.2016(25):101-106.

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

[5] 鹿玲杰.CRC檢錯(cuò)碼在基金會(huì)現(xiàn)場(chǎng)總線通信中的應(yīng)用[J].南方冶金學(xué)院學(xué)報(bào),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

國(guó)家自然科學(xué)基金項(xiàng)目(61502094)，黑龍江省自然科學(xué)基金項(xiàng)目(F2016002)

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

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

TP311

A

2000.00.00)