Transcript Gates - Department of Computer and Information Science

Introducing Gates
CSCI N301: Fundamental Computer
Science Concepts
Copyright ©2004  Department of Computer & Information Science
Goals
By the end of this lecture, you should
understand …
• How modern computers use transistors as
switches.
• What a gate is.
• How to construct a pump model of a gate.
• How to work with the basic Boolean
operators AND, OR and NOT.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Where We’ve Been
• We’ve considered switches, and devised
ways to encode information in switch
math.
• We’ve learned that the switch is the
fundamental computer component.
• Today, we’ll learn that modern computers
use a specific kind of switch, called a
transistor.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Transistors
• The transistor is a solid-state binary device (the
phrase “solid-state” means that an electrical
current follows a path through solid semiconductive material).
• Transistors replaced vacuum tubes in
computers, beginning in the 1960s.
• Transistors switch between two states – on and
off – electronically instead of mechanically.
• With the movement to transistors came
advances in size (transistors are much smaller)
and speed (transistors are much faster).
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Where do we go from here?
• We have switches, which we now know
are transistors. Transistors are either at a
low or high voltage setting.
• We need to consider how to
set/manipulate switches.
• To understand this, we’ll move up a level
of complexity, to the world of gates …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Gates
• A gate is an electronic device that operates on a
collection of binary inputs to produce a binary
output.
• This is exactly what we need – the ability to take
binary inputs (which is all we have inside the
computer), manipulate them according to some
set of processing rules and produce results
which a computer can store in binary form.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Gates: The Tool Set
• In the same way that binary math was the
toolset we needed for binary encoding, we
need to use a toolset for manipulating
gates.
• The toolset we’ll use is Boolean logic,
named after George Boole, the English
mathematician and pioneer of modern
symbolic logic.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Logic
• Boole’s observed that truth values can be
mapped to binary math.
• The mapping is straightforward:
– We can represent TRUE by using a 1.
– We can represent FALSE by using a 0.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Logic, the Other Half
• We are half way there … we know how to
map True/False to 1/0.
• Now we need a branch of mathematics
that presents a set of rules for
manipulating truth values.
• That’s the second half of Boolean logic …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Truth Tables
• Boole mapped truth tables that tell us how
to connect truth values.
• There are three primary operations that we
can perform on truth values:
– Two procedures that combine two truth values
(Combinational Procedures)
– One procedure that reverses a truth value
(Complementary Procedure)
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Combinations
• There are two forms of Boolean
combinations (both are binary operators,
they combine two values):
– Or
– And
• We need one other piece of information to
discuss this – we need to refine our
definition of a Boolean Value …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Values
• There are two Boolean values: True and
False.
• We can combine these two values to
produce Boolean expressions.
• A Boolean expression is one which we can
evaluate as being either True or False.
• Let’s try an example …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Values and
Expressions
• Consider the following sentence: “It is raining,
and the radio is playing.”
– I could assign a value, either True or False, to each of
the two phrases in that sentence.
– It is raining right now, so I will replace that part of the
sentence with a “T” for True.
– The radio is not playing, however, so I will replace
that part of the sentence with an “F” for false.
– If only I knew what to do with the connector in that
sentence, the word AND….
– And that’s what Boole’s truth tables gave us!
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Back to Combinations
• There are two ways to connect truth values:
– Using the OR operator
– Using the AND operator
• Possible TRUE outcomes of the OR operator:
– Condition A is TRUE
– Condition B is TRUE
– BOTH Condition A & Condition B are TRUE
• There is only one TRUE outcome of the AND
operator: both conditions MUST be true!
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Back to Our Example …
• Again, consider the sentence: “It is raining, and the radio
is playing.”
• Let’s evaluate the sentence using Boolean logic:
– It is raining, so I get a “T” for the first phrase.
– My radio is not playing, so I get an “F” for the second phrase.
– The connector is an AND, which means both phrases have to be
true for the entire expression to be true, so …
– Since the second phrase is FALSE, and since the operator
connecting the two phrases is the AND operator, we can
evaluate the entire sentence as having a truth value of FALSE.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Truth Table for AND
1st
Phrase
2nd
Phrase
Overall
Expression
T
T
T
T
F
F
F
T
F
F
F
F
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
AND Operator Summary
• There is only one possible way to produce
an overall TRUE expression from two
Boolean phrases connected with the AND
operator: both phrases have to be TRUE
for the entire combination to be TRUE.
• All other combinations result in a FALSE.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Truth Table for OR
1st
Phrase
2nd
Phrase
Overall
Expression
T
T
T
T
F
T
F
T
T
F
F
F
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
OR Operator Summary
• There is only one possible way to produce
an overall FALSE expression from two
Boolean phrases connected with the OR
operator: both phrases have to be FALSE
for the entire combination to be FALSE.
• All other combinations result in a TRUE.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
NOT Operator Summary
• Unlike AND and OR (which are both binary
operators), NOT is a unary operator (it works
with only 1 value).
• NOT “reverses the charge” of a value:
– A TRUE (1) becomes a FALSE (0). The complement
of TRUE is FALSE.
– A FALSE (0) becomes a TRUE (1). The complement
of FALSE is TRUE.
• NOT is also known as the complementary
operator.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Truth Table for NOT
Phrase
Overall
Expression
T
F
F
T
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Complex Comparisons
• If are testing more than two phrases, then you’ll need to
use the Boolean Operator Hierarchy:
– NOT
– AND
– OR
• A better idea is to use parentheses to indicate which
conditions your program should evaluate first.
• When using these truth tables, you can combine
switches in two ways (using AND or using OR) to
produce a single binary output from multiple binary
inputs. The NOT operator also produces a single binary
output, the complement of the input.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Moving from Comparisons to Gates
• Using Boolean operators, we have the
capability to take individual switches, and
connect them in gates.
• We can then wire gates to perform
Boolean logic – AND comparisons, OR
comparisons or NOT complements – base
on the switch settings.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
The AND Gate
• To construct an AND gate, we take two
switches in series.
• If either switch is set to zero, voltage is
impeded from flowing, and the output will
be a zero.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
The OR Gate
• To construct an OR gate, we connect two
switches in parallel.
• As long as voltage exists on at least one
input line, the output line will be high.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
The NOT Gate
• Only one switch is required to construct a NOT
gate. Why?
• A resistor is placed on the output line to force
voltage flow through the transistor.
• If the input line is low, the transistor delivers
current to the output line, which is high.
• If the input line is high, the transistor blocks flow
to the output line, and the output line remains
low.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Getting the Picture
• This all sounds reasonable, but a diagram
method would be helpful.
• Computer engineers developed several
models as visual teaching tools for gate
operation.
• We will use the “pump” model …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Pump Model: Off
Imagine two water pipes with pump
headers, as illustrated to the left. The
vertical pipe is open, and has water in
it, which unless impeded, will flow
downward (the path of least
resistance). The horizontal pump is off,
offering no impedance to the water in
the vertical pipe. So, we get output at
the bottom. Look at the horizontal
pump again. See the curly wire? That is
a spring… if we turn the pipe on, it
pushes the spring, which moves the
black block into the vertical pipe, and
flow would be impeded.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Pump Model: On
Here is the vertical pipe
again; this time, the
horizontal pump is
turned on. Notice that
the spring has pushed
the black block into the
horizontal pipe, and
water can’t flow
through.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Complex Pumps
Voltage 2
Input 1
Input 2
Voltage 1
Some key symbols: the voltage
lines, sometimes called Control
Lines, ALWAYS have initial
voltage. The Input Lines can be
high or low. Points along the way
can be measured to see if
voltage exists or not. When an
input line is HIGH, it’s “pump” is
on, and it moves a block to
impede. When an input line is
LOW, it’s “pump” if off, and it
offers no impedance to the
voltage line.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Complex Pumps
Voltage 2
A
Input 1 - High
B
Input 2 - Low
E
C
D
Voltage 1
Now, there is voltage on the
control lines, so points A and D
are high. Input 1 is on (pump
on), input 2 is off (pump off) .
Input 1 closes and impedes, so
current is trapped and can’t pass
to B; B is off. Input 2 is off, so
the “0” at point B passes
unimpeded to point C.
Remember, D had voltage, and
now that C is low, it can’t impede
the flow of D across, so the
voltage at point E is high.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Complex Pumps
Voltage 2
Still voltage on the control lines,
so points A and D are high. Input
1 is off (pump off), input 2 is on
(pump on) . Input 1stays open
and doesn’t impede, so current
passes to B. Input 2 is on, so the
“1” at point B can’t pass to point
C. Remember, D had voltage, and
now that C is low, it can’t impede
the flow of D across, so the
voltage at point E is still high.
A
Input 1 - Low
B
Input 2 - High
E
C
D
Voltage 1
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Complex Pumps
Voltage 2
Still voltage on the control lines,
so points A and D are high. Input
1 is off , input 2 is off . Input 1
stays open and doesn’t impede,
so current passes to B. Input 2 is
off, so the “1” at point B passes
to point C. Remember, D had
voltage, but the high voltage at C
means that Voltage 2 closes the
flow to D, impeding it. Thus the
voltage at E is off.
A
Input 1 - Low
B
Input 2 - Low
E
C
D
Voltage 1
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Complex Pumps
Voltage 2
Still voltage on the control lines,
so points A and D are high. Input
1 is high , input 2 is high. Input 1
closes and impedes, so no
current passes to B. Input 2
closes, so is downstream of it has
no current, either. Thus C is low.
Remember, D had voltage, which
passes unimpeded to E. Thus
the voltage at E is high.
A
Input 1 - High
B
Input 2 - High
E
C
D
Voltage 1
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
That Was an OR Gate!
What we just illustrated using the Pump Model, of course,
was an Or gate. Every combination of two inputs in which
at least one of the inputs was high produced a 1. The case
of two low inputs was the only case which resulted in a O
for an output. Notice that we took two binary outputs,
performed Boolean logic processing, and produced a single
binary output.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Up a Level of Abstraction
• As you might imagine, while the Pump
Model is a good teaching tool, it is a
cumbersome notation for experienced
electrical engineers
• A more abstract notation exists for
constructing and evaluating Boolean gates
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Gate Notation
NOT
AND
OR
SYMBOLS
~
·
+
┘
GATE
CIRCUIT
DIAGRAM
A
Q
A
Q
B
A
Q
B
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
What’s Next?
• In the next unit, we’ll expand our
knowledge of Boolean logic a bit by
combining gates in a higher level of
complexity to create circuits ...
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Questions?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science