Several gates can be interconnected to create a circuit. All you have to remember is that the output of a gate can be connected to the input of another gate. An output can be connected to several inputs, but two outputs cannot be connected together. Suppose the outputs of two inverters were connected together and the input to one inverter was 0 and the input to the other inverter was 1. The output of one inverter would be 1 and the output of the other would be 0. If both outputs were connected together, they would have to be the same value (because the voltage at a point can have only one value at any instant).
The EOR gate calculates the sum of two bits: 0+0=0, 0+1=1, 1+0=1, 1+1=0 (here “+” means plus). The table below gives the truth table of a half adder that adds bit A to bit B to produce a sum S and a carry C, and the figure shows the circuit of a two-bit adder. The carry bit is generated by ANDing the two inputs.
|
Truth table of a half adder
|
The two-bit adder (the half adder)
|
A single two-bit half adder is of limited practical use, because computers are seldom called upon to add just two bits. In general, computers have to add together two m-bit words; that is, bit ai must be added to bit bi together with a carry-in from stage i-1 of the adder to produce sum si and carry-out ci to stage i+1. We therefore need a full adder that adds two bits together with a carry-in to produce a sum and a carry-out.
If one EOR gate adds two bits to produce a sum, we can take the output of an EOR gate and feed it into a second EOR gate together with a carry-in to produce the sum of three bits. But how do we generate a carry-out? If you add three bits, you will get a carry if either two or three of the inputs are 1.
|
The full-adder
|
This figure demonstrates how two half adders are used to create a full adder that adds together three bits to produce a sum and a carry-out. The carry-out bit is generated by ORing the carry bits generated by the two half adders. |
 |
Is this circuit really that of a full adder? One way of determining whether this is a full adder circuit is to write down its truth table and compare the outputs with those of a full adder. The first three columns cover all eight possible values of the three bits to be added (Cin, A, and B), and the next two columns display the carry-out, Cout, and sum of a full adder that implements the binary addition Cin plus A plus B. The right-hand five columns provide the intermediate values (Carry1, Sum1, Carry2) generated by the circuit and the two outputs (Carryout and Sum). As you can see, this circuit does indeed implement the function of a full adder. |
Parallel Addition
A practical computer requires m full adder circuits to add two m-bit words in parallel.
 |
The parallel adder
This figure demonstrates the construction of an m-bit parallel adder. Each of the m full adders adds bit ai to bit bi, together with a carry-in from the stage on its right, to produce a carry-out to the state on its left. You might think that the least-significant stage that adds a0 to b0 doesn’t require a full adder, because it doesn’t have a carry-in (the carry-in in is shown as 0). In practice, a parallel adder does have a carry-in to the first stage, Cin, for three reasons: the first is that if B is set to 0 and Cin set to 1, the parallel adder performs the operation A plus 1. The second is that if the carry-in to the least-significant stage Cin is set to the carry-out of a previous addition, the circuit can be used to perform chained arithmetic. The third, is that Cin can be used to facilitate subtraction, as we shall soon see.
|
 |
The programmable inverter
Let’s take another look at the EOR gate. Suppose we make one of its inputs a control input, X, and feed the binary value ai to the other input. If X is 1 and ai is 0, the output is 0; if ai is 1, the output is 1. When the control input X is 0, the EOR gates copies the other input to its output. When X is 1 and ai is 0, the output is 1; if ai is 1, the output is 0. Therefore, control input determines whether ai is passed to the output or inverted. This figure shows how m EOR gates can be used to create an m-bit programmable inverter. If the input is A, the output is A if X = 0, and NOT A if X = 1. Computers use this circuit to generate the logical complement of a word. |
I
 |
The adder/subtractor If the programmable inverter is placed in series with one of the inputs of a parallel adder, and the invert control input connected to the carry-in bit of the least-significant stage, we have an interesting circuit. When the control input is 0, the bits of A are passed unchanged to the adder and the circuit calculates A plus B. When the control input is set to 1, the programmable inverter inverts all the bits of A and adds 1 to the carry-in of the first stage. Because the two’s complement of a number is formed by inverting its bits and adding 1, the circuit performs addition when the control bit is 0, and subtraction when it is 1. In a computer the control bit might be derived from the instruction being executed (e.g., ADD or SUB). |
Let’s look at some of the interesting things you can do with a few gates.
 |
Three-line to eight-line demultiplexer This circuit has three inputs A, B, and C, and eight outputs Y0 to Y7. The three inverters generate the complements of the inputs A*, B*, and C*. Each of the eight AND gates is connected to three of the six lines A, A*, B, B*, C, C* (each of the three variables must appear in either its true or complemented forms). The output of first gate, Y0, is A*.B*.C*, and is 1 if all inputs to the AND gates are 1 (i.e., A* = 1, B* = 1, C* = 1). Therefore, Y0 is 1 when A = 0, B = 0, C = 0. If you examine the other AND gates, you will see that each gate is enabled by one of the eight possible combinations of A, B, C.
This circuit is called a three-line to eight-line demultiplexer, because it converts a three-bit binary value, A, B, C, into one of 23 outputs. The table below provides a truth table for this circuit, which is also called a decoder because it can take, for example, the op-code field of an instruction register and decode it into individual instructions.
|
The demultiplexer
|
Inputs |
Outputs |
|||||||||
|
A |
B |
C |
Y0 |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
 |
Application of a demultiplexer |
 |
The two-input multiplexer and its truth
table
Another interesting circuit is the two-line to one-line multiplexer which is constructed entirely from NAND gates. Note that if both inputs of a 2-input NAND gate are connected together, it behaves exactly like an inverter.
The truth table for this circuit has three inputs and an output. The truth table shows that when input C = 0 the output is given by A, and when C = 1 the output is given by B. This circuit is an electronic switch that selects input A or input B, depending on the state of control input C. |
Our final circuit is the prioritizer. A prioritizer deals with competing requests for attention. Suppose that prioritizer’s five inputs x0 to x4 are connected to the outputs of five devices that can make a request for attention.
 |
The priority circuit Input x4 has the highest priority. That is, device i can put a logical 1 on input xi to request attention at priority level i. If several inputs are set to 1 at the same time, the prioritizer sets only one of its outputs to 1, all the other outputs remain at 0. For example, if the input is x4,x3,x2,x1,x0 = 00110, the output y4,y3,y2,y1,y0 = 00100, because the highest level of input is x2. If you examine the circuit , you can see that output y4 is equal to input x4 because there is a direct connection. If x4 is 0, then y4 is 0; and if x4 is 1 then y4 is 1. The value of y4 is fed to the input of the AND gates G3, G2, and G1 in the lower priority stages via an inverter. If x4 is 1, the logical level at the inputs of the AND gates is 0, which disables them and forces their outputs to 0. If x4 is 0, the value fed back to the AND gates is 1 and therefore they are not disabled by x4. Similarly, when x3 is 1, gates G2 and G1 are disabled, and so on. |
