CRC查表法的推廣及其在iLOCK聯(lián)鎖系統(tǒng)中的應(yīng)用

董高云，孫軍峰

（卡斯柯信號(hào)有限公司，上海 200071）

CRC查表法的推廣及其在iLOCK聯(lián)鎖系統(tǒng)中的應(yīng)用

董高云，孫軍峰

（卡斯柯信號(hào)有限公司，上海 200071）

通過整數(shù)字節(jié)的CRC查表算法，改進(jìn)了CRC編碼校驗(yàn)算法的效率；同時(shí)經(jīng)過推導(dǎo)證明，可以將傳統(tǒng)的16 bit或32 bit的整數(shù)字節(jié)CRC查表法，推廣至小于16 bit或32 bit的任意位數(shù)信息位的非整數(shù)字節(jié)。隨后將這兩種CRC查表法，應(yīng)用到iLOCK計(jì)算機(jī)聯(lián)鎖系統(tǒng)中的冗余編碼運(yùn)算中，提高了冗余編碼計(jì)算的運(yùn)算效率及iLOCK系統(tǒng)的整體性能。

CRC；查表法；計(jì)算機(jī)聯(lián)鎖；冗余編碼

循 環(huán) 冗 余 編 碼 檢 驗(yàn) 技 術(shù)（CRC，Cyclic Redundancy Check）被廣泛應(yīng)用于通信傳輸領(lǐng)域。由于其實(shí)現(xiàn)簡(jiǎn)單，檢錯(cuò)能力強(qiáng)，被廣泛使用在各種數(shù)據(jù)校驗(yàn)應(yīng)用中。它占用系統(tǒng)資源少，用軟硬件均能實(shí)現(xiàn)，是進(jìn)行數(shù)據(jù)傳輸差錯(cuò)檢測(cè)的一種很好的手段[1～5]。卡斯柯信號(hào)有限公司 iLOCK 聯(lián)鎖系統(tǒng)[3～4]下位機(jī)的冗余編碼就采用了多種不同的CRC循環(huán)冗余編碼校驗(yàn)算法。

由于采用硬件實(shí)現(xiàn) CRC循環(huán)冗余編碼需要專用的移位寄存器電路，且硬件電路的調(diào)整不夠靈活，因此在 iLOCK 聯(lián)鎖系統(tǒng)中采用軟件來實(shí)現(xiàn) CRC 冗余編碼。由軟件完成 CRC 計(jì)算，即 CRC 的算法問題[5]，許多相關(guān)的文獻(xiàn)中對(duì)此均有描述，軟件CRC算法普遍存在相對(duì)于硬件 CRC 算法耗時(shí)長(zhǎng)的缺陷。

聯(lián)鎖下位機(jī)系統(tǒng)作為高實(shí)時(shí)的嵌入式系統(tǒng)，為了適應(yīng)大站場(chǎng)時(shí)的大規(guī)模聯(lián)鎖邏輯運(yùn)算的需求，對(duì)于計(jì)算效率的要求比較高。為了提高效率，需要盡量減少CRC計(jì)算的耗時(shí)，以改進(jìn)軟件CRC算法耗時(shí)長(zhǎng)的缺陷，為此，編程人員提出了眾多的解決方法，CRC 查表法是最常用的一種縮短計(jì)算耗時(shí)的方法。

本文闡述單字節(jié)的CRC算法原理，通過建立單字節(jié)CRC表格，實(shí)現(xiàn)雙字節(jié)迭代CRC查表法，并將其應(yīng)用于 iLOCK 聯(lián)鎖系統(tǒng)中。通過證明和推導(dǎo)，將整數(shù)字節(jié)的數(shù)據(jù)位的CRC查表法推廣至任意位數(shù)據(jù)位的非整數(shù)字節(jié)。隨后也將其應(yīng)用于 iLOCK 聯(lián)鎖系統(tǒng)中，大幅度提高了冗余編碼計(jì)算效率，從而提高了 iLOCK 系統(tǒng)的整體性能。

1 單字節(jié)CRC算法及CRC查表法簡(jiǎn)介

CRC 的計(jì)算原理說明如下 :

下面為一個(gè)二進(jìn)制除法計(jì)算過程，假設(shè)待計(jì)算CRC 的原始數(shù)據(jù)為一個(gè)字節(jié) 0xd8（11011000），CRC生 成 多 項(xiàng) 式 取 為 0x17d3b（10111110100111011），則以 0xd8 為被除數(shù)，以生成多項(xiàng)式為除數(shù)，進(jìn)行二進(jìn)制除法運(yùn)算。計(jì)算原理見文獻(xiàn) [1]。由于生成多項(xiàng)式為2個(gè)字節(jié)，進(jìn)行除法運(yùn)算時(shí)，被除數(shù)需要在其后 補(bǔ) 齊 2 個(gè) 字 節(jié) 的 0， 變 為 :0xd80000（11011000 00000000 00000000）。

上面計(jì)算 的余數(shù)為 0xdaab（1101101010101011），即為原始數(shù)據(jù) 0xd8 的 CRC 校驗(yàn)碼值。這就是單字節(jié) CRC 計(jì)算原理。

對(duì)于所有的單字節(jié)原始數(shù)據(jù)（信息碼）（取值范圍為 :0x00～0xff）采用上述的多項(xiàng)式除法，都唯一對(duì)應(yīng)一個(gè)雙字節(jié)的余數(shù)（CRC 校驗(yàn)碼），全部的單字節(jié)數(shù)據(jù)及其對(duì)應(yīng)的雙字節(jié)余數(shù)（CRC校驗(yàn)碼）即可組成一張表，于是可編寫程序代碼按上式的計(jì)算方法生成一張信息碼—校驗(yàn)碼對(duì)照表，求取單字節(jié)的信息碼所對(duì)應(yīng)的校驗(yàn)碼的過程就簡(jiǎn)化為了查表過程，縮短了多項(xiàng)式除法的計(jì)算時(shí)間，這就是通用的單字節(jié)查表法。

構(gòu)造上述 16 bitCRC 表的 C 語言程序如下 :

說明如下 :aPoly 為除數(shù)（生成多項(xiàng)式）但注意要去掉最高位，只保留低 16 bit雙字節(jié)。nData 即為0～255 的單字節(jié)原始信息位數(shù)據(jù)，Table_CRC[i]即為生成的校驗(yàn)碼表，共有 256 個(gè)值，對(duì)應(yīng) 0～255 的信息位 nData。nAccum 為中間余數(shù)，初值為 nData。當(dāng)中間余數(shù)最高位為1時(shí)，下一次的除法運(yùn)算的中間余數(shù)就是本次中間余數(shù)移位后和 aPoly 異或的結(jié)果，否則只需將本次中間余數(shù)移位即可[3]。

2 多字節(jié)CRC迭代查表算法及其在iLOCK聯(lián)鎖系統(tǒng)中的應(yīng)用

上述單字節(jié)查表法僅解決了單字節(jié)信息位數(shù)據(jù)的校驗(yàn)碼求取問題，對(duì)于2個(gè)字節(jié)的數(shù)據(jù)，作如下分析:

為與單字節(jié)的情況作比較，將兩字節(jié)拆開計(jì)算，先看高字節(jié)數(shù)據(jù)D1的計(jì)算:

上述運(yùn)算中將每移位一個(gè)字節(jié)的單字節(jié)除法運(yùn)算作為一個(gè)階段，稱為1次，則2個(gè)字節(jié)共有2次余數(shù)。

比較雙字節(jié)運(yùn)算和高字節(jié)運(yùn)算的第1次余數(shù)A’和 HA’。先看低字節(jié)余數(shù) A0’和 HA0’:注意到兩種運(yùn)算被除數(shù)的第 2 個(gè)字節(jié)均為 0x00，而第 1 次的余數(shù)的低字節(jié)數(shù)據(jù)只與被除數(shù)的第2個(gè)字節(jié)和除數(shù)的移位有關(guān)，根據(jù)前述的單字節(jié)查表法原理知，除數(shù)的移位操作只與被除數(shù)的最高字節(jié)D1有關(guān)，由于兩種運(yùn)算的D1值相同，因此除數(shù)的移位也完全相同，故有 :A0’=HA0’。

再 看 高 字節(jié)余 數(shù) A1’和 HA1’。 雙 字 節(jié)運(yùn)算的 A1’=D0^p1^p2^…^p8，p1～p8 為逐 位 移 位運(yùn)過程中與高字節(jié)被除數(shù)的第 3 個(gè)字節(jié) 0x00 相對(duì)齊的除數(shù)（生成多項(xiàng)式）的一個(gè)字節(jié)的部分碼位。而高字節(jié)運(yùn)算 HA1’=0x00^p1^p2^…^p8，同樣根據(jù)前述的單字節(jié)查表法原理知，由于兩種運(yùn)算的被除數(shù)最高位 D1 值相同，故除數(shù)移位也完全相同，即 p1～p8與 高 字 節(jié) 運(yùn) 算 的 p1～p8 也 相 同， 再 根 據(jù) 邏 輯 代 數(shù)的相關(guān)運(yùn)算定律，邏輯代數(shù)運(yùn)算滿足結(jié)合律，且有 data=0x00^data, 故 A1’=D0^(p1^p2^..p8)= D0^(0x00^p1^p2^…p8)=D0^HA1’。

由上面的分析可知，可直接根據(jù)高字節(jié)運(yùn)算的第 1 次余數(shù)值 HA0’，HA1’和低字節(jié)數(shù)值 D0 來計(jì)算出 A0’，A1’，而高字節(jié)的第1次余數(shù)實(shí)際上就是單字節(jié)CRC運(yùn)算，可直接由前述的單字節(jié)查表法程序查表算得。

設(shè)查表法計(jì)算的函數(shù)為 PA=f(D)，D 為單字節(jié)數(shù)據(jù)，PA 為余數(shù)值，則 A1’=HA1’^D0=(HA’＞＞8)^D0=f(D1)＞＞8^D0。A0’=f(D1) && 0x00FF。

接下來的第2次余數(shù)值計(jì)算與第1次結(jié)構(gòu)完全相同，僅將 D1，D0換成了A1’，A0’，對(duì)于 N 個(gè)字節(jié)的數(shù)據(jù)，則有n次結(jié)構(gòu)相同的迭代運(yùn)算，設(shè)單字節(jié)第 n 次的查表法計(jì)算所得余數(shù)為 PA(n)，則第n次的余數(shù)為:

式（1）解釋如下:d 為第 n-1 次的余數(shù)的高 8 bit值，d=(PA(n-1)＞＞8)^D(n)

第 n-1 次余數(shù)的高 8 bit在由單字節(jié)查表算出后，還需與雙字節(jié)原始數(shù)據(jù)的低字節(jié) D(n)異或。

第 n 次余數(shù)值先由第 n-1 次余數(shù)的高 8 bit值 d查表算出 f(d)，然后需將 f（d）的高 8 bit與第 n-1次 余 數(shù) 的 低 8 bit PA（n-1） 異 或（ 類 比 前 述 A1’=D0^HA1’），異或前先將 PA（n-1）左移 8 bit以便與 f（d）高 8 bit對(duì)齊。

于是總的迭代公式可表示為:

式（2） 中 的 函 數(shù) f(d) 的 實(shí) 現(xiàn) 由 前 述 的 16 bit CRC 查表程序完成。

據(jù)此編寫的計(jì)算多字節(jié)數(shù)據(jù)的 16 bit CRC 值的C語言程序如下:

上面的 程 序 中，0x7d3b 為 16 bit生成多項(xiàng)式，首先調(diào)用 BuildTable16 函數(shù)建立信息碼 -校驗(yàn)碼的對(duì)照表 CRCTable1，然后在 CRC_16 函數(shù)中可迭代查表。*aData 為指向一個(gè)單字節(jié)數(shù)據(jù)的指針，aSize 則為總共的字節(jié)個(gè)數(shù)。

利用上述的多字節(jié)迭代查表算法，可以求出整數(shù)個(gè)字節(jié)的數(shù)據(jù)的CRC校驗(yàn)碼，當(dāng)除數(shù)（生成多項(xiàng)式）為 16 bit時(shí)，相應(yīng)的余數(shù)（CRC 校驗(yàn)碼）也為雙字節(jié) 16 bit數(shù)。這樣，對(duì)于 0x0000～0xFFFF 范圍內(nèi)的每一個(gè)數(shù)據(jù)，都有唯一對(duì)應(yīng)的CRC校驗(yàn)碼，組合起來可以構(gòu)成冗余編碼值用于冗余編碼運(yùn)算。

在 iLOCK 聯(lián)鎖系統(tǒng)中采用了雙字節(jié)的數(shù)據(jù)及其CRC 校驗(yàn)碼共同組成冗余碼字，進(jìn)行 NISAL 碼字運(yùn)算。為了提高運(yùn)算效率，將上述的多字節(jié)迭代CRC查表算法引入到 iLOCK 聯(lián)鎖系統(tǒng)的冗余碼字校驗(yàn)中。方法說明如下:

假 設(shè) 一 個(gè) 4 字 節(jié) 的 冗 余 碼 字 為 D（DH，DL），其中 DL為原始數(shù)據(jù)位，DH 為其 CRC校驗(yàn)碼，則可采用上述的多字節(jié)迭代CRC查表算法檢驗(yàn)DH是否為DL所對(duì)應(yīng)的正確的CRC值，以下程序中aData[0],aData[1] 分別為 DL 雙字節(jié)數(shù)據(jù)位的高、低字節(jié)，通過雙字節(jié)的迭代CRC查表法，算出CRC值 DH，左移 16 bit后，再與 DL 組合為最終的結(jié)果值 result，判斷 result如果與 D 相同，則通過校驗(yàn)，否則不通過。

3 CRC查表法的推廣——非整數(shù)字節(jié)的任意信息位編碼的查表及其在iLOCK聯(lián)鎖系統(tǒng)中的應(yīng)用

以上敘述了通用的CRC算法及查表法，以及基于該表格的多字節(jié)的迭代 CRC查表運(yùn)算。更多字節(jié)（如 32 bit）的 CRC 查表法可依此類推。該算法已成功被應(yīng)用到 iLOCK 聯(lián)鎖系統(tǒng)的冗余編碼運(yùn)算中，極大地改善了采用傳統(tǒng)移位算法進(jìn)行CRC運(yùn)算的計(jì)算效率。

除了上述CRC應(yīng)用外，在編碼領(lǐng)域，大量的場(chǎng)合還需要用到非整數(shù)個(gè)字節(jié)的數(shù)據(jù)的CRC冗余編碼，例如 :7 bit原始數(shù)據(jù)位，15 bit數(shù)據(jù)位等。本文將要證明在非規(guī)則的多項(xiàng)式除法運(yùn)算的情況下，非整數(shù)個(gè)字節(jié)的數(shù)據(jù)位編碼也可采用類似上面的規(guī)則多項(xiàng)式除法和整數(shù)個(gè)字節(jié)的方法實(shí)現(xiàn)查表法求取校驗(yàn)碼字，并給出相關(guān)的實(shí)現(xiàn)程序。隨后，同樣將這類非整數(shù)個(gè)字節(jié)的 CRC 編碼運(yùn)算應(yīng)用到 iLOCK 系統(tǒng)的冗余編碼運(yùn)算中。

圖1 為非規(guī)則的 7 bit移位 CRC 算法，一個(gè) 4 字節(jié)的 32 bit原始數(shù)據(jù)左移 7 bit（在其后添加 7 個(gè) 0）后再與 32 bit生成多項(xiàng)式 aPoly 進(jìn)行多項(xiàng)式除法運(yùn)算，最終的 7 步除法后的余數(shù)（32 bit）即為此非規(guī)則的CRC校驗(yàn)碼值。

圖1 非規(guī)則的7位移位CRC算法

這種非整數(shù)字節(jié)的移位CRC算法參照前述的CRC算法，可用以下的代碼實(shí)現(xiàn) :

以下將證明，上述的按位移位的CRC算法仍然可以采用查表法來實(shí)現(xiàn)，說明如下:

將原始數(shù)據(jù)D分拆為高低兩部分?jǐn)?shù)據(jù)，高位數(shù)據(jù) DH 為 7 bit(hhhhhhh)，低位數(shù)據(jù) DL 為 25 bit(lllll llllllllllllllllllll)，則僅僅高位數(shù)據(jù)的多項(xiàng)式除法運(yùn)算可表示為:

根據(jù)函數(shù)中定義的邏輯運(yùn)算規(guī)則知，每一步運(yùn)算中P是直接移位還是要進(jìn)行異或運(yùn)算，取決于每步移位操作中的最高位，實(shí)際上就是高位數(shù)據(jù)DH的各位狀態(tài)，故上面的實(shí)際數(shù)據(jù)D的運(yùn)算和高位數(shù)據(jù)H 的運(yùn)算過程中，由于高 7 bit均為 H，故總共 7 步除法的移位/異或操作過程相同。將上兩個(gè)運(yùn)算的余數(shù) A，A’分別拆為 A1、A0 和 A1’、A0’，A1,A1’為余數(shù)的高 25 bit，A0、A0’為余數(shù)的低 7 bit，則由于 A0，A0’所對(duì)應(yīng)的原始數(shù)據(jù)都為補(bǔ)齊的 7 個(gè) 0，故 A0=A0’，而 A1 和 A1’所對(duì)應(yīng)的原始數(shù)據(jù)分別為 DL（25 bit低位數(shù)據(jù)）和 0，且有 :

A1=DL^p1^p2…^p7，A1’=0^p1^p2…^p7。由于兩種運(yùn)算中高 7 bit數(shù)據(jù) DH 相同，故 7 步除法中的移位 /異或操作過程相同，從而 7步運(yùn)算的異或值p1～p7 在兩種運(yùn)算中相同，又 data=data^0。故有 :

A1=DL^0^p1^p2 … ^p7=D L^(0^p1^p2 …^p7)=DL^A1’。

即 :原始數(shù)據(jù)的余數(shù)的高 25 bit值等于原始數(shù)據(jù)的高 7 bit數(shù)據(jù)的余數(shù)與其低 25 bit數(shù)據(jù)相異或，而原始數(shù)據(jù)的余數(shù)的低 7 bit值就是原始數(shù)據(jù)高 7 bit數(shù)據(jù)的余數(shù)值的低 7 bit值。

DH的余數(shù)A’在生成多項(xiàng)式確定的情況下，只隨著DH的改變而改變，于是可以遵循上面的運(yùn)算規(guī)則生成一張 DH 與其余數(shù) A1’相對(duì)應(yīng)表格。采用查表法計(jì)算上述冗余編碼的程序可表示為:

計(jì)算最終的原始數(shù)據(jù)的余數(shù)時(shí)，再將上述查表結(jié)果 A’^（DL＜＜7）, 即可求出 A。其低 7 bit就是A’的低 7 bit，高 25 bitA’需要與原始信息位的低25 bit異或（需左移 7 bit以對(duì)齊），最終高低位拼起來就組成了A。利用生成的表格進(jìn)行查表運(yùn)算和后續(xù)處理的函數(shù)為:

以上非規(guī)則的移位 CRC 算法同樣被用于 iLOCK聯(lián)鎖系統(tǒng)中的冗余編碼運(yùn)算中，從而大幅度提高了運(yùn)算效率，使得整體的冗余編碼運(yùn)算速度大幅度加快，從而提高了 iLOCK 系統(tǒng)的整體性能。

4 結(jié)束語

循環(huán)冗余編碼CRC校驗(yàn)算法被廣泛應(yīng)用于各種數(shù)據(jù)校驗(yàn)中。用軟件實(shí)現(xiàn)的CRC算法效率較低，在實(shí)際應(yīng)用中需要通過查表法來提高運(yùn)算效率。本文基于單字節(jié)信息位的 16 bit CRC 冗余碼，建立了 16 bit的CRC表，并且推導(dǎo)了基于該CRC表進(jìn)行多字節(jié)查表的算法，將其應(yīng)用于 iLOCK 聯(lián)鎖系統(tǒng)的下位機(jī)冗余編碼運(yùn)算中，經(jīng)過理論推導(dǎo)，進(jìn)一步將整數(shù)字節(jié)的查表法推廣至任意位數(shù)信息位的查表算法，相關(guān)的算法也應(yīng)用到了 iLOCK 聯(lián)鎖系統(tǒng)的冗余編碼運(yùn)算中。經(jīng)測(cè)試，查表算法的應(yīng)用能大幅度提高冗余編碼計(jì)算效率，提高 iLOCK 系統(tǒng)的整體性能。

[1] 沙 依（美）.數(shù)據(jù)通信與網(wǎng)絡(luò)教程 [M].高傳善 ,譯 .北京：機(jī)械工業(yè)出版社，2000.

[2] 楊萃南 .數(shù)字電子技術(shù)與邏輯設(shè)計(jì)教程 [M].北京 ：電子工業(yè)出版社，2003（4）.

[3] 姜堅(jiān)華 .iLOCK 的安全模型和安全性分析 [J]. 鐵道通信信號(hào)，2010（7）.

[4] 呂永昌，林瑜筠 . 計(jì)算機(jī)聯(lián)鎖 [M]. 北京 ：中國(guó)鐵道出版社，2007（4）.

[5] 馮翔宇 .循環(huán)冗余校驗(yàn)碼 CRC 算法分析與實(shí)現(xiàn) [J].中國(guó) 科技信息，2010（21）.

責(zé)任編輯 方 圓

CRC table look-up method’s extension and its application in iLOCK Interlocking System

DONG Gaoyun, SUN Junfeng
( Casco Signal LTD., Shanghai 200071, China )

The ef ciency of CRC Code Veri cation Algorithm was improved by CRC Table Lookup Algorithm of integer byte. The derivation showed that the traditional CRC Table Lookup Algorithm for 16 bit or 32 bit of integer byte could be extended to less than 16 bit or 32 bit of non integer byte of arbitrary. Two kinds of CRC Table Lookup Algorithm were successfully applied to the redundant coding calculation in iLOCK Interlocking System, greatly improved the ef ciency of the redundant coding calculation. So the total performance of iLOCK System was improved.

CRC; Table Lookup Algorithm; computer interlocking; redundant coding

U284.3∶TP39

：A

1005-8451（2015）01-0040-06

2014-01-23

董高云，高級(jí)工程師；孫軍峰，高級(jí)工程師。