基于布尔逻辑的测试选择算法

基于布尔逻辑的测试选择算法 2007年第21卷第5期 (总第65期) 测试技术 JoURNALoFTESTANDMEASUREMENTTECHNOLOGY Vo1.21No.52007 (SumNO.65) 文章编号:1671—7449(2007)05—0386—05 基于布尔逻辑的测试选择算法 杨鹏,邱静,刘冠军,沈亲沐 (国防科技大学机电工程与自动化学院,湖南长沙410073) 摘要:提出了一种基于布尔逻辑运算的测试选择新 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 .首先建立布尔关联矩阵来 描述系统中故障与测 试的相关关系;然后依据关联矩阵,分别定义描述故障检测用测试集和故障隔离用 测试集的布尔逻辑函数; 再根据布尔运算定律对逻辑函数进行展开和化简处理.并根据计算结果得到最优 测试集.通过案例验证了 该方法的正确性,并指出了该方法的优势及其在计算复杂性方面存在的不足. 关键词:测试性 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ;测试选择;布尔逻辑;故障检测;故障隔离 中图分类号:TP391文献标识码:A TheTestSelectionAlgorithmsBasedonBooleanLogic YANGPeng,QIUJing,LIUGuanjun,SHENQinmu (CollegeofMechatronicalEngineeringandAutomation, NationalUniversityofDefenseTechnology.Changsha410073,China) Abstract:AnewmethodbasedonBooleanlogicoperationisproposedfortestselectioninthisp aper. Firstly,thecorrelativeBooleanmatrixisconstructedtodescribethedependentrelationshipb etween faultsandtestsinasystem.Secondly,theBooleanlogicfunctionswhichdescribethetestsetsforfault detectionandforfaultisolationarerespectivelydefinedthroughthedependencymatrix.Thirdly,the logicfunctionsareexpandedandsimplifiedaccordingtotheBooleancalculationrulesandtheoptimal testsetsarederivedfromtheresults.Finally,theproposedmethodisverifiedbyanexperiment.Its advantageincomparisonwithotherexistingmethodsanditsdisadvantageincomplexityarerespectively indicated. Keywords:DesignforTestability(DFT);testselection;booleanlogic;faultdetection;faultisolation 近年来,测试性和故障诊断学界对测试(点)选择问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 做了初步的研究L】J,主要包 括基于信息理论 的排序选择方法和基于组合优化的搜索算法.前者是用信息熵来定义测试对于故 障检测和故障隔 离的有用程度,并以此作为测试的权重,优先选择高权重的测试,直到满足测试性 要求为止;后者则首 先定义测试选择的目标函数和约束条件,然后采用各种智能优化算法来求解.这两 种方法涉及到信息权 重和目标函数的定义,主观性较强.本文借鉴组合电路测试码生成技术中的布尔差 分法以及文献[6]中 的逻辑方法,提出了基于布尔逻辑的测试选择算法,该算法主要以关联模型为基础 构建.关联模型l7J又 称诊断推理模型,因果模型],信息流模型和多信号流图模型],是普遍应用于系统测 试性分析与 设计的一种模型,它主要描述故障单元同测试结论之间的因果关系.先根据系统功 能结构单元和测点信 息构建关联图,然后根据关联图生成故障与测试关联矩阵.生成关联矩阵是进行测试与诊断策略设计的 关键,它是一种布尔矩阵,描述的是故障状态与测试结论相关(逻辑1)和不相关(逻辑O)的关系. 1面向故障检测的测试选择 及测试的相互关系构建关联矩阵 收稿日期:2006—12-07 作者简介:杨鹏(1978一),男,博士生,主要从事测试性建模分析与设计研究 (总第65期)基于布尔逻辑的测试选择算法(杨鹏等)387 ' 1 ' 2…' 3 Fr2…] 一 zft . 2.':'ft. 2 1.?:l::::I FLyt1ft2…ft-J 该矩阵是布尔矩阵,,一{f1,…,)表示系统故障集,丁一{",厶)表示经过初选得到的备选测试集, 该测试集是能保证系统测试性指标的完备测试集(如果不是完备测试集,则必须添加测试点以保证其完 备性,即保证关联矩阵中不存在全0行),但并不一定是最小完备测试集.矩阵元素 满足 f1tj可检测(ti与相关)'… Lijl0tj不可检测(f与不相关).… 考察关联矩阵F的各行,第i行上为1的元素所对应的测试都能单独检测到故障.因此不妨 用D()来表示可以检测故障的全部测试集 D(fi)一?(ft?),(3) 式中:为"逻辑加"的累积,若D()一0,则表明测试集丁中没有一个测试可以检测故障.例如 D(f)一f+f.表示测试tl或t2可以检测,其中"+"表示逻辑"或". 式(3)描述的是检测单个故障的可选测试集,如果要能检测两个故障,则要么执行可同时检测两个 故障的测试,要么同时执行两个分别检测这两个故障的测试,等价于逻辑"与".因此不妨用D(F)表示 同时检测所有故障的全部测试组合,记为 D(F)一TTD(fi),(4)苒 式中:儿为"逻辑乘"的累积,表示同时检测不同故障的测试组合.把式(4)完全展开成"与或"式,显然 每一个"与"式均表示能检测所有故障的测试组合.例如D(f1)一f+f.,D(f2)一f+f.,由式(4)可得 D(fl,)一f+ft.+ft.,即测试集{t),{t,t),{ff.)均可检测这两个故障,显然{t)为最小检测用测 试集.基于上述分析,可以得到面向故障检测的测试集选择 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 . 1.1选择步骤 基于布尔逻辑法的故障检测用测试选择的思路为:STEP1:按照式(3)分别计算每个故障的检测用 测试集D();STEP2:将计算结果代入式(4)中,并按照布尔运算规则将式中"或与"运算式展开成"与 或"运算式,其中每一个"与"式均表示能检测所有故障的测试组合;STEP3:再从这 些测试组合中选择费 用函数C0最小的,就是检测用测试选择问题的最优解. 1.2案例分析 采用文献1-33中的案例验证该方法,图1是一个4组件(故障源)4测试的关联图模 型. 该系统的故障集为F一{fl,f2,f3,),备选测试集 为丁一{t,t,t.,t),分析图中故障信息的传播方向(箭头 所示方向)以及故障源(方框表示)同各测试点(黑点表示) 位置关系可得系统关联矩阵为 11 10 10 01 (5) 首先矩阵没有全0行,因此备选测试集是完备测试 集,然后根据式(3)计算检测单个故障的测试集,再代入式(4)得 图1关联图模型 Fig.1Dependencygraphmodel 11OO n 一 F 388测试技术2007年第5期 D(F)一(f1+t2+t3+t4)(f2+t3)(f3)(f4)一tat2t3t4+tat3t4+t2t3t4+t3t4.(6) 因此,在该系统中,可检测所有故障的测试组合有4个,分别为{t,t,t.,t),{t,t.,t),{t.,ts,t), {t.,t).假设每个测试的费用相等,则最优测试子集为{t.,t).该结果同文献[3]所得结 果一致. 2面向故障隔离的测试选择 一 般假设系统在某一时刻只有一个故障发生,这是一个典型的二元模式辨识问题,需要结合不同测 试输出结果来判断可能发生的故障.对于式(1)所示关联矩阵,考虑到故障隔离结论中有无故障的结 论,所以定义元素厂0表示系统无故障,并定义系统状态集F一{fiI一0,1,…,),由此得到系统状态一 测试关联矩阵 12… F.Ff,.1ft.2…] 一 ft . 一:'it. h? :I::::I FmLf,mftm2…ftm 其中第一行元素比价特殊,根据式(2)的定义,规定itoJ一0,一1,2,…,. 两个故障可以被隔离的条件是二者所对应的行矢量必须相异,而且相异元素所对应的测试就可以隔 离这两个故障,用逻辑"或"表示相应的测试可以隔离这两个故障.基于这一思想,用I(fi,^)来表示能 隔离故障和的测试集,记为(,)=?[(oit)f],(8) 式中:o为"异或"运算,且i:/:k.考虑到it一0,一1,2,…,,因此有 (厂0,)一?E(ooit)f]一?(it?tj)一D(),k?0,(9) 式(9)说明隔离和其他故障,矗?o等价于检测故障^. 根据式(8)得到隔离任意两个故障的测试组合,将隔离任意两个故障的测试集作累积运算就可以得 到隔离全部状态测试组合,不妨用(F)来表示隔离所有状态的测试集,记为 I(F)一?I(fi,)一?{?[(.oft)f]}.(10)i.=0.f?^i?一0??J=1 结合式(9)可得式(10) I(F)一?(,^)一?(,)??(厂0,) "一.?'?(11, === ?(,)??D(^)一(F)?D(F). 式(11)说明故障隔离用测试集由隔离所有故障用测试集和检测所有故障用测试集联合组成.即用于故 障隔离的测试集覆盖了用于故障检测的测试集. 2.1选择步骤 基于上述分析,可以得到基于布尔逻辑法的故障隔离用测试选择的思路:STEP1: 按照式(8)计算隔 离任意两个故障的测试集,得到的是一系列的"或"式,其每一个元素表示一个隔离这两个故障的测试; STEP2:把计算结果代入式(10)中,按照布尔逻辑将"与或"运算式展开成"或与"运算式,其中每个"与" 式均表示能隔离所有故障的测试组合;STEP3:从这些测试组合中选择费用函数co最小的,就是隔离 用测试选择问题的最优解. 2.2案例分析 采用前面案例,根据式(7)可以得到确定性关联矩阵为 (总第65期)基于布尔逻辑的测试选择算法(杨鹏等)389 FT— OO 11 O1 00 OO OO 11 1O 1O O1 (12) 首先分别按式(9)计算隔离任意两个故障的测试集 (/1,f2)=t1+t4,I(f1,)一t1+t2+t4,I(f1,):t1+t2+t3,(,厂3)一t2, (,)一t2+t3+t4,(,)一t3+t4,D(F)一tit2t3t4+ht3t4+tzt3t4+t3t4.(13) 然后根据式(13)对隔离不同故障的测试组合求"与"运算可得 4 (F)一D(F)?几(,)一(f1t2t3t4+f1f3t4+tzt3t4+t3t4)?j.k三i?k (1+t4)(1+2+t4)(1+t2+t3)(2)(2+t3+t4)(3+t4)一Qtzt3t4+tzt3t4.(14) 由此可以看出测试集{t,t.,t.,t)和{t2,t.,t)均可以隔离系统所有的故障,显然{t.,t.,t)是最小 完备故障隔离用测试集.该结论同文献E3-i中结论一致. 3方法应用及特点分析 为了进一步验证算法的有效性,应用文献[133中的阿波罗发射前测试系统作为案例验证本文提出的 测试选择.该系统有10个故障和15个测试,假设测试代价都为1,关联矩阵如表1所示. 表1阿波罗发射前测试系统故障一测试关联矩阵 Tab.1Fault—testdependencymatrixforapolloprelaunchcheckoutsystem Test Fau1t 123456789101112131415 1000100010111100 2001010000011010 3000011101111001 4010001100000011 5010101111100110 6000110011101111 7】00110010010101 8111001101110010 9100110000001011 10111100100010110 采用面向故障检测用测试选择算法得到最小故障检测用测试集为{t?t);采用故障隔离用测试选 择算法得到的最小故障隔离用测试集包括:{t,t,t…t1},{t,t11't1.,t14},{t,t1.,t11,t1},{t,t1.,t11't1}, {t9,t11,t12,f14),{t1,t4,ts,f14),{t1,t4,t5,t14),{t1,t4,t12,t14),{t5,t9,t14,t15).系统故障检测率和隔离率均为 100%.若要求故障检测用测试集最小,则全局最优的测试集为(t,t.,t11,t1),{t蚓t,t1.,t1),{t,t1.t, t1),{t7,t1.,t11't1),{t9,t11,t12,t1).若考虑费用因素,则可以作进一步优化选择. 同其它测试选择方法相比,基于布尔逻辑的方法具有表2所示特点. 表2本文方法与其它方法的特点比较 Tab.2Comparisonbetweenthismethodandotherexistingmethods 方法算法使用程序实现算法精度适用范围 布尔逻辑法容易容易全局最优解矩阵维数在百维以下的中小系统 信息理论法较易较易容易陷入局部最优解矩阵维数在百维以上的大系统 组合优化法较难较难容易陷入局部最优解矩阵维数在百维以上的大系统 390测试技术2007年第5期 同布尔差分法类似,基于布尔逻辑的测试选择算法的局限性在于存在维数灾难.对于X维关联 矩阵,在最坏的情况下,检测用测试选择算法复杂度为O(),隔离用测试选择算法则更为复杂,因此 限制了该算法在较大规模系统中的应用.但是可以采取一些 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 降低计算量,如在计算之前可以通过矩 阵分析剔除冗余测试(列矢量相同的测试),合并模糊故障(行矢量相同的故障,理论上不可隔离)以降低 矩阵维数,从而减少计算量.在或与式展开时优先将测试个数小的或式展开合并也可以降低计算量.此 外可以采用分治策略,即将矩阵分解成若干小矩阵,分别计算最优解,然后合并得到系统最优解,该方 法可以有效降低计算量,但它是以牺牲全局最优解为代价的,采取何种分解方法以尽可能接近全局最优 解还有待进一步研究. 4结论 故障与测试关联矩阵描述了各备选测试同故障的布尔逻辑关系,本文将用于故障检测和隔离的测试 组合方式同逻辑运算中的"或","与"和"异或"相对应,然后根据这一思想构建了基于布尔逻辑的测试选 择算法.实践证明,该方法选择得到的结果正确,而且由于全部运算都是布尔代数运算,因此适合计算 机程序实现.本文提出的布尔逻辑法为测试选择问题提供了一种新的思路,但是在降低复杂度方面还有 待进一步研究. 参考文献: [1]蔡金燕,陈国通,张宏伟.故障诊断中的测试节点优选方法[J].军械工程学院,2002.14(1):7-l0. CaiJinyan,ChenGuotong,ZhangHongwei.Amethodofselectionnodesforfaultdiagnosis[- J].JournalofOrdnance EngineeringCollege?2002,14(1):7-l0.(inChinese) [2]张复春,张风鸣.颐文灿.关于测点分布的矩阵分析[-J1.测试技术,2004,l8(2):ll4 一ll7. ZhangFuchun.ZhangFengming?GuWencan.Thematrixanalysisaboutthedistributionofth emeasuringpoints [-J1.JournalofTestandMeasurementTechnology,2004.18(2):ll4一ll7.(inChinese) [-31田仲.石君友.系统测试性设计分析与验证[M].北京:北京航空航天大学出版 社.2003:l8l—l83. [4]黎琼炜,胡政.系统级BIT设计中的测试选择方法[-J1.计算机工程与应 用.2001(19):l27一l29. IiQiongwei,HuZheng.TestSelecetionalgorithminsystem— levelBITdesign[J].ComputerEngineeringand Applications,2001(19):l27一l29.(inChinese) [5]苏永定,钱彦岭.邱静.基于启发式搜索策略的测试选择问题研究[J].中国测试技 术,2005.31(5):46—48. SuYongding,QianYanling,QiuJing.Heuristicsearchintestselection[-J].ChinaMeasureme ntTechnology?2005, 3l(5):46—48.(inChinese) [-61苏永定.机电产品测试性辅助分析与决策相关技术研究[D].长沙:国防科技大 学,2004. [7]HinzmannMA.Dependencymodelingofanavionicspower— supplyfortestabilityanalysis[c].Reliabilityand MaintainabilitySymposium.1995:283—289. [8]HaynesI,KelleyB.ChujenEin.eta1.Automaticdependencymodelgeneratorformixed —signalcircuits[,C1.IEEE SystemsReadinessTechnologyConference.1998:9l一96. [9]IEEEStdl232— 2002.IEEEStandardforArtificialIntelligenceExchangeandServiceTietoAllTestEm,iron ments (AI—ESTATE)[s].Piscataway:IEEEStandardsPress,2002. [101PengYun,ReggiaJA.Abductiveinferencemodelsfordiagnosticproblem— sol,,ing[M].NewYork:Splinger— Verlag,l990. [11]SimpsonWR,SheppardJW.Systemtestanddiagnosis[M].Boston:KluwerAcademicP ublishers,l994. [12]DebS.PattipatiKR,RaghavanV.eta1.Multi— signalflowgraphs:anovelapproachforsystemtestabilityanalysis andfaultdiagnosis[J].IEEEAESMagazine.1995(1):l4—25. [13]WohlJG.InformationautomationandtheApolloprogram:Aretrospective[-J1.IEEETrans.onSystem?man? andCybernetics,l982,l2(4):469—478.