Short Complete Fault Detection Tests for Logic Networks with Fan-In Two

Abstract

It is established that we can implement almost every Boolean function on n variables by a logic network in the basis {x&y, x ∨ y, x ⨁ y, 1}, allowing a complete fault detection test with length at most 4 under arbitrary stuck-at faults at outputs of gates. The following assertions are also proved:We can implement each Boolean function on n variables by a logic network in the basis {x&y, x ∨ y, x ⨁ y, 1} (in the basis {x&y, x ∨ y, x ∨ y, x ⨁ y}) containing at most one dummy variable and allowing a complete fault detection test of length at most 5 (at most 4, respectively) under faults of the same type.