Testability of 2-level AND/EXOR circuits

It is often stated that AND/EXORcircuits are much easier to test than AND/O R circuits. This statement, however, only holds true for circuits derived f rom restricted classes of AND/EXOR expressions, like positive polarity Reed -Muller and fixed polarity Reed-Muller expressions. For these two classes o f expressions, circuits with good deterministic testability properties are known. In this paper we show that these circuits also have good random patt ern testability attributes. An input probability distribution is given that yields a short expected test length for biased random patterns. This is th e first time theoretical results on random pattern testability are presente d for 2-level AND/EXOR circuit realizations of arbitrary Boolean functions. It turns out that analogous results cannot be expected for less restricted classes of 2-level AND/EXOR circuits. We present experiments demonstrating that generally minimized 2-level AND/OR circuits can be tested as easy (or hard) as minimized 2-level AND/EXOR circuits.