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

46 views1 pages
School
UTSG
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
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
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
Unlock document

This preview shows half of the first page of the document.
Unlock all 1 pages and 3 million more documents.

## 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)