5. Logic Gates and Circuits
The functionality of even the most complex computer is achieved by connecting simple logic gates
into operational circuits.
Basic Gates
There are four basic logic gates. The symbols used for these gates and their "truth tables" are
given below (note that these are not the "standard" electrical engineering symbols for these gates).
- NOT : unary input; output is reverse of input
- AND : binary inputs: output is "on" only if both inputs are "on"
|
INPUTS |
OUTPUT |
|
Input-1 |
Input-2 |
|
0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
- OR : binary inputs: output is "off" only if both inputs are "off"
|
INPUTS |
OUTPUT |
|
Input-1 |
Input-2 |
|
0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
- XOR : binary inputs: output is "on" only if the inputs are different
|
INPUTS |
OUTPUT |
|
Input-1 |
Input-2 |
|
0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
Basic Binary Encoding
Basic Binary Addition
0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 10 (i.e. the result in this "column" is 0 with a "carry" of 1 that needs to
be added to the next position to the left)
Logic Gate Application for Binary Addition
Truth Table for Single Bit Addition:
|
INPUTS |
OUTPUTS |
|
A |
B |
C |
R |
|
0 |
0 |
0 |
0 |
| 0 |
1 |
0 |
1 |
| 1 |
0 |
0 |
1 |
| 1 |
1 |
1 |
0 |
Addition of "words" with multiple "bits" extends this logic.
Selector
A collection of input wires or "bits" is "decoded" to turn on ("select") exactly one (output) circuit.
(This is contrary to Englander's definition in "The Architecture of Computer Hardware and
Software", page 720).
Multiplexor
A single input wire (at any one time) from a collection of possible inputs, is "encoded" into a
pattern on a smaller collection of wires. A multiplexor performs the reverse function of a
"selector". (The 2-input to 1-output ciruit described by Englander, as noted above, is a
multiplexor).
Memory Circuits
A single memory "bit" must have the ability
- to have a data value of either 0 or 1 "written" to it,
- to retain that value after the "write" request is done, and
- to return that retained value at a later time in response to a "read" request.
As another way of thinking about it:
- Sometimes the memory bit is Enabled (to be read from / written to); other times it is in a
"passive" remembering state
- When enabled, a signal must indicate if we are trying to Read from it (the alternative being, write
to it)
- If we are writing to it, an Input data value (0/1) must be provided
- If we are reading from it, an Output path must be provided
Of course, to be very useful, we need many (millions) of these memory bits. A "Selector" circuit
is then required to permit us to access a particular bit (or collection of bits) based on an input
"address".
Application of Logic Gates to Basic Binary Encoding
Simple binary logic gates operate on one pair of single bits at a time, but most basic computer
operations work on pairs of multiple bits. In general this increases the speed at which the
computer operates. For example, comparing two patterns of 16 bits each in parallel should be 16
times faster than performing 16 separate comparisons on pairs of single bits.
Each logic gate takes a certain (small) amount of time to respond to a change in its inputs; this is
called the gate switching time. The time required to perform any basic computer instruction
depends upon the maximum number of logic gates signals must pass through to complete the
instructional operation (plus some other "overhead" factors.
The fastest instructions should therefore be those which involve no operational logic gates: the
shifts and rotates, followed by those which involve only one level of operational logic gates: the
bit level logical operators, and so on.
In actual practice, computer instructions are organized so as to start on regular internal clock
pulses (a 200MHz clock, for example, providing 200 million pulses per second). Even at today's
high clock speeds, modern gate switching times in VLSI is fast enough that multiple logic gates
can be managed within a single clock pulse "frame"; however, when the instruction becomes
complex enough that the number of logic gates on the longest path reaches a certain level, the
instruction will require multiple clock pulse "frames" to complete.
Fast Operations That Require No Operational Logic
Gates
Shift
- Left Shift - each input bit is reproduced as an output bit one position further to the left
except for the left-most input bit which is ignored (or copied to a status flag); the
right-most output bit is set to 0.
For example, LeftShift of (00110101) would be (01101010)
Note, as a result of this "shift" each bit gets moved to a position with double the weight
of its original position, and (provided no 1-valued bit is lost off the left-end) the result
for an unsigned binary encoded number is twice the original value.
- Right Shift (Logical) - same as the Left Shift except for the direction of the shift;
RightShift of (00110101) would be (00011010), with the right-most 1 being lost (or
copied to a status flag).
For an unsigned binary encoded number, the RightShift is a fast method for
dividing by 2.
- Right Shift (Arithmetic) - many computers also include another version of the
RightShift in which the left-most output bit is a copy of the left-most input bit (instead
of being automatically 0).
This is sometimes called the "Arithmetic" Right Shift because of its use with a signed
binary encoding scheme, called 2's Complement.
Rotate
Bit Manipulation with a Single Layer of Operational
Gates
Note that while these computer operations have the same names as the logic gates on which they
are based, they operate on two words in parallel and not on a pair of bits.
- OR - Turning Selected Bits of a Word "On"
- If we wish to force the right-most two bits of a 6-bit word to be "on" (we want the
result to look like xxxx11, where the x's represent the original bit values),OR the
original pattern with 000011
- AND - Turning Selected Bits of a Word "Off"
- If we wish to force the middle two bits of a 6-bit word to be "off" (we want the result
to look like xx00xx)AND the original pattern with 110011
- XOR - "Toggling" Selected Bits of a Word
- If we wish to reverse the left-most bits of a 6-bit wordXOR the original pattern with
110000
- NOT - Reversing All Bits of a Word
- NOT the original pattern (which is the same as XOR'ing with 111...1)
Unsigned Binary Addition - Multiple Layers of Gates
Addition of 2 Bits
- note that although there are two logic gates there is only one layer of gates required
Addition of 2 Multi-Bit Words
- note that because of the carry requirement from each column to the next, the number of layers
of gates increases with the number of bits in a word; effectively, from a gate switching point of
view, addition of 32-bit words should take 4 times longer than addition of 8-bit words.
More Complex Instructions and CISC Computers
CISC - Complex Instruction Set Computer
Factors Which Reduce Instruction Execution Speed
- larger number of logic gate layers in the instruction circuit
- requirements to access data value in external memory (with sub-factors:
the number of accesses required, and the type/speed of the external memory)
Alternative: RISC - Reduced Instruction Set Computer
Binary Operation Flags
Performing arithmetic operations produce results which require more space
(more circuits/bits) than were provided by individual input data values.
For simple operations, such as addition and subtraction, this "extra" space is only one bit and can
be handled by the use of a "Carry/Borrow" (single-bit) flag. Other operations, such a
multiplication and division, require different methods for handling this problem; these methods are
much less standard and vary considerably from computer to computer.