逻辑表达式图的实现及其在集成电路故障 可测性中的应用

数字电路的可靠性有着至关重要的影响，测试是其重要保证，测试向量的自动生成(ATPG)在数字电路的测试中占有重要地位；逻辑表达式图(Boolean Expression Diagrams,BED)是用于逻辑函数与逻辑电路表达与运算一种数据结构，能够将逻辑电路在线性空间复杂度内表达，是二元判决图(Binary Decision Diagrams, BDD)在概念上的推广且保留着BDD的许多有用的性质。讨论了BED的性质与实现方法，并将BED用于逻辑电路呆滞型故障测试向量的自动生成中，基于BED的测试算法直接将原电路与故障电路做异或运算后用BED表达再化简或判断其可满足性，算法能充分使用逻辑代数的化简规则和利用电路与故障电路的相似性。实验结果表明,基于BED的测试方法具有较低的复杂度。

Implementation of Boolean Expression Diagrams and Its Application to the Testability of the Fault of Integrated Circuits

Reliability of digital circuits is very important and testing is its significant guarantee,while Automatic Test Pattern Generation(ATPG) is the major task of the test.Boolean Expression Diagrams(BEDs) is a new data structure for representing and manipulating Boolean functions or Boolean circuits and capable of representing any Boolean circuit in linear space.The properties and implementing methods of BED,which was applied to the ATPG of stuck-at faults of logic circuits,was studied.In this ATPG algorithm,the XOR of the functions of the original circuit and the fault circuit was directly simplified or judged whether to be satisfiable after expressed by BED.The algorithm can sufficiently apply the simplification rules of Boolean Algebra and exploit the structural similarities between the two circuits.Experiments showed that the methods based on BEDs are less complex.