Information Technology Reference
In-Depth Information
Fig. 2.8. Truth table for AND Gate.
A
B
A AND B
A
A AND B
0
0
0
0
1
0
B
1
0
0
1
1
1
Fig. 2.9. Truth table for OR Gate.
A
B
A OR B
A
0
0
0
A O R B
0
1
1
B
1
0
1
1
1
1
Fig. 2.10. The NOT Gate.
A
NOT A
NOT A
A
0
1
1
0
Fig. 2.11. The NOR Gate.
A
B
A NOR B
0
0
1
A
A NO R B
0
1
0
B
1
0
0
1
1
0
construct any logical operation with any number of inputs and outputs. There
are also other possible choices for such a “complete set” of gates.
Let's see how this all works by building a “bit-wise adder” black box
from our basic AND, OR, and NOT building blocks. The bit-wise adder has two
inputs - the bits A and B to be added - and two outputs - the result R and the
carry C, if there is one ( Fig. 2.12 ).
We need to combine AND, OR, and NOT gates appropriately to produce this
logical behavior. First we note that the table for the carry bit is identical to that
of the AND gate. We can write:
Carry C: A AND B
The table for the result R is almost the same as that for the OR gate except for
the result for the 1 + 1 input when the output must be inverted. The result
R is therefore A OR B unless A AND B is 1. After some thought we can write
this as:
Result R: (A OR B) AND NOT (A AND B)
This leads to the implementation of the bit-wise adder shown in Figure 2.13 .
This circuit is actually called a “half-adder” because although it correctly
produces the carry value, it does not include a possible carry as an input to the
device, as well as A and B. Using the half-adder of Figure 2.13 , we can easily cre-
ate an implementation for a “full adder” ( Fig. 2.14 ). Adders for words with any
number of bits can now be created by chaining these full adders together.
These examples illustrate two key principles of computer design. The first
principle is that we rely on a “hierarchical design” process by which complex
objects are built up from simpler objects. Logic gates are our fundamental and
Search WWH ::




Custom Search