面向接觸網(wǎng)狀態(tài)監(jiān)測的無線傳感網(wǎng)絡(luò)循環(huán)冗余校驗多項式性能研究

譚 平，毛江峰，丁 進，程劍鋒，趙 陽，強 力，馬吉恩

（1.浙江科技學(xué)院 自動化與電氣工程學(xué)院，浙江 杭州 310023；2.中國鐵道科學(xué)研究院集團有限公司 通信信號研究所，北京 海淀 100081；3.中鐵高鐵電氣裝備股份有限公司 研究中心，陜西 寶雞 721013；4.浙江大學(xué) 電氣工程學(xué)院，浙江 杭州 310027)

接觸網(wǎng)是高速鐵路的關(guān)鍵系統(tǒng)，是高速列車的動力之源，實現(xiàn)接觸網(wǎng)狀態(tài)在線監(jiān)測，對保障高速鐵路行車安全，提升高速鐵路運營效率具有非常重要的意義。面向高速鐵路接觸網(wǎng)監(jiān)測的無線傳感網(wǎng)絡(luò)節(jié)點，具有安裝方便、布線簡單、維護方便等優(yōu)勢，是今后技術(shù)發(fā)展的重要方向［1-2］。接觸網(wǎng)狀態(tài)在線監(jiān)測無線傳感模塊需要滿足五年以上的長壽命周期要求，但高速鐵路沿線無線通信系統(tǒng)種類繁多、電磁環(huán)境復(fù)雜，如何保證無線鏈路中數(shù)據(jù)傳輸?shù)目煽啃院凸?jié)點的能量消耗是十分關(guān)鍵的問題，因此合理設(shè)計用于接觸網(wǎng)在線監(jiān)測的無線傳感模塊通信協(xié)議，以及無線傳感模塊傳輸數(shù)據(jù)包的可靠性校驗都極其重要。較差錯控制編碼方式而言，CRC編碼方式對于均衡能量消耗和誤碼率問題都不失為1 種較好的解決方案，但從充分保障無線傳輸數(shù)據(jù)的完整性與可靠性的角度，還需要繼續(xù)研究CRC的特征多項式性能，以確保選擇的特征多項式位數(shù)合適、運算空間低，從而進一步提升校驗性能。

目前CRC 算法主要通過串、并行算法或查表法實現(xiàn)。如羅宇等［3］將CRC 算法變?yōu)榫仃嚲€性運算，降低運算耗時、節(jié)省資源占用。陳容等［4］和左飛飛等［5］分別提出基于遞推法32 位改進并行算法，大大節(jié)省了硬件資源。王寧平等［6］對查表法進行優(yōu)化，在1 個周期內(nèi)實現(xiàn)CRC 運算。上述方法主要從編譯碼算法實現(xiàn)角度，根據(jù)實際情況兼顧軟硬件配置，提高了CRC 算法的校驗效率，但其應(yīng)用范圍均有一定局限性。

從自身性能來看，CRC的殘余誤差概率（RP）會直接影響校驗結(jié)果。如16 位國際通用特征多項式CRC-ANSI 和CRC-CCITT，在17 位突發(fā)差錯時的糾錯率均為99.997%、18 位及以上時均為99.998%［7］。特征多項式校驗時不同數(shù)據(jù)長度會出現(xiàn)不同殘余誤差概率［8］，分析特征多項式性能因素對校驗特征多項式選取具有指導(dǎo)意義，其殘余誤差概率的計算結(jié)果也具有普遍適用性。Agarwal V K 等［9］推導(dǎo)得到關(guān)于殘余誤差概率合法碼碼重的計算方法。IEC 61784-3［10］給出殘余誤差概率的簡化計算方法。KOOPMAN P等［11］通過最小漢明距離計算殘余誤差概率的方法來選取特征多項式，發(fā)現(xiàn)近似性能特征多項式無法運用簡化模型計算并直接比較出校驗性能，若直接運用原理法計算則步驟復(fù)雜、計算量大［6-7］。

目前CRC 特征多項式的性能理論分析不夠充分，既有文獻尚未形成可快速、準(zhǔn)確選取性能更優(yōu)特征多項式的統(tǒng)一標(biāo)準(zhǔn)。針對這一情況，本文首先建立特征多項式殘余誤差概率計算模型，根據(jù)特征多項式自身性能剖析影響殘余誤差概率的主要因素，提出1 種對任意數(shù)據(jù)長度校驗實現(xiàn)CRC 多項式性能定量評估的計算方法。以設(shè)計接觸網(wǎng)在線監(jiān)測無線傳感模塊數(shù)據(jù)包256 bit 的數(shù)據(jù)位長為驗證對象，先確認(rèn)特征多項式位數(shù)，根據(jù)殘余誤差概率初步分析特征多項式性能，再通過對近似性能多項式位出錯漏檢率的精確計算，最終快速、準(zhǔn)確選取更優(yōu)檢錯性能特征多項式。

1 殘余誤差概率計算

殘余誤差概率也稱為未被檢測錯誤概率（Un?detected Error Probability，Pue）［12］。以k為數(shù)據(jù)碼中待校驗信息碼的位長，r為校驗位長，那么含校驗位的數(shù)據(jù)總位長n=k+r。當(dāng)CRC 多項式校驗數(shù)據(jù)的位長不小于固有長度的2r-1-1 時，此時Pue值與生成特征多項式的選擇無關(guān)，只與該特征多項式的最高階數(shù)r有關(guān)；當(dāng)待校驗數(shù)據(jù)位長小于固定長度2r-1-1 時，校驗碼即為縮短碼，此時Pue值既與特征多項式有關(guān)，又與縮短后的數(shù)據(jù)總位長n有關(guān)。根據(jù)文獻［8］，Pue的通用計算方法有式（1）和式（2）這2種。

式中：Ap為合法碼字中碼重為p的碼字?jǐn)?shù)目，p=0，1，…，n；ε為位出錯概率。

式中：q為有限域元素個數(shù)；Bp為合法對偶碼中碼重為p的碼字?jǐn)?shù)目，p=0，1，…，n。

以二進制對稱信道（BSC）作為一般的信道編碼模型，式（1）和式（2）分別對應(yīng)為式（3）和式（4）。

1.1 殘余誤差概率序列計算方法

校驗位長r越多，特征多項式校驗?zāi)芰υ綇姟５S著待檢數(shù)據(jù)總位長n增加，Ap和Bp的計算復(fù)雜度也會隨之增加。在校驗應(yīng)用的眾多場合中，一般r?k，因此Bp的計算復(fù)雜度遠小于Ap［13］，通過Bp計算殘余誤差概率更為簡便。

以p（x）為不可再被約分的本原多項式，可針對Bp提出1種適用于校驗碼為固有長度或縮短碼的計算方法，生成形式為“（x+1）p（x）”的多項式g（x），該方法具體步驟如下。

1）初始化數(shù)列

設(shè)有數(shù)列Wi（i=0，1，…，n），初始值為：W0取1，數(shù)列中其他項均取0。

2）生成特征序列

根據(jù)線性反饋移位寄存器，生成周期2r-1-1的序列。r-1 級線性反饋移位寄存器運算過程如圖1 所示，主要由移位寄存器和異或門邏輯組成。圖中：白、黑箭頭分別表示數(shù)字流的運行方向和反饋移位寄存器的運算方向。

圖1 r-1級線性反饋移位寄存器運算過程

線性反饋移位寄存器的周期即所產(chǎn)生的碼組長度只與反饋方式有關(guān)。根據(jù)反饋方式，圖1中的線性反饋移位寄存器對應(yīng)的特征方程為［14］

式中：α為第α位寄存器，α∈［0，r-1］；fα為0-1變量，若第α位寄存器參與異或運算，則取值為1，否則取值為0。

此特征方程即為生成的特征多項式g（x）=（x+1）p（x）中的本原多項式p（x）。

對各觸發(fā)器賦初始值，且至少1 個觸發(fā)器的初始值賦為1（若初始狀態(tài)全為0則無法循環(huán)）。定義T時刻的輸出aT是前一時刻狀態(tài)sT-1=(aT-1aT-2…aT-n)和特征多項式系數(shù)矩陣f=(f0f1…fr-1)的轉(zhuǎn)置矩陣的內(nèi)積，即

直到下一循環(huán)周期開始前，依次記下這一周期內(nèi)的全部輸出，即為特征序列。

3）計算Wi

從特征序列最低位開始的n位進行檢驗，若從低位開始的n位中有i個1，則對應(yīng)的Wi須加1。

先將生成的多項式左移1 位，即特征序列的初始最高位移到初始最低位；再檢驗特征序列新的最低n位，可按式（3）運用簡化計算方法實現(xiàn)；重復(fù)上述檢驗步驟，直到特征序列初始最低位從序列最高位移出序列并恢復(fù)至初始狀態(tài)。

式中：Nold和Nnew分別為每次移位前、移位后最低n位中數(shù)字“1”的個數(shù)；u為特征序列每次移位前最低位；v為特征序列移位后的第n位。

4）計算Bp，得到殘余誤差概率后計算結(jié)束

Bp的計算式為

若n為偶數(shù)，則其中Wi自動相加；再將Bp代入式（4），就可以得到相應(yīng)殘余誤差概率Pue的值。

1.2 殘余誤差概率比較

以8 位特征多項式CRC-8，16 位特征多項式CRC-CCITT，32 位特征多項式CRC-32Q 為例，目前國際通用的幾種含x+1 因式的CRC 多項式分解計算方法分別如下［15］。3種計算方法得到的特征多項式都由因式x+1和p（x）組成。

1）8位特征多項式CRC-8

其中，

2）16位特征多項式CRC-CCITT

其中，

3）32位特征多項式CRC-32Q

其中，

對于接觸網(wǎng)狀態(tài)監(jiān)測無線傳感模塊擬設(shè)計256 bit 待校驗數(shù)據(jù)位，3 種計算方法下，計算得到的CRC 多項式殘余誤差概率結(jié)果如仿真軟件截圖如圖2所示。

圖2 待校驗數(shù)據(jù)位長256 bit時3種CRC多項式殘余誤差概率

根據(jù)圖2計算結(jié)果可知：CRC殘余誤差概率隨字節(jié)出錯概率的增加而增長，8 位特征多項式計算結(jié)果最終穩(wěn)定在3.906×10-3，數(shù)量級符合2-8；16位最終穩(wěn)定在1.525×10-5，數(shù)量級符合2-16；32位最終穩(wěn)定在2.328×10-10，數(shù)量級符合2-32。

CRC 多項式校驗時，其待校驗數(shù)據(jù)位長一般都小于2r-1-1位［16］。例如：8位CRC多項式，待校驗數(shù)據(jù)位長一般不超過28-1-1=127 bit；16位一般不超過32 767 bit。因此，對于數(shù)據(jù)位長256 bit 的無線傳感模塊，若選用8 位CRC 校驗碼，待校驗位超過127 bit，漏檢率高，無法保障接觸網(wǎng)監(jiān)測模塊數(shù)據(jù)傳輸可靠性；若選用24位或32位CRC 校驗碼，則校驗效率低，且校驗位占用較多空間，數(shù)據(jù)傳輸有效率降低、運算周期長、資源占用大。綜合對比后，可認(rèn)為16 位CRC 校驗碼更適用于256 bit的數(shù)據(jù)位長校驗。

1.3 影響殘余誤差概率的因素

CRC 校驗碼實際是1 種縮短漢明碼［17］，實際計算過程中，其位出錯概率ε隨合法碼字中碼重為p的碼字?jǐn)?shù)目的增加而增加。為簡化殘余故障概率計算過程，通常采用含最小漢明距離的近似模型進行計算［18］，即

式中：h為最小漢明距離（HD），bit；m為出錯位數(shù)，bit。

式（12）即是近似殘余誤差概率模型。CRC多項式校驗數(shù)據(jù)位長固定的情況下，不同最小漢明距離對應(yīng)多個不同CRC 多項式。仍取待校驗數(shù)據(jù)位長256 bit（其他數(shù)據(jù)位長情況類似），按照16 位CRC 多項式校驗，仿真計算不同最小漢明距離下的殘余誤差概率，發(fā)現(xiàn)最小漢明距離為4時，所有小于4 bit 的錯誤均可被檢測出；同理最小漢明距離為6 時，所有小于6 bit 的錯誤也均可被檢測出。因此選取最小漢明距離分別為4，5 和6 bit，采用MATLAB 進行仿真計算相對應(yīng)的16 位CRC 多項式的殘余誤差概率，仿真結(jié)果如圖3所示。

圖3 待校驗數(shù)據(jù)位長256 bit時不同最小漢明距離對應(yīng)的16位CRC多項式殘余誤差概率

根據(jù)圖3 仿真結(jié)果可知：待校驗數(shù)據(jù)位長256 bit 且字節(jié)出錯概率相同時，最小漢明距離越大殘余誤差概率越小，但最小漢明距離每增加1 bit，計算所需位空間也相應(yīng)增加1 bit；隨BSC 信道位出錯概率增加，不同最小漢明距離下的殘余誤差概率最終都逐漸趨于2-16；若只考慮殘余誤差概率性能因素，位長固定時應(yīng)優(yōu)先選取最小漢明距離較大的特征多項式。

由式（12）可知，殘余誤差概率還與數(shù)據(jù)字節(jié)位數(shù)有關(guān)。取位出錯概率為0.1，最小漢明距離為4 的16 位CRC 多項式，其字節(jié)位數(shù)與殘余誤差概率關(guān)系如圖4所示。

圖4 最小漢明距離為4時16位CRC多項式字節(jié)數(shù)與殘余誤差概率關(guān)系

根據(jù)圖4 可知：隨待校驗位長的增加，殘余誤差概率是1條無限逼近于定值的單調(diào)遞增曲線；數(shù)據(jù)位長在50 bit 以內(nèi)時，數(shù)據(jù)位數(shù)對殘余誤差概率影響很大；數(shù)據(jù)位長大于50 bit 后，這一影響越來越小，殘余誤差概率隨位數(shù)的增加逐漸穩(wěn)定于2-16；待校驗數(shù)據(jù)位長達到256 bit 后，殘余誤差概率已趨于穩(wěn)定。

圖3 和圖4 的結(jié)果均表明，最小漢明距離和數(shù)據(jù)位長均是影響殘余誤差概率的重要因素；數(shù)據(jù)位長的確定，則須結(jié)合最小漢明距離和實際設(shè)計需求選擇合適的特征多項式；多項式殘余誤差概率與待校驗數(shù)據(jù)位長、最小漢明距離、CRC 校驗碼位數(shù)和字節(jié)出錯概率直接相關(guān)。

2 特征多項式檢錯性能定量評估

2.1 特征多項式的精確選取方法

考慮實際高速鐵路沿線復(fù)雜的電磁環(huán)境、電磁干擾嚴(yán)重，信道環(huán)境不夠穩(wěn)定，此時位出錯概率ε維持較高值，不同最小漢明距離對應(yīng)的16 位特征多項式殘余誤差概率都趨于2-16。因此，對256 bit待校驗數(shù)據(jù)位長進行校驗時，選取最小漢明距離為4 的16 位CRC 多項式不僅可獲得與最小漢明距離為6時相似的殘余誤差概率，同時還可節(jié)省更多的位空間。

提出1 種特征多項式的精確選取方法，其具體步驟如圖5所示。首先根據(jù)應(yīng)用場景，對部分適用特征多項式進行初步篩選；之后通過近似殘余誤差概率模型簡單計算，快速選取性能更優(yōu)特征多項式；然后，根據(jù)模型計算結(jié)果，若發(fā)現(xiàn)得到的特征多項式性能接近，則對特征多項式位漏檢率進行精確定量計算，準(zhǔn)確選取更優(yōu)特征多項式。從計算原理可知，此方法計算簡單，且適用于任意數(shù)據(jù)位長校驗時性能更優(yōu)特征多項式的選取。如進行CRC多項式校驗時，可結(jié)合具體應(yīng)用環(huán)境、待校驗位長、信道位出錯率、各特征多項式固定位長對應(yīng)的最小漢明距離及具體漏檢率等因素，運用此方法逐步判斷各特征多項式的檢錯性能優(yōu)劣，便可篩選得到性能更優(yōu)的特征多項式。

圖5 特征多項式選取具體方法

當(dāng)待校驗數(shù)據(jù)位長256 bit、最小漢明距離為4時，CRC-ANSI 多項式、CRC-CCITT 多項式為應(yīng)用最廣泛的2種16位通用特征多項式。其中：前者多用于Modbus和USB 等場景；后者多用于高級數(shù)據(jù)鏈路控制（HDLC）、FCS和藍牙等場景。這2個特征多項式都包含x+1因式，在最小漢明距離、數(shù)據(jù)位長都相同的情況下，計算得到的殘余誤差概率接近，難以根據(jù)近似模型簡化計算并直接比較特征多項式性能優(yōu)劣。針對此類近似性能特征多項式的準(zhǔn)確選取，有必要進一步根據(jù)實際校驗數(shù)據(jù)位長分析各特征多項式位出錯發(fā)生時所有可能的漏檢情況，精確計算不同位長出錯時的漏檢率，定量分析特征多項式校驗性能。

2.2 2種近似性能特征多項式檢錯能力對比

CRC-ANSI 多項式和CRC-CCITT 多項式的性能近似，均可檢測出所有奇數(shù)位錯；待校驗數(shù)據(jù)位長256 bit 時的最小漢明距離均為4。根據(jù)Koop?man P［19］的研究結(jié)果，總數(shù)據(jù)位長272 bit（含16 bit 驗位）時，CRC-ANSI 多項式和CRC-CCITT多項式的檢錯能力見表1。

表1 總數(shù)據(jù)位長272 bit時2種多項式檢錯能力對比

根據(jù)表1，CRC-ANSI 多項式和CRC-CCITT多項式發(fā)生位出錯時，可被完全檢測和未被完全檢測情形一致，因此需對位出錯可被完全檢測出的具體概率和未被完全檢測出的具體概率即漏檢率分別按位定量計算，具體分析特征多項式檢錯性能。

BSC 信道模型中，位出錯漏檢率與待校驗數(shù)據(jù)位長、位出錯率及所選特征多項式有關(guān)。當(dāng)總數(shù)據(jù)位長為n的數(shù)據(jù)中出錯位數(shù)為m時，共有種出錯可能，出錯概率為P(m，ε)=

根據(jù)表1，總數(shù)據(jù)位長272 bit 時，分可被完全檢測和未被完全檢測2 種情況，分別計算2 種特征多項式下位出錯的檢出情況。

1）可被完全檢測時

求和得到2 種特征多項式下，出錯位可被完全檢測的概率P1為

2）未被完全檢測時

根據(jù)Koopman P 的研究結(jié)果，0≤m≤3 或m=2j-1（3≤j≤136）時，am=0，bm=0；m≥4時，對CRC-ANSI 多項式有a4=19 233，a6=18 209 209，a8=20 614 494 970，對CRC-CCITT多項式有b4=6 587，b6=16 262 773，b8=20 437 276 732。

總數(shù)據(jù)位長272 bit 的信息中出錯位數(shù)不少于3 bit 時，CRC-ANSI 多項式下偶數(shù)位出錯的可被檢測概率P2A和漏檢概率Pue，ANSI分別按式（14）和式（15）計算。

總數(shù)據(jù)位長272 bit 的信息中出錯位數(shù)不少于3 bit 時，CRC-CCITT 多項式下偶數(shù)位出錯的可被檢測概率P2C和漏檢概率Pue，CCITT分別按式（16）和式（17）計算。

綜合位出錯可被完全檢測和未被完全檢測2 種情形，得到總數(shù)據(jù)位長272 bit 時，CRC-ANSI 多項式下總檢錯概率PANSI=P1+P2A，即

CRC-CCITT 多項式下總檢錯概率PCCITT=P1+P2C，即

2.3 2種特征多項式漏檢率對比

由式（18）和式（19）可知，特征多項式的漏檢率與其對應(yīng)的漏檢數(shù)直接相關(guān)，CRC-ANSI 多項式與CRC-CCITT 多項式的檢錯能力則分別取決于其位出錯漏檢數(shù)am和bm。

將上述am值代入式（15），得到CRC-ANSI多項式的漏檢率為

將上述bm值代入式（17），得到CRC-CCITT多項式的漏檢率為

根據(jù)上述推算，Pue，ANSI和Pue，CCITT包含0～272 bit 出錯所有可能的漏檢情形。對數(shù)據(jù)位長272 bit時，CRC-ANSI多項式和CRC-CCITT多項式漏檢率仿真計算的結(jié)果如仿真軟件截圖如圖6所示。

圖6 2種特征多項式漏檢率對比

由圖6 可知：2 種特征多項式下漏檢率均隨位出錯概率的增加而增長；當(dāng)位出錯概率ε≤10-3，ε相同時CRC-CCITT 多項式的漏檢率明顯更低；當(dāng)ε>10-3，ε相同時兩者漏檢率趨于相同。因此，在BSC信道模型中，當(dāng)CRC-ANSI多項式和CRCCCITT多項式發(fā)生同種漏檢情形時，CRC-CCITT多項式的整體漏檢率明顯更低。

若出錯位數(shù)為m且m>9 bit時，對應(yīng)的具體漏檢數(shù)未給出，則am和bm值均為此時所有漏檢都發(fā)生情形下的漏檢數(shù)。仍設(shè)出錯位數(shù)為m，假設(shè)此時CRC-CCITT 多項式中所有漏檢情形同時發(fā)生，則Pue，CCITT為CRC-CCITT多項式最大漏檢率，式（21）不變；假設(shè)此時CRC-ANSI 多項式中所有漏檢情形都未發(fā)生，則Pue，ANSI為CRC-ANSI 多項式最小漏檢率，可由此將式（20）變形為

對CRC-CCITT多項式最大可能漏檢率和CRCANSI 多項式最小可能漏檢率進行計算，計算結(jié)果根據(jù)Mathematic仿真軟件截圖如圖7所示。

圖7 CRC-CCITT多項式最大漏檢率與CRC-ANSI多項式最小漏檢率對比

由圖7 可知：CRC-CCITT 多項式最大可能漏檢率和CRC-ANSI 多項式最小可能漏檢率在同一位出錯概率的交點坐標(biāo)（5.422×10-3,3.682×10-6），當(dāng)位出錯概率ε<5.422×10-3時，相同信道環(huán)境中CRC-CCITT 多項式最大漏檢率都小于CRC-ANSI 多項式最小漏檢率；信道位出錯概率小于5.422×10-3且出錯位數(shù)為m時，無論存在哪種未被檢測可能，CRC-CCITT 多項式的漏檢率都一定低于CRC-ANSI 多項式；校驗數(shù)據(jù)位長272 bit（含16 bit 校驗位）時，CRC-CCITT 多項式在出錯位數(shù)較低時的具體漏檢數(shù)及0～272 bit 出錯漏檢率都相對更低，說明CRC-CCITT 多項式的整體檢錯性能更優(yōu)。

由此，設(shè)計接觸網(wǎng)在線監(jiān)測無線傳感模塊數(shù)據(jù)包時最終選取CRC-CCITT 多項式對272 bit 數(shù)據(jù)位長進行CRC多項式校驗。

3 結(jié)論

（1）針對生成形式為g（x）=（x+1）p（x）的特征多項式，在推導(dǎo)殘余誤差概率序列計算方法的基礎(chǔ)上，通過仿真計算發(fā)現(xiàn)，特征多項式殘余誤差概率與待校驗數(shù)據(jù)位長、最小漢明距離、CRC校驗碼位數(shù)和字節(jié)出錯概率直接相關(guān)；16 位CRC 多項式更適用于待校驗數(shù)據(jù)位長為256 bit時的情況。

（2）提出1 種可定量評估CRC 多項式性能的簡單計算方法，適用于任意數(shù)據(jù)位長校驗時更優(yōu)性能特征多項式的精確選取。應(yīng)用CRC 多項式校驗時，都可在結(jié)合具體應(yīng)用環(huán)境、待校驗位長、信道位出錯率、各特征多項式固定位長對應(yīng)的最小漢明距離及具體漏檢率等因素的基礎(chǔ)上，運用此方法逐步判斷各特征多項式的檢錯性能優(yōu)劣，篩選出性能更優(yōu)特征多項式。

（3）當(dāng)無法通過近似殘余誤差概率模型快速計算并直接比較2 種相近性能特征多項式的優(yōu)劣時，可對存在位出錯未被檢測出的所有可能情形進行分析，便可準(zhǔn)確計算其具體漏檢率，并進一步篩選比較特征多項式之間的性能。在BSC 信道下，運用CRC-ANSI 多項式和CRC-CCITT 多項式精確定量計算總數(shù)據(jù)位長272 bit（含16 bit 校驗位）時的位出錯漏檢率，發(fā)現(xiàn)位出錯概率小于5.422×10-3時，CRC-CCITT 多項式的漏檢率更低，整體檢錯性能更優(yōu)。