You have just received a large collection of digital circuits from a not too trustworthy supplier. You know which wires are connected to which circuit elements, and you are told what the elements are supposed to be. The question is: Have you been told the truth? You want to use as few tests as possible to determine if the supplier has actually put in the correct elements. These circuits use just two possible elements: AND and OR logic gates. Each can be characterized by a truth table relating its two inputs to its output [see tables below]. The output of an AND gate is 1 only when both inputs are 1, and the output of an OR gate is 1 when either input is 1.

As a warm-up, assume that the circuit is in the three-element configuration shown at the bottom left. You suspect that the OR gate (element 3) may actually be an AND gate and that one or both of the AND gates (elements 1 and 2) may actually be OR gates. You can test the circuit by putting a binary value--either 1 or 0--in each of the inputs (A, B, C and D) and seeing which values appear in the outputs (E and F). Only one test is needed to determine whether the logic gates in this circuit are correctly labeled. But what inputs should you use for the test, and what outputs should you expect?

This article was originally published with the title Verifying Your Circuits.

Comments