Stuck-at fault detection, controllability and observability functions of the combinational circuit gate pole

The stuck-at fault at the gate pole is a widely used and studied fault model for combinational and sequential circuits. In this work, stuck-at fault detection, controllability and observability Boolean functions corresponding to the combinational circuit gate pole are considered. Effective methods of their representations obtaining in the orthogonal DNF (ODNF) and the BDD are suggested. Studies allow us to solve together a number of tasks related to the stuck-at fault at the combinational circuit gate pole. Stuck-at fault detection function represents all test patterns for the single stuck-at fault at the gate pole; obsen>ability function represents all sets of input values that provide different values on at least one of the circuit output for different values on the considered pole; a-controllability function represents sets of input values providing the value а, ае {0, 1}, at the pole. Functions are defined on the set of circuit input variables. The ODNF and the BDD representations of Boolean function have the property that they clearly represent the set of input values sets on which function takes value 1: the ODNF conjunctions are orthogonal in pairs and consequently any set of input values can turn into a value 1 not more than one conjunction of the ODNF; in the BDD paths from the root to a terminal vertex represent conjunctions orthogonal in pairs as well. Besides, having the ODNF or the BDD of considered functions, it is easy to calculate testability measures: the fault detection probability, controllability and observability. The а-controllability function C (X), ае {0, 1}, is the function performed by the output of the subcircuit corresponding to the considered pole when а = 1, and its inversion when а = 0. The ODNF and the BDD of the function C (X) can be derived directly from the structural description of the circuit. For the one-output combinational circuit stuck-at-а fault detection function D (X) and observability function B(X) can be obtained according to definitions by formulas: In these formulas, ф(¥) is the function performed by the output of the fault-free circuit, ф%¥) is the function performed by the output of the circuit with stuck-at-a fault, aе {1, 0}, at the considered pole. Here, for reducing the text, we consider a one-output circuit, whereas, in the full paper, we consider a multiple-output circuit. To obtain some representation of functions D (X) and B(X) directly from the formulas (1) and (2), respectively, it is very time-consuming. In this work, for the obtaining of the ODNF and the BDD of observability function B(X), the subcircuit of the initial circuit is considered, where the pole is considered as the subcircuit input. Let us denote as v the input variable met in correspondence to the pole and as ц^У, v) - the function corresponding to the output of such subcircuit. Obtained in this work the formula for ODNF representation construction of observability function allows to reduce approximately 4 times the computational cost when compared to its obtaining directly from the formula (2). For BDD representation construction of the function, first the BDD of the function ц(^, v) is obtained, where the variable v is considered as the last variable in the function decomposition, then the BDD of observability function is obtained from the BDD of the function ц(^, v) by simple procedure proposed in this work. Thus, the complexity of the suggested procedure of the BDD construction of observability function is comparable with the complexity of the BDD construction for the function performed by the output of the subcircuit of the initial circuit. Also, we propose to obtain the ODNF and BDD representations of stuck-at-a fault detection function, ае {1, 0}, by multiplying of the ODNF and BDD, correspondingly, of observability function and a -controllability function. Note that this formula corresponds to the known test pattern construction method based on the Boolean difference. This formula allows distinguishing common part for the obtaining of stuck-at fault detection function for the stuck-at-1 and the stuck-at-0 faults. For solving of some tasks, for example, such as search of one test pattern, may be sufficient to perform only partial multiplication of the representations of two functions.

Keywords

Authors

References