基于低复杂度编译码的数据流错误纠错方法

卫彦伉,王大鸣,崔维嘉

(解放军信息工程大学信息系统工程学院,郑州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