面向接觸網狀態監測的無線傳感網絡循環冗余校驗多項式性能研究

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

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

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

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

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

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

1 殘余誤差概率計算

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

式中：Ap為合法碼字中碼重為p的碼字數目，p=0，1，…，n；ε為位出錯概率。

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

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

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

校驗位長r越多，特征多項式校驗能力越強。但隨著待檢數據總位長n增加，Ap和Bp的計算復雜度也會隨之增加。在校驗應用的眾多場合中，一般r?k，因此Bp的計算復雜度遠小于Ap［13］，通過Bp計算殘余誤差概率更為簡便。

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

1）初始化數列

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

2）生成特征序列

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

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

線性反饋移位寄存器的周期即所產生的碼組長度只與反饋方式有關。根據反饋方式，圖1中的線性反饋移位寄存器對應的特征方程為［14］

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

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

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

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

3）計算Wi

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

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

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

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

Bp的計算式為

若n為偶數，則其中Wi自動相加；再將Bp代入式（4），就可以得到相應殘余誤差概率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

其中，

對于接觸網狀態監測無線傳感模塊擬設計256 bit 待校驗數據位，3 種計算方法下，計算得到的CRC 多項式殘余誤差概率結果如仿真軟件截圖如圖2所示。

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

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

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

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

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

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

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

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

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

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

圖4 最小漢明距離為4時16位CRC多項式字節數與殘余誤差概率關系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）可被完全檢測時

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

2）未被完全檢測時

根據Koopman P 的研究結果，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。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由此，設計接觸網在線監測無線傳感模塊數據包時最終選取CRC-CCITT 多項式對272 bit 數據位長進行CRC多項式校驗。

3 結論

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

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

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