Transcript Designing Circuits - Department of Computer and Information Science

Designing Circuits
CSCI N301: Fundamental Computer
Science Concepts
Copyright ©2004  Department of Computer & Information Science
Goals
By the end of this lecture, you should
understand …
• How to use the Sum-Of-Products to
construct circuits.
• How to construct a basic, binary input
circuit.
• How to construct more complex circuits,
using three or more inputs.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Where We’ve Been
• We are developing an increasingly
complex model of computer operation.
• We began with the switch and saw how
we can use it encode information in
digitized form.
• We combined switches into gates and saw
how we can use Boolean logic process
binary information.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Where We’re Going
• We will learn how to combine gates to
form circuits.
• We are looking at a special kind of circuit –
a combinational circuit – although from
here on out we simply refer to circuit.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
What is a Circuit?
• A circuit is a combination of logic gates that
changes a set of binary inputs into a set of
binary outputs in which the values of the outputs
depend only on the electrical current (high/low
voltage) values of the inputs.
• By the way, there are also circuits that depend
also on the previous values of the inputs, but we
won’t consider them in this class.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Circuit Analysis
• Circuits depend on Boolean logic, which we introduced
last lecture.
• Boolean notation allows us to create logical expressions
using Boolean operators.
• For example:
Examples of Boolean Expressions
Using Operator Names
Using Symbols
Q = (A OR B)
Q = (A + B)
Q = NOT ((A OR B) AND (NOT B)) Q = ~ ((A + B) • (~B))
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Circuits & Boolean Expressions
• You can express every Boolean expression
using a circuit diagram.
• Conversely, you can represent every circuit
diagram as a Boolean expression.
• Of course, we aren’t going after just any circuits
here…. we want to develop the skills to
construct and analyze circuits that can perform
the logic and arithmetic calculations that a
computer requires to operate.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Constructing Circuits
• We can use any one of several algorithms for
constructing circuits, just like there were several
different algorithms for modeling gates.
• We will use an algorithm called the sum-ofproducts algorithm to design our circuits. When
using the sum-of-products algorithm, we move in
a step-by-step process to build a circuit.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
The Four Steps for the
Sum-Of-Products Algorithm
1.
2.
3.
4.
From a problem statement, construct a truth table that
describes what the voltage output should be under
each possible combination of voltage inputs.
From the truth table, identify those gate combinations
that produce positive voltage output, and write sub
expressions for those conditions.
Combine the sub expressions (a.k.a. “Boolean terms”)
into a single Boolean expression.
Draw a circuit diagram that corresponds to the
Boolean expression.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sub-of-Products Example
• Problem Statement:
“Design a circuit that has two inputs (A, B)
and one output, Q. Q = 1 iff* both a and b
are the same voltage.”
* - iff = “If and only if”
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sub-of-Products Example
• How to read the problem:
– We two input lines coming into a circuit. One input line
is labeled A and the other input line is labeled B.
– There is one output line, labeled Q.
– The output voltage on Q is high if and only if both B
and B have high voltage, or both A and B have low
voltage (A and B have the same voltage).
– By inference, when A is high and B is low, or when A
is low and B is high, the output line Q is low.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sub-of-Products Example: Step 1
• STEP 1: Construct a truth table to illustrate the
problem statement:
INPUTS
OUTPUT
A
B
Q
0
0
0
1
1
0
1
1
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sub-of-Products Example: Step 2a
• STEP 2a: Scan the table to determine when the Output
column is TRUE. Identify those instances:
INPUTS
A
0
0
B
0
1
OUTPUT
Q
1
0
1
0
0
1
1
1
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sum-of-Products Example: Step 2b
• From the table we can identify 2 instances of
high output:
– Where both A and B were 0
– Where both A and B were 1
• Now let’s create Boolean sub expressions for
each instance (STEP 2b):
– ~A • ~B (NOT A AND NOT B)
– A • B (A AND B)
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sum-of-Products Example: Step 3
• STEP THREE: Combine the Boolean sub-expressions
(or terms) into an overall expression.
• In our example, we are building an OR statement. We
are saying Q can be high with one set of input conditions
(~A • ~B), or using a second set of input conditions
(A • B).
• Therefore, our expression will be connected with the OR
operator. There are two terms – one for each high
voltage output.
• Our single Boolean Expression is:
Q = (~A • ~B) + (A • B)
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Sum-of-Products Example: Step 4
• STEP FOUR: Build the circuit to represent our
Boolean Expression.
A
Q
B
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Where We Were Limited
• The example we looked at took 2 inputs.
But, of course, circuits are not limited to
just two inputs.
• We can extend our process to include n
inputs.
• Consider the following overall remarks
regarding how we extend our model to
build more complex circuits …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
General Rules/Guidelines
• When you add additional input lines, it becomes possible to see
some general patterns…
• In the step from problem statement to truth table, remember this:
– A problem with n input lines will produce a truth table with 2n
elements (or rows)… for example, 2 inputs lines result in 4
possible voltage combinations, while 3 input lines result in 8
possible combinations.
• In the step from truth table to circuit drawing, remember this:
– We can combine various high sub-conditions joined by an OR
using an AND gate. To better manage the spacing required to
include the or gates and input lines, experienced students
sometimes draw their circuits from right to left.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Do One!
• Consider the following problem statement.
Analyze it using the 4 step, Sum of
Products Algorithm to produce a circuit.
• Problem Statement: “Design a circuit that
takes 3 inputs, and outputs a high value
IFF exactly two of the inputs are high.”
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Problem Solution
• Step One: Create truth table
INPUTS
OUTPUTS
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Q
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Problem Solution
• Step One: Create truth table
INPUTS
OUTPUTS
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Q
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Problem Solution
•
Step Two: Scan the table to determine when the Output column is TRUE.
Identify those instances:
INPUTS
OUTPUTS
A
B
C
Q
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Problem Solution
•Step Three: Create Boolean expression
Q = (~A * B * C) +
(A * ~B * C) +
(A * B * ~C)
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Problem Solution: Step 4
• STEP FOUR: Build the circuit to represent our
Boolean Expression.
Click Button for the xLogicCircuits Applet
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Simplifying Boolean Expressions
• When you look at complicated input
combinations which result in Boolean
expressions with many terms, you can
save a lot of time by using some
simplification rules. These rules allow you
to reduce and combine terms.
• You can find a summary of these simple
Boolean rules on the next slide …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Boolean Axioms
•
•
•
•
•
•
TRUE * P = P
FALSE * P = FALSE
FALSE + P = P
TRUE + P = TRUE
P+Q=Q+P
P*Q=Q*P
•
•
•
•
•
(P + Q) +R = P + (Q + R)
(P * R) * Q = P * (R * Q)
P * ~P = FALSE
P+P=P
P*P=P
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
De Morgan’s Laws
• In addition to the preceding axioms, a
mathematician named de Morgan first provided
proof of the following laws:
– ~(P * Q) = ~P + ~Q
– ~(P + Q)= ~P * ~Q
• In your next lab assignment, you will confirm
de Morgan’s Laws. You can easily do the lab by
constructing a truth table with inputs for P, Q,
P*Q, ~(P*Q), ~P, ~Q, and ~P+~Q.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Where We Are Going
• Now that you have some understanding of
how to build a general circuit, we will look
at some specific ones.
• Next time, we’ll consider circuits that play
particularly important roles in computer
operation: adders and Arithmetic Logic
Unit processing.
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