基于低復(fù)雜度編譯碼的數(shù)據(jù)流錯誤糾錯方法

衛(wèi)彥伉,王大鳴,崔維嘉

(解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院,鄭州450002)

基于低復(fù)雜度編譯碼的數(shù)據(jù)流錯誤糾錯方法

衛(wèi)彥伉,王大鳴,崔維嘉

(解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院,鄭州450002)

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

單粒子翻轉(zhuǎn);數(shù)據(jù)容錯;線性分組碼;故障注入;星載計算機;糾錯碼

1 概述

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

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

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

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

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

2.1 線性分組碼

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

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

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

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

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

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

2.2 建模評價

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

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

監(jiān)督矩陣H可表示如下:

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

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

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

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

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

3.1 編碼算法設(shè)計

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

圖1 SBC編碼原理

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

3.2 譯碼算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

3.3 LCCE譯碼算法復(fù)雜度分析

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

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

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

4 算法實驗評估

4.1 實驗方法

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

當對程序進行故障注入后,可產(chǎn)生的故障結(jié)果如下:

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

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

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

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

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

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

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

4.2 實驗結(jié)果及分析

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

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

表1 跳故障注入實驗結(jié)果%

表2 空間開銷與時間開銷

5 結(jié)束語

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

［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]賀朝會.單粒子效應(yīng)研究的現(xiàn)狀和動態(tài)［J］.抗核加固,2000,17(1):82-82.

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

［4]徐建軍,譚慶平,李建立,等.一種基于格式化標簽的可擴展控制流檢測方法［J］.計算機研究與發(fā)展, 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]李愛國,洪炳镕,王 司.一種星載計算機數(shù)據(jù)流軟故障糾正算法［J］.宇航學(xué)報,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]葉俊民,熊華根,董威,等.運行時軟件故障注入器的設(shè)計與實現(xiàn)［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

衛(wèi)彥伉,王大鳴,崔維嘉.基于低復(fù)雜度編譯碼的數(shù)據(jù)流錯誤糾錯方法［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”計劃基金資助項目“多業(yè)務(wù)模擬協(xié)議解析”(2012AA01A505)。

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

2014-03-24

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