Synthesis of easily testable circuits in the basis $\{\&,\vee,\bar{\vphantom{x}}\,\}$ under single-type constant faults at the outputs of elements

We suggest a method to synthesise easily testable circuits of functional elements over the basis $\{\&,\vee,\bar{\vphantom{x}}\,\}$ which realise Boolean functions such that at most $h$ variables occur both with and without negation in their disjunctive normal forms. Constant faults of type $1$ at outputs of elements are allowed. It is proved that a complete test for such circuits is of length at most $h$.
This research was supported by the Russian Foundation for Basic Research, grant 02–01–00985; by the program of the President of Russian Federation for supporting leading scientific schools, grant 1087.2003.1; by the program ‘Universities of Russia;’ and by the program of basic research of the Department of Mathematical Sciences ‘Algebraic and Combinatoric Methods of Mathematical Cybernetics.’