BDD and DNF Based Algorithms for Constructing All Testability Functions of Combinational Circuit

Constructing testability functions of a combinational circuit line, such as: the controllability, observability and stuck-at fault detection functions, as well as the complement of the observability function is considered. Methods and algorithms for constructing testability functions based on Binary Decision Diagram (BDD) and Disjunctive Normal Form (DNF), as well as methods for constructing Conjunctive Normal Form (CNF) and obtaining testability functions using a SAT solver are proposed. Methods and algorithms for constructing testability functions for all and a subset of lines of a circuit are also proposed. Proposed methods and algorithms make it possible to significantly reduce the computational costs for constructing testability functions of a combinational circuit.