基于低復雜度編譯碼的數據流錯誤糾錯方法

衛彥伉,王大鳴,崔維嘉

(解放軍信息工程大學信息系統工程學院,鄭州450002)

基于低復雜度編譯碼的數據流錯誤糾錯方法

衛彥伉,王大鳴,崔維嘉

(解放軍信息工程大學信息系統工程學院,鄭州450002)

針對單粒子翻轉可能帶來的數據流錯誤,設計一種改進的數據流錯誤糾錯方法。利用線性分組碼的相關理論,分析常用數據流容錯方法的容錯能力,從線性分組碼的編譯碼原理出發給出一種低復雜度編譯碼算法,基于該編碼的容錯方法能夠以較少的開銷糾正單粒子翻轉造成的單比特數據錯誤。實驗結果表明,該方法能夠有效糾正單粒子翻轉造成的數據錯誤,與常用的糾檢錯方法相比,具有較優的糾錯性能和較少的容錯開銷。

單粒子翻轉;數據容錯;線性分組碼;故障注入;星載計算機;糾錯碼

1 概述

在太空環境中,星載計算機系統常受到各種輻射現象的影響。當外部環境中的高能粒子輻照和電磁干擾等電子噪聲作用于半導體電路時,會誘發半導體電路的瞬態故障,也被稱為軟錯誤［1］。由文獻［2］可知,單粒子效應大約占半導體電路軟錯誤的50%。單粒子效應中發生頻率最高的是單粒子翻轉(Single Event Upset,SEU)現象。單粒子翻轉主要發生于存儲器件和邏輯電路中,是當高能粒子轟擊半導體電路時形成瞬態電流,會導致PN結出現瞬時充放電,從而改變內部邏輯狀態,例如從邏輯0變成邏輯1。這種錯誤會在系統內部傳播,引起系統出錯、失效甚至更嚴重的后果。而隨著處理器逐步采用深亞微米制造工藝,在性能得到大幅提高的同時,處理器對于引起SEU的各種噪聲干擾也變得越來越敏

感。同時,星載平臺的計算資源受限,如何利用有限的計算資源,解決計算可靠性問題已成為一個日益嚴峻的課題,所以SEU是航天計算的最主要挑戰［3］。

SEU對系統可靠性的影響可分為數據流錯誤和控制流錯誤,前者指SEU影響了存儲部件和運算部件中的錯誤,后者指SEU改變了程序正常的執行軌跡。控制流錯誤的容錯方法主要是基于簽名的各種控制流檢測技術［4-5］。數據流錯誤的容錯方法,主要為各種信息冗余技術［6-7］和容錯編碼技術［8］。以上方法雖然可以達到較高的錯誤覆蓋率,但是仍有很多問題亟待解決。如信息冗余技術中的重復變量和重復指令方法,只具有檢錯功能而無法糾錯,糾錯功能的實現,往往需要另外的故障恢復例程,同樣帶來更多的時間開銷與存儲開銷。糾檢錯編碼是一種對數據進行容錯加固的有效方法,如線性分組碼、循環碼、卷積碼等。將糾檢錯編碼運用于衛星處理平臺時,必須選擇一種構造方便、編碼簡單、譯碼也容易實現的編碼方案。因為較復雜的編譯碼算法在使用軟件實現時,不僅帶來較多的時間開銷和存儲開銷,還會帶來數據流錯誤和控制流錯誤的隱患。因此,本文從線性分組碼的糾檢錯原理出發,對各種容錯方法進行建模分析,評價其容錯能力與容錯開銷,并提出一種低復雜度的編譯碼方法(Low Complexity Coding and Encodig,LCCE)。

2 線性分組碼及其對常用容錯方法的評價

線性分組碼是信道編碼中最基本的一類碼,具有明顯的數學結構,是討論各類碼的基礎。指令復算方法和重復變量方法都可以將其建模為一種線性分組碼的檢錯方法,并用線性分組碼理論評價其容錯性能。

2.1 線性分組碼

一般(n,k)線性分組碼的生成方式可表示如下:

其中,m為k位信息位;V為生成碼字;G為生成矩陣。尤其是當線性分組碼為系統碼且信息位排在碼的前k位時,G可表示為:

通常把式(2)的生成矩陣成為標準生成矩陣,其中,Ik為單位陣。

對于可糾錯的的線性分組碼的譯碼可采用伴隨式糾錯譯碼,對于接收到的碼字V—,計算其伴隨式如下:

其中,H為線性分組碼的一致監督矩陣,簡稱監督矩陣,當G可表示為式(2)時,H可表示如下:

當出錯的數目在線性分組碼的檢錯能力范圍時,若sT=0,則認為r無錯;若sT≠0,時說明一定有錯。當出錯時,若sT等于H的第i列,則說明的第i位發生錯誤;若sT不等于H的任一列,則說明發生錯誤,但超過此線性分組碼的糾錯能力。

2.2 建模評價

指令復算糾方法［9］源自時間冗余技術,目的是為了減少時間冗余開銷。指令復制方法應用于匯編語言,將寄存器和變量做雙份冗余,并將除轉移指令以外的所有指令也進行復制,并在存儲和條件轉移指令之前插入檢錯代碼來保證轉移和寫入內存中的數據的正確性。重復變量［10-11］(Duplicated Variable,DV)的方法首先將變量劃分為中間變量和最終變量。中間變量是指參與計算其他變量的變量,而最終變量不參與計算其他變量。然后將程序中的所有變量(稱為原始變量)進行復制,對原始變量的每一次讀寫操作,都進行雙份冗余操作。并且在對最終變量的寫操作完成之后,進行該變量的一致性校驗。

指令復算方法和重復變量方法可以將其建模為一種(2n,n)線性分組碼的檢錯方法。并且其編碼構成可表示為監督位與信息位相同,其檢錯方法亦可簡單建模為判斷監督位與信息位是否相同。生成矩陣G可表示為:

監督矩陣H可表示如下:

當接收到碼字的第i位發生錯誤時,伴隨是sT等于單位矩陣In的第i列元素,也等于接收碼子的信息位與監督位的異或值。因此,采用此編碼的譯碼方式可以通過比較信息位與監督位是否相同來檢錯,但是卻無法判斷出錯位置是在監督位還是在信息位中,這是由于監督矩陣H中的任一列向量都不具有唯一性。由于其信息位與監督位完全相同,這樣構成的線性分組碼最小碼距為2,因此其只具有檢錯功能而不能糾錯。

由于SEU會造成數據的單比特錯誤,因此容錯編碼必須有糾正單個錯誤的能力。漢明碼是一種常用的的糾正單個錯誤的線性分組碼,傳統的存儲器檢驗方式是對16/32位的數據,添加6/8位的漢明校驗碼。漢明碼的編碼效率隨著信息位數的增加而提高,但是其糾錯的速度會隨著信息位數的增加而減慢。并且漢明碼的編譯碼算法較為復雜,對于(7,4)的漢明碼譯碼中,需要進行多達20次的碼位

運算［8］,其復雜的糾錯過程會帶來較多的時間開銷與存儲開銷。實驗結果表明采用(38,32)漢明碼方法容錯的平均時間開銷是采用DV方法平均時間開銷的500倍之多［8］。因此,必須設計一種低復雜度編譯碼算法的數據流錯誤糾錯方法。

3 一種低復雜度的線性分組碼編譯碼算法

文獻［8］提出了一種單比特錯誤糾正算法(Single Bit error Correct,SBC),由于其對程序中的變量只進行了少量的處理而不是簡單的復制,因此其在保證糾錯的同時也保持了較低的容錯開銷。其基本思想是針對程序的變量,在進行存儲操作時產生附加信息,在進行讀取操作時由原始變量和附加信息共同得到正確的變量值。實驗結果表明,該算法能夠有效地對數據錯誤進行糾正,且容錯開銷遠小于漢明碼,但是其時間開銷確實DV方法的3倍～4倍。這是由于SBC方法本質是一種(16,8)的線性分組碼糾錯方法,而所提的編譯碼算法并未從線性分組碼的編譯碼數學表述出發進行設計,導致其所提譯碼算法過于復雜,影響了算法性能。下面對其進行詳細闡述,并提出低復雜度的編譯碼算法——LCCE。

3.1 編碼算法設計

如文獻［8］所述,以8位二進制數據為例,其編碼算法如圖1所示。編碼算法可用公式表示如下:

圖1 SBC編碼原理

式(7)與圖1均表示對8位二進制數據V添加8位冗余位,其中,V是碼元Vcode的信息位;V+ (V＞＞1)構成碼元冗余位,記冗余位為Vr。Vr的生成方式為原信息位與原信息位循環右移一位所的數據的異或值,本文中的“+”均表示異或運算。該編碼算法結構簡單,且所用運算異或和右移指令均為處理器的高效指令,因此編碼方案仍沿用SBC算法的編碼算法。

3.2 譯碼算法設計

由編碼算法可以得到此(16,8)線性分組碼的生成矩陣G如式(8)所示。由式(8)可知G為標準生成矩陣,因此可以得到監督矩陣H如式(9)所示:

由式(8)、式(9)可知G,H滿足如下關系:

其中,I表示單位矩陣。因此:

同時由于×P即表示該編碼的監督位生成方式,因此可得sT計算如下:

式(12)通過移位運算和異或運算,避免了運算量較高的矩陣乘法運算,得到伴隨式sT。

式(12)通過異或運算,將不受影響的冗余位置0,得到伴隨式sT。由sT伴隨式中數值為1的元素位置與碼元中發生錯誤的元素的位置關系,可以得到糾錯變量check如式(13)所示:

式(13)中&表示與運算,通過左移操作和與操作得到糾錯變量check。check中元素為1的位置對應于信息位出錯的信息位。由此可以得到信息位的糾錯如式(14)所示:

以上式(12)～式(14)是在考慮信息位中出現一位錯誤的情況,當數據錯誤發生在冗余位中

時,即信息位正確,此時可不需要對信息位進行糾錯,而如果仍套用以上公式對接收碼元code進行糾檢錯時,需要保證check恒為0。當數據錯誤發生在冗余位中時,可以驗證由式(12)得到的sT僅有一位為1,所以能夠保證check恒為0。當冗余位發生錯誤時,式(12)～式(14)仍然適用。

綜上可以得到譯碼算法的具體過程如下:

(1)輸入碼元check,根據信息位計算其冗余編碼:+(＞＞1)。

(4)對信息進行糾錯:,結束。

3.3 LCCE譯碼算法復雜度分析

譯碼算法與SBC譯碼算法流程如圖2所示。從圖2可以看出,LCCE算法在進行糾錯譯碼時,共需要2次移位、3次異或、1次與運算;而SBC譯碼算法在進行糾錯時,共需要2次移位、6次異或、1次與預算以及2次判斷分支。

圖2 LCCE譯碼算法與SBC譯碼算法流程

這是因為SBC所提譯碼算法,在對接收碼元進行糾檢錯譯碼時,分別進行了2次判斷:(1)有無錯誤發生;(2)錯誤生發在信息位還是冗余位。并對不同的分支作了不同的處理。而LCCE譯碼算法只對信息位進行糾錯,因此復雜度會明顯降低。進一步分析可以看出,較多的處理指令會帶來較多的時間開銷與存儲開銷,尤其是較多的判斷分支指令會打亂處理器流水線,增加時間開銷。因此,LCCE譯碼算法明顯優于SBC譯碼法。

4 算法實驗評估

4.1 實驗方法

為驗證LCCE編譯碼算法的有效性,在Intel處理器Linux操作系統(Ubuntu 13.10)下對4個標準程序進行了故障注入實驗［12］:冒泡排序(BS),快速排序(QS)、40×40矩陣乘法(MM)、1 024點快速傅里葉變換(FFT)。隨機故障被注入到程序的數據段和堆棧段,即在程序數據空間隨機選擇一個地址并隨機翻轉其中一位。

當對程序進行故障注入后,可產生的故障結果如下:

(1)程序結果正確(CR):故障沒對程序運行無影響。

(2)故障被系統檢測或出發硬件報警機制(OS):操作系統檢測到訪問非法內存地址。

(3)程序結果錯誤(ER):程序正常退出,容錯機制未糾正錯誤,但程序結果出錯。

(4)程序運行超時(TO):程序在給定的時間內沒有結束。

(5)故障被容錯機制糾正(SC):故障被添加的檢錯機制檢成功檢測。

(6)故障被容錯機制檢測(SD):故障被添加的糾錯機制成功糾正。

檢測算法的開銷包括時間開銷和空間開銷,均表示與未進行數據流容錯加固的原始程序的相應開銷的比值。

4.2 實驗結果及分析

由表1對比可知采用重復變量方法和編碼方法對數據錯誤都具有很高的檢測率。但是重復變量方法無法糾錯,而且編碼方法的檢測能力均優于DV方法。編碼方法中,LCCE方法的糾錯能力最高(由于三者都是“糾一檢二碼”,理論上應該相當),這主要是因為隨機故障可能破壞糾檢錯過程中的中間變量,導致糾錯失敗。但是由于LCCE方法低復雜度的優點,其中間變量少,導致糾錯失敗的可能性被大大降低,因此其糾錯能力由于另外2種編碼方式。

同時由表2在容錯機制帶來的時間開銷與存儲開銷的對比中可以發現。DV的時間開銷與存儲開銷最小,而3種編碼方法中,海明方法時間開銷過大,SBC方法時間開銷也達到DV方法的3倍～4倍。而LCCE方法在容錯開銷與DV方法相當的情況下實現了糾正單比特錯誤的能力。

表1 跳故障注入實驗結果%

表2 空間開銷與時間開銷

5 結束語

本文利用線性分組碼的相關理論,分析了各種數據流容錯方法的容錯能力,提出一種線性分組碼的低復雜度編譯碼算法,基于該編碼的容錯方法能夠以較低的開銷有效糾正單粒子翻轉造成的單比特數據錯誤。故障注入實驗結果表明,該方法在容錯開銷與重復變量相當的情況下,能有效糾正單粒子翻轉造成的數據錯誤。

［1]Baumann R C.Radiation-induced Soft Errors in Advanced Semi-conductor Technologies［J］.IEEE Transactions on Device and Materials Reliablity,2005,5(3):305-316.

［2]賀朝會.單粒子效應研究的現狀和動態［J］.抗核加固,2000,17(1):82-82.

［3]徐建軍,譚慶平,熊 磊,等.一種針對軟錯誤的程序可靠性定量分析方法［J］.電子學報,2011,39(3): 675-679.

［4]徐建軍,譚慶平,李建立,等.一種基于格式化標簽的可擴展控制流檢測方法［J］.計算機研究與發展, 2011,48(4):638-646.

［5]Oh N,Shirvani P P,McCluskey E J.Control-flow Checking by Software Signatures［J］.IEEE Transactions on Reliability,2002,51(1):111-122.

［6]Nicolescu B,Savaria Y,Velazco R.SIED:Software Implemented Error Detection［C］//Proceedings of the 18th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems.［S.1.］:IEEE Press,2003: 589-596.

［7]Oh N,Shirvani P P,McCluskey E J.Error Detection by Duplicated Instructions in Super-scalar Processors［J］.IEEE Transactions on Reliability,2002,51(1):63-75.［8]李愛國,洪炳镕,王 司.一種星載計算機數據流軟故障糾正算法［J］.宇航學報,2007,28(4):1044-1048.

［9]Reis G A,Chang J,Vachharajani N,et al.SWIFT: SoftwareImplementedFaultTolerance［C］//Proceedings of International Symposium on Code Generation and Optimization.［S.1.］:IEEE Computer Society, 2005:243-254.

［10]Nicolescu B,Velazco R,Sonza-Reorda M,et al.A Software FaultToleranceMethodforSafety-criticalSystems: Effectiveness and Drawbacks［C］//Proc-eedings of the 15th Symposium onIntegratedCircuitsandSystems Design.［S.1.］:IEEE Press,2002:101-106.

［11]Oh N,Mitra S,McCluskey E J.ED 4 I:Error Detection by Diverse Data and Duplicated Instructions［J］.IEEE Transactions on Computers,2002,51(2):180-199.

［12]葉俊民,熊華根,董威,等.運行時軟件故障注入器的設計與實現［J］.計算機工程,2008,34(24):4-6.

編輯 索書志

Data Stream Error Correction Method Based on Low Complexity Coding and Encoding

WEI Yankang,WANG Daming,CUI Weijia
(College of Information System Engineering,PLA Information Engineering University,Zhengzhou 450002,China)

This paper designs a kind of encoding and decoding algorithm with a low complexity based on the data correction method to resolve the data stream errors which Single Event Upset(SEU)may bring.It uses the theory of linear block codes to analyze various methods of data fault tolerance,and designs a kind of encoding and decoding algorithms with a low complexity of linear block code from the encoding and decoding principle of linear block codes,the fault-tolerant coding method can effectively correct single-bit data errors caused by SEU,with low fault-tolerant overhead.Fault injection experiments show that this method can effectively correct data errors caused by single event upset,compared with other common error detection or correction methods,error correction performance of this method is superior,while its fault tolerance cost is less.

Single Event Upset(SEU);date fault tolerance;liner block code;fault injection;on-board computer;error correction code

衛彥伉,王大鳴,崔維嘉.基于低復雜度編譯碼的數據流錯誤糾錯方法［J］.計算機工程, 2015,41(3):97-101,105.

英文引用格式:Wei Yankang,Wang Daming,Cui Weijia.Data Stream Error Correction Method Based on Low Complexity Coding and Encoding［J］.Computer Engineering,2015,41(3):97-101,105.

1000-3428(2015)03-0097-05

:A

:TP306.3

10.3969/j.issn.1000-3428.2015.03.018

國家“863”計劃基金資助項目“面向3G-LTE基于商用芯片的高可用高效能星載處理平臺”(2012AA01A502);國家“863”計劃基金資助項目“多業務模擬協議解析”(2012AA01A505)。

衛彥伉(1988-),男,碩士研究生,主研方向:衛星移動通信;王大鳴,教授;崔維嘉,講師。

2014-03-24

:2014-05-15E-mail:wykbssd@126.com