Transcript CSE 1520 Computer Use: Fundamentals

Week 6:
Gates and Circuits: PART I
•
READING: Chapter 4
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits
What is a “gate”?
• A gate is a device that performs a basic operation on electrical
signals
What is “circuit”?
• Gates are combined to form different “circuits” to perform more
complicated tasks
2
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits
Three notational methods to describe the behavior of gates:
1. Boolean expressions: A form of algebra in which variables and
functions take on only one of two possible values (0 and 1)
2. Logic diagrams: graphical representation of a circuit
3. Truth tables: defines the function of a gate by listing all possible
input combination and the corresponding output.
3
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits
• A gate or logic gate performs only one logical function. Each gate
accepts one or more input values and produces a single output value.
A0
A1
...
Logic Gate
X
An
Six types of logic gates:
1.
2.
3.
4.
5.
6.
NOT
AND
OR
XOR
NAND
NOR
4
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits: NOT Gate
• Also referred to as an “inverter”
• If the input value is 1, the output is 0; if the input value is 0, the
output is 1
Boolean Expression
Logic diagram Symbol
Truth Table
• Sometimes the “ ’ ” mark is replaced by horizontal bar placed
over the value:
X  A'  A
5
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits: AND Gate
• If the two input values are both 1, the output is 1; otherwise,
the output is 0
Boolean Expression
Logic diagram Symbol
Truth Table
• Sometimes the “ . ” mark is replaced by the asterisk symbol “ * ”
6
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits: OR Gate
• If both input values are both 0, the output is 0; otherwise, the
output is 1
Boolean Expression
Logic diagram Symbol
Truth Table
7
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits: XOR or exclusive OR Gate
• If the two inputs are the same, the output is 0; otherwise, the
output is 1
Boolean Expression
Logic diagram Symbol
Truth Table
• Not the difference between the XOR gate and the OR gate; they only
differ in one input situation:
• When both input signals are 1, OR gate produces a 1 and the XOR gate
produces a 0
8
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits: NOR Gate
• The NOR gate is essentially the opposite of the OR gate. That
is, the output of a NOR gate is the same as if you took the
output of an OR gate and put it through a NOT gate
Boolean Expression
Logic diagram Symbol
Truth Table
9
EECS 1520 -- Computer Use: Fundamentals
Gates and Circuits: NAND Gate
• The NAND gate is the opposite of the AND gate.
Boolean Expression
Logic diagram Symbol
Truth Table
10
EECS 1520 -- Computer Use: Fundamentals
Transistors
How do we implement the “gates”?
• A gate uses one or more transistors to establish how the input values
map to the output value
• A transistor acts like a “switch”.
• It either turns on to conduct electricity or turns off to block the flow of
electricity
11
EECS 1520 -- Computer Use: Fundamentals
Transistors
• A transistor has three terminals: source, base and emitter
source
output
base
emitter
• When an electrical signal is grounded, it has 0 volts!
• If the source signal is pulled to ground, the output signal is low
• If the source signal remains high, the output signal is high
output is “0”
output is “1”
12
EECS 1520 -- Computer Use: Fundamentals
Transistors – NOT Gate
• The output is determined by the base electrical signal.
source
Vout
Vin
base
Vin
Vout
1
0
0
1
emitter
• If Vin is high, the source is pulled to ground and Vout is low (i.e. 0)
• If Vin is low, the source is not grounded and Vout is high (i.e. 1)
“NOT Gate” needs 1 transistor
13
EECS 1520 -- Computer Use: Fundamentals
Transistors – NAND Gate
source
Vout
Vin1
Vin2
Vin1
Vin2
Vout
0
0
1
0
1
1
1
0
1
1
1
0
emitter
• If Vin1 and Vin2 are high, the source is pulled to ground and Vout is low (i.e. 0)
• If Vin1 and Vin2 are low, the source is not grounded and Vout is high (i.e. 1)
• If either Vin1 or Vin2 is low, the source is not grounded and Vout is high (i.e. 1)
“NAND Gate” needs 2 transistors
14
EECS 1520 -- Computer Use: Fundamentals
Transistors – NOR Gate
source
Vout
Vin1
Vin2
emitter
emitter
Vin1
Vin2
Vout
0
0
1
0
1
0
1
0
0
1
1
0
• If Vin1 and Vin2 are high, the source is pulled to ground and Vout is low (i.e. 0)
• If Vin1 and Vin2 are low, the source is not grounded and Vout is high (i.e. 1)
• If either Vin1 or Vin2 is low, the source is grounded and Vout is low (i.e. 0)
“NOR Gate” needs 2 transistors
15
EECS 1520 -- Computer Use: Fundamentals
Transistors – OR Gate
• Since OR gate is the opposite of NOR gate, how many transistors would you
think will be required to implement the “OR” gate?
“OR Gate” needs 3 transistors
16
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• Gates are combined into circuits by using the output of one gate as the
input for another gate.
• For example:
17
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• For example:
Logic diagram Symbol
Truth Table
•
Since there are 3 inputs, there are
8 possible outcomes
18
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• For example:
Logic diagram Symbol
Boolean expression
• D=AB
• E = AC
• X = AB + AC
19
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• Now, we want to investigate the following Boolean expression:
X = A(B+C)
• How do we want to create the logic diagram (called circuit 2) of the
above Boolean expression?
- We have an inner function which consists of an “OR” gate
between B and C
- We then have an outer function which is an “AND” gate
between A and (B+C)
Logic diagram Symbol:
(circuit 2)
A(B+C)
B+C
20
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• We have the following:
Boolean expression:
X = A(B+C)
Logic diagram Symbol:
A(B+C)
B+C
Truth table:
A
B
C
B+C
A(B+C)
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
1
21
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• Circuit 1:
• Circuit 2:
A(B+C)
B+C
A
B
C
D
E
X
A
B
C
B+C
A(B+C)
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
•
Their results are identical!
22
EECS 1520 -- Computer Use: Fundamentals
Combinational Circuits
• We have therefore demonstrated circuit equivalence
• That is, both circuits produce the same results for each input
combination
• Boolean algebra allows us to apply provable mathematical
principles to help us design logical circuits
• From the previous example:
X = AB + AC = A(B+C)
23
EECS 1520 -- Computer Use: Fundamentals
Properties of Boolean Algebra
• DeMorgan’s law, in particular, is very useful in Boolean algebra.
• For instance, it means that:
___
___
___
1 NAND gate is equivalent to 2 NOT gates with an OR gate
24