董高云，孫軍峰

（卡斯柯信號有限公司，上海 200071）

CRC查表法的推廣及其在iLOCK聯鎖系統中的應用

董高云，孫軍峰

（卡斯柯信號有限公司，上海 200071）

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

CRC；查表法；計算機聯鎖；冗余編碼

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

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

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

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

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

CRC 的計算原理說明如下 :

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

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

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

構造上述 16 bitCRC 表的 C 語言程序如下 :

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

2 多字節(jié)CRC迭代查表算法及其在iLOCK聯鎖系統中的應用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

利用上述的多字節(jié)迭代查表算法，可以求出整數個字節(jié)的數據的CRC校驗碼，當除數（生成多項式）為 16 bit時，相應的余數（CRC 校驗碼）也為雙字節(jié) 16 bit數。這樣，對于 0x0000～0xFFFF 范圍內的每一個數據，都有唯一對應的CRC校驗碼，組合起來可以構成冗余編碼值用于冗余編碼運算。

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

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

3 CRC查表法的推廣——非整數字節(jié)的任意信息位編碼的查表及其在iLOCK聯鎖系統中的應用

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

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

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

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

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

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

將原始數據D分拆為高低兩部分數據，高位數據 DH 為 7 bit(hhhhhhh)，低位數據 DL 為 25 bit(lllll llllllllllllllllllll)，則僅僅高位數據的多項式除法運算可表示為:

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

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

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

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

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

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

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

4 結束語

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

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

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

[3] 姜堅華 .iLOCK 的安全模型和安全性分析 [J]. 鐵道通信信號，2010（7）.

[4] 呂永昌，林瑜筠 . 計算機聯鎖 [M]. 北京 ：中國鐵道出版社，2007（4）.

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

責任編輯 方 圓

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

董高云，高級工程師；孫軍峰，高級工程師。