Transcript Some “facts” about software…

XOR Operator
• A short digression…
• … to introduce another Boolean operation: exclusiveOR (XOR)
A
B
A+B
0
0
0
0
1
1
1
0
1
1
1
0
XOR
XOR Operator
• Also referred to as
an “odd” function
since it returns a 1
only when an odd
number of 1’s are
input
A
B
C
A+B+C
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
Simplification
• Using the axioms to “prove” that a
simplified version of a circuit is
equivalent to the complex version takes
a special kind of person…
– …of which I’m not one
• Fortunately, there’s another way…
Karnaugh Maps
• Also known as K-Map
• Recall that an expression can be written
in the form
F(A,B,C) = Σ(0,2,4,5,6)
• Which means the functional value is 1
at binary input patterns 0, 2, 4, 5, 6 and
0 at all other input patterns
– What does the truth table look like?
K-Maps
• F(A,B,C) = Σ(0,2,4,5,6) is called a “sum
of minterms” representation
• The expression for such a
representation is
F(A,B,C) = A’B’C’ + A’BC’ + AB’C’ + AB’C + ABC’
• We could simplify this via the axioms,
right? (assuming we were that special
kind of person)
• It’s painful!!!
K-Maps
• A K-Map is a grid (map) where each square
corresponds to a minterm
BC
A
0
A
00
1
0
0 1
1
01
11
10
0 1 3 2
4 5 7 8
CD
A
B
0
1
AB
0
1
0 1
3 2
00
01
11
10
0 1 3 2
01 4 5 7 8
11 12 13 15 14
10 8 9 11 10
00
Note the ordering
here is Gray code,
not binary
K-Maps
• Notice how neighboring squares
(minterms) differ by a single bit…this is
the key to the whole thing
– Consider minterms 1 and 3
• 1: A’B’C
• 3: A’BC
– If we were to OR these together
• (A’B’C + A’BC) would simplify to A’C via the
axioms
K-Maps
• Great, now what do we do with them?
• Place 1’s on the squares that
correspond to minterms in the truth
table
• Place 0’s on all other squares
• Group adjacent 1’s into the largest
group whose size is a power of 2
K-Maps
• Notes:
– Adjacencies wrap top-to-bottom and left-toright
– 1’s can be part of more than one group
– When you are grouping adjacent squares
you’re essentially applying axiom 4 (x + x’
= 1) so the variable that is being “spanned”
can be removed from the minterm
Simplification via Axioms
(aka Proofs)
• Here’s a little insight that no one ever taught
me
F(x, y, z) = xy’z + x’y’z + x’yz
• Notice how the middle term shares two
elements with each of the others
• Using association, distribution, and inverse:
F(x, y, z) = y’z + x’yz
• One more application of distribution
F(x, y, z) = z(y’ + x’y)
• We could have arrived at a similar solution by
grouping the 2nd two terms
Simplification via Axioms
(aka Proofs)
• But, can we do better?
yz
x
0
1
00
01
11
10
0 1 1 0
0 1 0 0
F(x, y, z) = y’z + x’z = z(x’ + y’)
• Notice that we use the minterm x’y’z in
two groupings
• What does that mean in terms of an
axiomatic proof?
Simplification via Axioms
(aka Proofs)
• It means exactly this…
F(x, y, z) = xy’z + x’y’z + x’yz
F(x, y, z) = xy’z + x’y’z + x’y’z + x’yz
• …by idempotence over OR
• Now we can form two associative
groupings and arrive at the same
answer that the Karnaugh Map gave us
Karnaugh Maps
AB
CD
00 01 11 10
00
01
11
10
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
• What is the truth-table?
• What is the expression in
sum-of-minterms form?
• What is the simplified
expression?
• What is the (schematic)
logic gate
implementation?
Sum-of-Products
• This is what we previously called the
“sum-of-minterms”
• Form the largest power-of-two
groupings of 1’s on the K-map
• Create the schematic
Product-Of-Sums
• Instead of forming large adjacent
groups of 1’s (on the K-map), form large
adjacent groups of 0’s
– What does this mean in terms of the
original expression/truth-table?
– It means you have simplified F’, instead of
F
– To “fix” what you’ve done you need only
negate the final result them apply De
Morgan’s theorem
Example – Sum-of-Products
•
•
•
•
F(A,B,C,D) = Σ(0,1,2,5,8,9,10)
Form the truth-table
Form the K-map
Simplify the K-map using sum-ofproducts
• Formulate the boolean expression
• Draw the schematic diagram
Example – Sum-of-Products
B’
D’
C’
A’
D
F
Example – Product-of-Sums
•
•
•
•
F(A,B,C,D) = Σ(0,1,2,5,8,9,10)
Form the truth-table
Form the K-map
Simplify the K-map using product-ofsums
• Formulate the boolean expression
• Negate, apply De Morgan’s
• Draw the schematic diagram
Example – Product-of-Sums
B’
D
A’
F
C’
D’
So What?
• As it turns out, the sum-of-products can
be easily implemented with NAND gates
• Similarly, the product-of-sums can be
easily implemented with NOR gates
• This may greatly simplify the design
thus saving us money!
NAND/NOR Implementations
B’
D’
C’
A’
D
B’
D
A’
C’
D’
Combinational Circuits
• Definition: A connected arrangement of
logic gates with a set of inputs and
outputs
• Specifically, they have no memory!
• Basically, it’s the stuff we’ve been
working on so far
Combinational Circuit Design
• Design a Half-Adder
– A combinational circuit that adds 2 bits
•
•
•
•
Input 1 is call the “Augend”
Input 2 is called the “Addend”
Output 1 is called the “Sum”
Output 2 is called the “Carry”
Augend
Sum
Half-Adder
Addend
Carry
Combinational Circuit Design
• Design a Full-Adder
– A combinational circuit that adds 3 bits
•
•
•
•
•
Input 1 is call the “Augend”
Input 2 is called the “Addend”
Input 3 is call the “Carry-in”
Output 1 is called the “Sum”
Output 2 is called the “Carry-out”
Carry-in
Augend
Addend
Sum
Full-Adder
Carry-out
Homework
• Pages 37, 38: 1-8, 1-9, 1-10, 1-12, 1-13
• Due Thursday (next lecture)