應(yīng)答器報(bào)文硬件和軟件CRC校驗(yàn)對比分析

朱衛(wèi)華 張 奇

朱衛(wèi)華:西門子信號有限公司 工程師 710016 西安

張 奇:西門子信號有限公司 工程師 710016 西安

1 應(yīng)答器

地-車信息傳輸系統(tǒng)是列車運(yùn)行控制系統(tǒng)的核心構(gòu)成部分之一。車載列控設(shè)備需要獲取從列車控制中心發(fā)送的臨時(shí)限速命令、前方線路的允許速度、線路坡度、區(qū)段長度等信息，從而對高速行駛列車進(jìn)行自動控制。

應(yīng)答器(Balise)作為地-車信息傳輸通道中的地面信息傳輸載體，廣泛應(yīng)用在我國高鐵領(lǐng)域。主要用途是向列控車載設(shè)備提供可靠的地面固定信息和可變信息。應(yīng)答器分為固定(無源)應(yīng)答器和可變(有源)應(yīng)答器。當(dāng)應(yīng)答器被車載天線激活后，將持續(xù)的發(fā)送存儲在其內(nèi)部的報(bào)文，從而將地面信息傳遞給車載設(shè)備。

2 報(bào)文CRC校驗(yàn)

CRC即循環(huán)冗余校驗(yàn)碼(Cyclic Redundancy Check)，是數(shù)據(jù)通信領(lǐng)域中最常用的一種差錯(cuò)校驗(yàn)碼，為了保證地面到車載設(shè)備傳輸信息的正確，應(yīng)答器報(bào)文系統(tǒng)采用75位的CRC校驗(yàn)。當(dāng)車載設(shè)備接收到報(bào)文數(shù)據(jù)后，需要對報(bào)文CRC校驗(yàn)和解碼，從而獲得正確的報(bào)文。75位CRC校驗(yàn)是整個(gè)報(bào)文接收過程中最復(fù)雜和關(guān)鍵的環(huán)節(jié)，為此介紹CRC校驗(yàn)的編碼策略、軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)，以及各自特點(diǎn)，為開發(fā)報(bào)文CRC校驗(yàn)?zāi)K提供參考。

2.1 編碼策略

FFFS編碼策略(Form Fit Function Specification Coding Strategy)是由EUROSIG聯(lián)盟為推進(jìn)歐洲鐵路信號標(biāo)準(zhǔn)化而制定的標(biāo)準(zhǔn)，它定義了應(yīng)答器報(bào)文的格式。報(bào)文格式對隨機(jī)位錯(cuò)誤、突發(fā)錯(cuò)誤、位滑動和位插入，以及它們的所有組合設(shè)計(jì)有完全的安全性證明。應(yīng)答器長報(bào)文原始數(shù)據(jù)為830位，經(jīng)過加擾和編碼后，產(chǎn)生了1023位的數(shù)據(jù)。在該數(shù)據(jù)循環(huán)發(fā)送的過程中從任意字節(jié)開始取1023位可以被編碼的多項(xiàng)式整除。利用報(bào)文的這個(gè)特點(diǎn)，可以采用多項(xiàng)式除法(模2除法)對報(bào)文進(jìn)行CRC校驗(yàn)。取1023位長度的報(bào)文數(shù)據(jù)M(x)，表示為:校驗(yàn)公式G(x)的最高次數(shù)為75，表示為:

以G(x)為模對M(x)作模運(yùn)算，表示為:

其中Q(x)和R(x)分別是商和余項(xiàng)。

當(dāng)CRC余數(shù)R(x)為零時(shí)，說明報(bào)文數(shù)據(jù)CRC校驗(yàn)正確，非零表示存在位錯(cuò)誤，重新選1023位數(shù)據(jù)進(jìn)行校驗(yàn)。

2.2 軟件算法

隨著微處理器的不斷發(fā)展，及高速低功耗處理器的不斷推出，使用軟件進(jìn)行CRC校驗(yàn)成為可能。軟件算法主要有程序法、查表法和眾多優(yōu)化設(shè)計(jì)。限于篇幅這里只列出程序法和查表法2種方法。

2.2.1 程序法(比特型算法)

1．將1023位數(shù)據(jù)流高75位(先收到的為高)放入一個(gè)長度為75位的寄存器。

2．如果寄存器的首位為1，則與生成多項(xiàng)式G(x)做異或運(yùn)算;否則僅將寄存器左移1位(寄存器的最低位從下一個(gè)字節(jié)獲得)。

3．重復(fù)第2步，直到數(shù)據(jù)流(1023位)全部移入寄存器。

4．寄存器中的值為全0則報(bào)文CRC校驗(yàn)正確，否則報(bào)文存在錯(cuò)位，繼續(xù)下一個(gè)1023位的檢驗(yàn)。

該算法通過左移位和異或運(yùn)算來完成模2除法運(yùn)算。原理簡單易懂，易于維護(hù)和更新。對1023位數(shù)據(jù)完成一次CRC校驗(yàn)，大概需要1023－75=948次移位運(yùn)算，和948×75=71100次異或運(yùn)算(最不利情況下)。

2.2.2 查表法(字節(jié)型算法)

1．75位的CRC寄存器組初始化為全“0”。注意:CRC寄存器組初始化全為1時(shí)，最后CRC應(yīng)取反。

2．CRC寄存器組向左移8位，并保存到CRC寄存器組。

3．原CRC寄存器組高8位(右移8位)與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。

4．索引所指的表值與CRC寄存器組做異或運(yùn)算。

5．?dāng)?shù)據(jù)指針加1，如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟2。

6．1023位全部處理完畢后，寄存器中的值為全0則報(bào)文CRC校驗(yàn)正確，否則報(bào)文存在錯(cuò)位，繼續(xù)下一個(gè)1023位的檢驗(yàn)。

字節(jié)型算法一次移出待測數(shù)據(jù)的8位，即一次進(jìn)行一個(gè)字節(jié)的計(jì)算，則余數(shù)表格有28=256個(gè)表值，每個(gè)表值為75位。對1023位數(shù)據(jù)完成一次CRC校驗(yàn)大概需要1024/8=128次移位運(yùn)算、128次查表運(yùn)算和128×8+128×75=10624次異或運(yùn)算。

2.3 硬件算法

在硬件中實(shí)現(xiàn)該過程需要使用移位寄存器(CRC寄存器)。該移位寄存器長度為75位。圖1為實(shí)現(xiàn)該算法的線性反饋移位寄存器(LFSR)的框圖。

報(bào)文CRC校驗(yàn)過程如下。

1．初始化75位CRC寄存器。

2．每次獲取報(bào)文位后，將輸入數(shù)據(jù)和上一次異或運(yùn)算的結(jié)果組成新的數(shù)據(jù)，進(jìn)行循環(huán)異或運(yùn)算。

3．?dāng)?shù)據(jù)未滿1023則返回步驟2，收到1023位數(shù)據(jù)后，判斷CRC寄存器內(nèi)的值。如果余數(shù)為0，則表示收到的1023位報(bào)文可以被75位多項(xiàng)式整除，可以進(jìn)一步判斷1023位是否為正式報(bào)文;如果余數(shù)非0，則表示不能整除，該1023位存在錯(cuò)位。

以上即為單線程的CRC校驗(yàn)算法原理。為了能夠及時(shí)收到正確的報(bào)文，達(dá)到接收1位報(bào)文數(shù)據(jù)就可以判斷整個(gè)1023數(shù)據(jù)流是否滿足CRC校驗(yàn)，可以采用如下2種方式進(jìn)行實(shí)現(xiàn)。

方式1:并行設(shè)計(jì)。

在設(shè)計(jì)CRC校驗(yàn)時(shí)，將報(bào)文數(shù)據(jù)同時(shí)輸入到1023路CRC校驗(yàn)電路中，每路信號開始校驗(yàn)的時(shí)間依次后移1位。該方法理論上對于數(shù)據(jù)可以做到1位數(shù)據(jù)就可以計(jì)算出整個(gè)數(shù)據(jù)段的CRC校驗(yàn)碼，但是，由于每位CRC寄存器的值都是由有效數(shù)據(jù)位和CRC寄存器的前一個(gè)狀態(tài)組成的異或電路運(yùn)算所得，并且需要1023個(gè)相差1位的硬件電路，硬件單元使用較多。筆者以ACTEL公司的FPGA工作頻率40 MHz為例，制作的單一線程CRC校驗(yàn)需要消耗大概500個(gè)硬件單元，1023路需要消耗大概511500個(gè)硬件單元。

方式2:并行優(yōu)化設(shè)計(jì)。

應(yīng)答器報(bào)文以565 kb/s速率按位進(jìn)行串行傳輸，因此一個(gè)數(shù)據(jù)周期為1.77 μs。而現(xiàn)有的FPGA等硬件設(shè)備的工作頻率均遠(yuǎn)遠(yuǎn)高于報(bào)文傳輸速率。以頻率為40 MHz的FPGA為例，其工作周期為0.025 μs，在等待接收1位報(bào)文數(shù)據(jù)的過程中，F(xiàn)PGA可以進(jìn)行大概70次運(yùn)算，由于1023次移位運(yùn)算即可判斷CRC校驗(yàn)的正確性，因此單線程計(jì)算一次CRC的過程內(nèi)可以收到15位報(bào)文數(shù)據(jù)。為了實(shí)現(xiàn)1位數(shù)據(jù)即可判斷CRC正確性，需要擴(kuò)展到15線程，如圖2所示。

圖2 15線程循環(huán)校驗(yàn)

接收到1位數(shù)據(jù)與前1022位構(gòu)成M(x)1，將該1023位數(shù)據(jù)輸入一路CRC校驗(yàn)電路;再接收到1位數(shù)據(jù)與前1022位構(gòu)成M(x)2，同樣輸入一路CRC校驗(yàn)電路，直到M(x)15，一共15個(gè)CRC校驗(yàn)線程。這樣當(dāng)?shù)贛(x)1數(shù)據(jù)CRC校驗(yàn)完畢后，可以繼續(xù)接收數(shù)據(jù)重新構(gòu)成新的M(x)1，周而復(fù)始，每收到一位數(shù)據(jù)都可以計(jì)算出CRC校驗(yàn)的結(jié)果。

一路CRC校驗(yàn)需要消耗500個(gè)硬件單元，15路則需要消耗7500個(gè)硬件單元。

3 軟件校驗(yàn)和硬件校驗(yàn)對比分析

3.1 用時(shí)對比

以軟件校驗(yàn)使用40 MHz主頻的MCU為例，且2個(gè)時(shí)鐘周期為一個(gè)指令周期，則一個(gè)指令周期大概為0.05 μs。在接收滿1023位報(bào)文后，比特型算法大概需要(948+71100) ×0.05=3.602 ms可以計(jì)算出CRC余數(shù);字節(jié)型算法大概需要(128+128×256/2+10624) ×0.05=1.356 ms可以計(jì)算出CRC余數(shù)。實(shí)際設(shè)計(jì)中由于軟件為串行處理機(jī)制，因此用時(shí)會大于估算結(jié)果。

硬件校驗(yàn)以使用40 MHz主頻的FPGA為例，則并行設(shè)計(jì)和優(yōu)化的并行設(shè)計(jì)每隔1.77 μs即可以校驗(yàn)一個(gè)1023位數(shù)據(jù)。

由此可見軟件校驗(yàn)的運(yùn)算時(shí)間保持在毫秒的數(shù)量級，而硬件則保持在微秒的數(shù)量級。

3.2 占用資源對比

軟件校驗(yàn)可以集成在MCU的程序內(nèi)，查表法需要占用75×255=19125位的程序存儲空間來放置余數(shù)表。軟件設(shè)計(jì)的靈活性高，可移植性強(qiáng)，且修改方便。

硬件校驗(yàn)需要相應(yīng)的硬件電路作為支持，設(shè)計(jì)復(fù)雜。1023線程的并行設(shè)計(jì)方案占用大量硬件資源，在不要求1位即可校驗(yàn)的情況下，可以通過減少線程的方式來降低硬件資源的消耗。優(yōu)化的并行設(shè)計(jì)方案需要15路并行校驗(yàn)代碼，消耗大概7500個(gè)硬件單元。

3.3 實(shí)時(shí)性對比

軟件一次CRC校驗(yàn)時(shí)間遠(yuǎn)遠(yuǎn)大于1.77 μs的報(bào)文接收時(shí)間，因此不能達(dá)到同步校驗(yàn)。校驗(yàn)延時(shí)將隨報(bào)文接收誤碼的增多而逐漸累積，例如報(bào)文內(nèi)存在1000位誤碼，則校驗(yàn)時(shí)間將大于1 s。因此軟件校驗(yàn)實(shí)時(shí)性差。硬件校驗(yàn)1.77 μs內(nèi)即可判斷數(shù)據(jù)的CRC是否正確，并且對報(bào)文接收誤碼沒有時(shí)間積累，能夠達(dá)到同步校驗(yàn)，因此實(shí)時(shí)性最好。

4 結(jié)束語

軟件CRC校驗(yàn)占用資源較少，設(shè)計(jì)簡單、靈活，代碼可移植性強(qiáng)，修改方便。但由于校驗(yàn)用時(shí)較長，且存在延時(shí)積累，導(dǎo)致實(shí)時(shí)性差，因此可以應(yīng)用在對實(shí)時(shí)性要求不高的場合，比如使用便攜式手持設(shè)備對報(bào)文讀取測試等場合。

硬件CRC校驗(yàn)需要相應(yīng)的硬件電路，設(shè)備成本較高，設(shè)計(jì)復(fù)雜。通過減少并行設(shè)計(jì)的線程數(shù)可以在校驗(yàn)時(shí)間和資源占用之間進(jìn)行適當(dāng)平衡;優(yōu)化并行設(shè)計(jì)方案，需要硬件時(shí)鐘周期和報(bào)文傳輸時(shí)鐘周期的配合，對硬件電路的設(shè)計(jì)精度和可靠性要求較高，但占用資源較少，可以做到同步校驗(yàn)，實(shí)時(shí)性好，可以應(yīng)用在車載報(bào)文傳輸通道等設(shè)備上。

針對不同的使用場合，應(yīng)該合理的選擇報(bào)文CRC校驗(yàn)的方法，以達(dá)到速度、資源和成本的平衡，使設(shè)計(jì)達(dá)到最優(yōu)化。

［1］肖甜，趙會兵.歐洲應(yīng)答器編碼策略的安全性研究［J］.鐵道學(xué)報(bào)，2008.

［2］朱榮華.一種CRC并行計(jì)算原理及實(shí)現(xiàn)方法［J］.電子學(xué)報(bào)，1999.

［3］李劍峰.新的高性能CRC查表算法［J］.計(jì)算機(jī)應(yīng)用，2011(6).

［4］張樹剛，張遂南，黃士坦.CRC校驗(yàn)碼并行計(jì)算的FPGA實(shí)現(xiàn)［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2007.

［5］徐寧，楊志杰.歐洲應(yīng)答器報(bào)文譯碼的研究以及FPGA實(shí)現(xiàn)［J］.鐵路通信信號，2008.