Class Notes
(809,049)

Canada
(493,506)

University of Toronto St. George
(42,805)

Computer Science
(743)

CSC258H1
(46)

Steve Engels
(31)

Lecture

# jan16ce.docx

Unlock Document

University of Toronto St. George

Computer Science

CSC258H1

Steve Engels

Winter

Description

Coverting SOM to gates Reducing Boolean expressions
o Once you have a Sum-of-Minterms expression, it is easy to convert A B C Y
this to the equivalent combination of gates 0 0 0 0
o Ex. 0 0 1 0
Y = m 0 + m 1 m + 2 3 0 1 0 0
Y = A*B*C + A*B*C + A*B*C + A*B*C
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
o Ex. given the above logic specs, can get the following
Then combine terms, like the last two:
o Different final expressions possible depending combination process
Reducing circuits
o Note example of Sum-of-Minterms (above) circuit design Ex. about SOM, combine the middle and end terms:
o To minimize the number of gates, we want to reduce the Boolean
o What is considered the “simplest” expression?
expression as much as possible from a collection of minterms to
something smaller In this case, “simple” denotes the lowest gate cost (G) or the
Boolean algebra review lowest gate cost with NOTs (GN)
To calculate the gate cost simply
o Axioms
add all the gates together
For GN cost Include the
From this we can extrapolate cost of NOT gates
o Karnaugh maps (K-maps)
The technique used to to find the
“simplest” expressions
Karnaught maps are a 2D gird where the values are minterms
Adjacent minterms only differ by a single value
Values of the grad are the output for that minterm
o Other Boolean identities K-maps can be of any size & have any number of inputs
Commutative Law:
m0 m1 m 3 m 2

More
Less
Related notes for CSC258H1