CLA CS-101: Introduction to Computers
The above could be also done for AND gates. For example the figure below shows two different ways of implementing a 4-input AND gate from 2-input AND gates.
First, we notice that it has two inputs, X and Y. Each one of these inputs may assume one of two values 0 and 1. Thus the truth table for that circuit will have four entries. For each such entry we have to find out the output Z. We do so by labeling the circuit. For example, if X = 0 and Y = 0 , we can label the various inputs and outputs of all gates until we find out that Z = 0 as shown below...
Similarily, we can do it for X = 0 and Y = 1 to get Z = 1 as shown below...
If we do this for all 4 input combinations, we get the truth table below.
XOR -------------- | X Y | Z | | -------+----- | 0 0 | 0 | | 0 1 | 1 | | 1 0 | 1 | | 1 1 | 0 | --------------
The above procedure for finding out what the truth table for a particular circuit is could be repeated for any circuit.
First, one has to identify all the "rows" in the truth table for which the output is a 1. Each one of these rows identifies a combination of inputs for which the output must be 1. Thus, one may say that the output must be 1 if the first such combination is present, or the second is present, or the third is present, etc... Thus the output of this circuit is the output of an OR gate whose inputs are the outputs of a number of smaller sub-circuits, each corresponding to a given row in the truth table with an output of 1 .
Second, for each row in the truth table (and thus for every sub-circuit connected to the OR gate), we notice that a particular pattern for the inputs must be present. Such a pattern can be tested using an AND gate with as many inputs as there are inputs to the truth table. A particular input to the AND gate is inverted (using a NOT gate) if its corresponding input in the truth table is 0.
Let's look at an example... Assume we want to build a circuit that has three binary inputs W, X, and Y and one output Z, which is to be 1 when all three inputs are identical (i.e. all 0 or all 1). The tuth table for such a circuit is shown below.
Equivalence ----------------- | W X Y | Z | | ----------+----- | 0 0 0 | 1 | | 0 0 1 | 0 | | 0 1 0 | 0 | | 0 1 1 | 0 | | 1 0 0 | 0 | | 1 0 1 | 0 | | 1 1 0 | 0 | | 1 1 1 | 1 | -----------------
1 1 1 1 0 0 0 0 <--- Cin 0 1 0 1 1 1 0 1 <--- X + 0 0 1 1 1 0 1 0 <--- Y ------------------------ 1 0 0 1 0 1 1 1 <--- S 0 1 1 1 1 0 0 0 <--- Cout
In order to design such a above circuit, we have to come up with its truth tables for the two outputs S and Cout. Once we have done that, we can draw the circuit equivalent to these truth tables as shown above.
The truth table for the S as a function of the inputs X and Y and Cin of the circuit is given below.
S ----------------- | X Y Cin| Z | |-----------+----- | 0 0 0 | 0 | | 0 0 1 | 1 | | 0 1 0 | 1 | | 0 1 1 | 0 | | 1 0 0 | 1 | | 1 0 1 | 0 | | 1 1 0 | 0 | | 1 1 1 | 1 | -----------------
Cout ----------------- | X Y Cin| Z | |-----------+----- | 0 0 0 | 0 | | 0 0 1 | 0 | | 0 1 0 | 0 | | 0 1 1 | 1 | | 1 0 0 | 0 | | 1 0 1 | 1 | | 1 1 0 | 1 | | 1 1 1 | 1 | -----------------
By connecting several such one-bit adders we could obtain adders that are capable of adding any number of bits we want! For example, a 5-bit adder would look as follows...
Created on: April 13, 1995. Updated on: November 15, 1995.