# CSC258H1 Lecture Notes - Canonical Normal Form, Boolean Expression, Group For The Study Of Reactive Motion

46 views1 pages

Published on 20 Apr 2013

Department

Computer Science

Course

CSC258H1

Professor

Coverting SOM to gates

o Once you have a Sum-of-Minterms expression, it is easy to convert

this to the equivalent combination of gates

o Ex.

Y = m0 + m1 + m2 + m3

Y = A*B*C + A*B*C + A*B*C + A*B*C

Reducing circuits

o Note example of Sum-of-Minterms (above) circuit design

o To minimize the number of gates, we want to reduce the Boolean

expression as much as possible from a collection of minterms to

something smaller

Boolean algebra review

o Axioms

From this we can extrapolate

o Other Boolean identities

Commutative Law:

Associative Law:

Distributative Law:

Simpliciation Law:

Consensus Law:

Absorption Law:

De Morgan’s Laws:

Converting to NAND gates

o Last week, we talked about how a Sum-of-Products circuit could be

converted into an equivalent of NAND gates:

Based on de Morgan’s Law

Sum-of-Minterms task

o Given an expression , expand this into a SOM

Result:

SOM form

POM form

Reducing Boolean expressions

A

B

C

Y

0

0

0

0

0

0

1

0

0

1

0

0

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

Ex. about SOM, combine the middle and end terms:

o What is considered the “simplest” expression?

In this case, “simple” denotes the lowest gate cost (G) or the

lowest gate cost with NOTs (GN)

To calculate the gate cost simply

add all the gates together

For GN cost Include the

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

K-maps can be of any size & have any number of inputs

m0

m1

m3

m2

m4

m5

m7

m6

m12

m13

m15

m14

m8

m9

m11

m10

Since adjacent minterms only differ by a single value, they can

be grouped into a single term that omits that value

Once K-maps are created box groups of high ouput values

Boxes must be rectangular, and aligned with map

Box size must be a power of 2

Boxed may overlap with each other

Boxed may wrap across edges of map

Once the minial number of boxes that cover all the high outputs

are found, creates a Boolean expression from the inputs that are

common to all ements in the box

o Ex. using Karnaught Maps

0

0

1

0

1

0

1

1

Vertical box: Horizontal box:

Overall Equation:

o Can also use Karnaught Maps to group maxterms together as well

Karnaught Maps with maxterms involves grouping the zero

entires together, instead of grouping the entires with one values

M0

M1

M3

M2

M4

M5

M7

M6

M12

M13

M15

M14

M8

M9

M11

M10

## Document Summary

Reducing boolean expressions: once you have a sum-of-minterms expression, it is easy to convert this to the equivalent combination of gates, ex. Y = m0 + m1 + m2 + m3. Y = a*b*c + a*b*c + a*b*c + a*b*c. Reducing circuits: note example of sum-of-minterms (above) circuit design, to minimize the number of gates, we want to reduce the boolean expression as much as possible from a collection of minterms to something smaller. From this we can extrapolate: other boolean identities. Converting to nand gates: last week, we talked about how a sum-of-products circuit could be converted into an equivalent of nand gates: Sum-of-minterms task: given an expression ( ) , expand this into a som. 1: ex. given the above logic specs, can get the following. Then combine terms, like the last two: different final expressions possible depending combination process. In this case, simple denotes the lowest gate cost (g) or the lowest gate cost with nots (gn)