基于冗余編碼系統(tǒng)的循環(huán)冗余校驗(yàn)方法

夏 偉 蔣建金 傅林泰 張 磊

(卡斯柯信號(hào)有限公司，200071，上海//第一作者，工程師)

列車自動(dòng)控制(ATC)系統(tǒng)是由列車自動(dòng)保護(hù)(ATP)系統(tǒng)、列車自動(dòng)監(jiān)控(ATS)系統(tǒng)、列車自動(dòng)運(yùn)行(ATO)系統(tǒng)和計(jì)算機(jī)聯(lián)鎖系統(tǒng)組成[1]，對(duì)列車運(yùn)行速度、運(yùn)行間隔和運(yùn)行方向等進(jìn)行控制，保證列車安全、高效運(yùn)行。這些系統(tǒng)大多在設(shè)計(jì)時(shí)需要采用安全冗余編碼技術(shù)來提高系統(tǒng)的安全性，使系統(tǒng)達(dá)到SIL4安全完整性等級(jí)。

循環(huán)冗余校驗(yàn)(CRC)是通信領(lǐng)域常用的一種校驗(yàn)碼，用于檢測(cè)數(shù)據(jù)在傳輸過程中是否發(fā)生了被篡改的錯(cuò)誤。一般的方法是通信雙方定義好計(jì)算多項(xiàng)式和CRC的計(jì)算方法(包括寬度、起始值、結(jié)果異或值、輸入輸出數(shù)據(jù)反轉(zhuǎn)等)，發(fā)送方在對(duì)數(shù)據(jù)計(jì)算后將得出的CRC值附在消息幀后面一起發(fā)送；接收方收到后對(duì)數(shù)據(jù)進(jìn)行同樣的計(jì)算，并將結(jié)果與原始的CRC進(jìn)行比較，來校驗(yàn)數(shù)據(jù)的正確性與完整性。

當(dāng)冗余編碼的列車自動(dòng)控制系統(tǒng)與其它類型冗余編碼或非冗余編碼系統(tǒng)通信時(shí)，需要采用CRC來保證傳輸數(shù)據(jù)的完整性，且只需傳輸高位數(shù)據(jù)，低位冗余碼不參與傳輸。當(dāng)列車自動(dòng)控制系統(tǒng)無故障時(shí)計(jì)算出的冗余碼CRC與標(biāo)準(zhǔn)CRC結(jié)果完全一致，外界系統(tǒng)可校驗(yàn)通過；當(dāng)列車自動(dòng)控制系統(tǒng)存在故障時(shí)，計(jì)算出的冗余碼CRC需要包含故障信息且該故障能被外界檢測(cè)出而拒絕接收?，F(xiàn)有的技術(shù)在發(fā)送消息時(shí)，僅對(duì)高位數(shù)據(jù)進(jìn)行CRC計(jì)算，那么會(huì)導(dǎo)致外界系統(tǒng)無法檢測(cè)到低位數(shù)據(jù)中可能存在的隨機(jī)性失效或故障；收到外界消息時(shí)，如果只是根據(jù)高位數(shù)據(jù)直接計(jì)算出低位冗余碼，那么當(dāng)CRC校驗(yàn)過程失效時(shí)，故障信息將不體現(xiàn)在低位冗余碼中而無法被當(dāng)前系統(tǒng)檢測(cè)。為此，提出了一種安全性高、錯(cuò)誤可檢測(cè)率高、基于冗余編碼的CRC校驗(yàn)方法。

1 冗余編碼技術(shù)

冗余編碼技術(shù)雖然種類多樣，但是編碼形式、安全原理大致相同。每個(gè)變量都是由高位與低位組成，高位為數(shù)據(jù)的信息位，低位為數(shù)據(jù)的校驗(yàn)位，其中低位是由高位、簽名、時(shí)間戳等信息通過預(yù)定義的公式計(jì)算得出，因此每個(gè)變量的高低位之間存在確定的對(duì)應(yīng)關(guān)系。系統(tǒng)在運(yùn)行的每個(gè)周期都會(huì)對(duì)關(guān)鍵變量的高位、低位正確性進(jìn)行校驗(yàn)，用于判斷是否存在內(nèi)存錯(cuò)誤、隨機(jī)性失效等故障。本文采用AN碼、分離碼相結(jié)合的編碼方式[2-3]。對(duì)于簡(jiǎn)單變量x，設(shè)計(jì)其編碼后的形式為：

X=Ax+Bx+DT

式中：

A——編碼時(shí)選擇的大素?cái)?shù)；

Bx——編碼時(shí)為變量x分配的大素?cái)?shù)；

DT——時(shí)間戳。

在實(shí)際編碼中，將長(zhǎng)度為k個(gè)字節(jié)(k=1,2,3,4)的變量分成了高k位和低k位，高k位為數(shù)值域，存放數(shù)據(jù)的原始值，低k位為校驗(yàn)域。

按照這種編碼方法，對(duì)每個(gè)操作數(shù)分配一個(gè)固定的簽名，可以檢測(cè)操作數(shù)尋址簽名錯(cuò)誤和操作符錯(cuò)誤；時(shí)間戳可以檢測(cè)循環(huán)變量值沒有被更新的錯(cuò)誤，或者循環(huán)變量值失效使用上周期變量值的錯(cuò)誤。

2 CRC技術(shù)

CRC校驗(yàn)技術(shù)是一種十分有效的錯(cuò)誤檢測(cè)技術(shù)，能檢驗(yàn)一位錯(cuò)、雙位錯(cuò)、所有的奇數(shù)錯(cuò)、所有長(zhǎng)度小于或等于所用的生成多項(xiàng)式長(zhǎng)度的錯(cuò)誤。如采用16位生成多項(xiàng)式的CRC校驗(yàn)，對(duì)17位以上的檢錯(cuò)率高達(dá)99.997%[4]，32位生成多項(xiàng)式的出錯(cuò)概率比16位低10-5倍[5]，因此CRC 32更適用于重要數(shù)據(jù)的傳輸，在軌道交通列車自動(dòng)控制系統(tǒng)中得到廣泛應(yīng)用。文獻(xiàn)[6-8]中對(duì)查表法CRC校驗(yàn)的原理做了詳細(xì)闡述。

3 基于冗余編碼的CRC校驗(yàn)方法

針對(duì)現(xiàn)有技術(shù)無法實(shí)現(xiàn)對(duì)列車信號(hào)控制系統(tǒng)中冗余碼進(jìn)行CRC校驗(yàn)以及無法利用CRC校驗(yàn)碼與外界冗余/非冗余編碼系統(tǒng)進(jìn)行通信的問題，提出一種基于冗余編碼系統(tǒng)的CRC校驗(yàn)方法：

1)對(duì)發(fā)送消息進(jìn)行編碼。通過將冗余碼校驗(yàn)信息融合到CRC校驗(yàn)計(jì)算過程中，在無故障的情況下得出的CRC校驗(yàn)碼與標(biāo)準(zhǔn)CRC完全一致，保證了正常的通信功能；在列車信號(hào)控制系統(tǒng)發(fā)生故障的情況下能夠?qū)㈠e(cuò)誤信息反饋到編碼CRC校驗(yàn)碼中，外界冗余/非冗余系統(tǒng)可校驗(yàn)出故障信息。

2)收到外界消息，根據(jù)消息中的CRC校驗(yàn)碼和高位數(shù)據(jù)對(duì)該消息進(jìn)行解碼校驗(yàn)，校驗(yàn)結(jié)果加入最終生成的低位冗余碼，保證了傳輸過程中任何故障可以被編碼系統(tǒng)及時(shí)檢測(cè)出。

該方法實(shí)現(xiàn)步驟包括離線數(shù)據(jù)準(zhǔn)備模塊、編碼模塊和解碼模塊三個(gè)部分。

3.1 離線數(shù)據(jù)準(zhǔn)備模塊

離線配置工具輸入的文件有msgType.xml(定義所有消息的格式，每條消息中包含的具體變量，每個(gè)變量的長(zhǎng)度)和signature.txt(包含所有變量的簽名)。

離線配置工具需要根據(jù)輸入文件計(jì)算每條消息中每個(gè)變量簽名數(shù)據(jù)的補(bǔ)償值。由于在計(jì)算CRC時(shí)需要同時(shí)進(jìn)行低位冗余碼的計(jì)算，因此需要根據(jù)具體CRC的多項(xiàng)式和計(jì)算方法，計(jì)算每個(gè)變量的簽名補(bǔ)償值表，用于在CRC計(jì)算時(shí)抵消低位冗余碼信息。簽名補(bǔ)償值的計(jì)算公式如下：

Smod=(S∧M)×Pk-1

式中：

S——原始簽名；

Smod——簽名補(bǔ)償值；

M——CRC 32多項(xiàng)式對(duì)應(yīng)的掩碼；

P——多項(xiàng)式轉(zhuǎn)換成的32位矩陣；

k——變量長(zhǎng)度，支持1-4 B。

簽名計(jì)算完成需要進(jìn)行校驗(yàn)，校驗(yàn)的方法是進(jìn)行反向計(jì)算，逆推原簽名。如果校驗(yàn)失敗，則終止輸出；校驗(yàn)成功后輸出的bin文件中應(yīng)包含：每條消息的格式，每條消息中每個(gè)變量對(duì)應(yīng)的簽名補(bǔ)償值，臨時(shí)接收簽名TempSig_rcv(跟Sig_nature保持常量差Constant_1)。離線配置工具處理如圖1所示。

圖1 離線配置工具處理流程圖

3.2 編碼模塊

冗余編碼系統(tǒng)中所有待發(fā)送消息的變量均采用編碼技術(shù)，包含高位和低位數(shù)據(jù)。由于冗余碼無法直接轉(zhuǎn)換為CRC，在編碼時(shí)(即計(jì)算CRC的過程)，會(huì)同時(shí)對(duì)每個(gè)變量的高位、低位進(jìn)行校驗(yàn)，如果發(fā)現(xiàn)冗余碼故障或在編碼過程中發(fā)生隨機(jī)性失效，那么該錯(cuò)誤信息將會(huì)被融合于CRC計(jì)算過程，得到錯(cuò)誤的CRC校驗(yàn)碼，外部系統(tǒng)可以檢測(cè)出該故障信息。處理流程如圖2所示。

圖2 發(fā)送消息編碼處理流程圖

具體步驟為：

1) 從配置bin文件中獲取當(dāng)前變量的長(zhǎng)度。

2) 查表法依次計(jì)算當(dāng)前變量的每個(gè)字節(jié)的CRC值。

3) 查找簽名補(bǔ)償值表，計(jì)算當(dāng)前變量當(dāng)前字節(jié)簽名對(duì)應(yīng)的補(bǔ)償值。

4) 根據(jù)當(dāng)前變量的長(zhǎng)度判斷當(dāng)前變量CRC計(jì)算是否結(jié)束，如未結(jié)束則執(zhí)行步驟2)，如結(jié)束則根據(jù)當(dāng)前變量的整體簽名補(bǔ)償值、高位數(shù)據(jù)、低位冗余碼、時(shí)間戳(TimeStamp)進(jìn)行校驗(yàn)。當(dāng)數(shù)據(jù)正確時(shí)校驗(yàn)結(jié)果應(yīng)為0；如果校驗(yàn)結(jié)果非0，則表示存在故障。將每個(gè)變量的校驗(yàn)結(jié)果信息異或到編碼CRC值。

5) 判斷當(dāng)前消息所有變量是否都已計(jì)算結(jié)束，如未結(jié)束執(zhí)行步驟1)，如已結(jié)束則返回編碼CRC值作為最終結(jié)果。

其中步驟3)中一個(gè)變量的某個(gè)字節(jié)CRC補(bǔ)償值的計(jì)算公式為：

Scmp[x]=(T[xk]-1×2k1×8)MOD(A)

式中：

xk——該字節(jié)的數(shù)值，范圍為[0, 255]；

T——查表法CRC32計(jì)算表；

k1——變量的第幾個(gè)字節(jié)，范圍為[0, 3]。

3.3 解碼模擬

由于接收到的消息只有高位數(shù)據(jù)和CRC，需要根據(jù)高位數(shù)據(jù)和CRC生成有效的冗余碼。如果數(shù)據(jù)在傳輸過程被篡改或解碼過程發(fā)生隨機(jī)性失效，將導(dǎo)致校驗(yàn)結(jié)果異常，生成的冗余碼包含錯(cuò)誤信息，該錯(cuò)誤會(huì)被系統(tǒng)檢出。在解碼時(shí)，先對(duì)消息進(jìn)行臨時(shí)編碼，將臨時(shí)編碼 CRC與接收CRC進(jìn)行比較，并將校驗(yàn)結(jié)果融合到最終冗余碼的計(jì)算過程。具體為：

1) 根據(jù)配置信息中的TempSig_rcv和收到消息中的高位數(shù)據(jù)計(jì)算出每個(gè)變量的臨時(shí)冗余碼Temp_Redcode，且不包含TimeStamp信息。

2) 根據(jù)Temp_Redcode對(duì)收到的消息進(jìn)行臨時(shí)編碼, 得到臨時(shí)編碼CRC。

3) 將步驟2)中的臨時(shí)編碼CRC與接收CRC進(jìn)行校驗(yàn)比較，并去除步驟1)中常量差Constant_1。如果兩者相等，則校驗(yàn)通過，校驗(yàn)結(jié)果為0；如果兩者不等，則校驗(yàn)不通過，校驗(yàn)結(jié)果非0。

4) 如果步驟3)校驗(yàn)通過，修改步驟1)中每個(gè)變量的Temp_Redcode，異或3.2中步驟3)校驗(yàn)結(jié)果，并加上TimeStamp，作為最終冗余碼結(jié)果輸出。

5) 如果步驟3)校驗(yàn)不通過，返回錯(cuò)誤，不輸出冗余碼；如果發(fā)生隨機(jī)性失效，進(jìn)入步驟4)，輸出的冗余碼會(huì)攜帶步驟3)中的錯(cuò)誤校驗(yàn)結(jié)果，當(dāng)前系統(tǒng)會(huì)檢測(cè)出該故障，處理流程如圖3所示。

圖3 接收消息解碼處理流程圖

4 結(jié)語

采用基于冗余編碼系統(tǒng)的CRC校驗(yàn)方法，可實(shí)現(xiàn)冗余編碼系統(tǒng)與非冗余編碼系統(tǒng)的正常通信，提高系統(tǒng)的通信兼容性，并且有效保證了對(duì)傳輸過程中的錯(cuò)誤信息和系統(tǒng)的隨機(jī)性失效的檢出率。目前該方法已成功應(yīng)用于ATP、ATS等多個(gè)安全產(chǎn)品中。