Chap#4.
Simplification of Boolean Functions
@
Topic :
-
Minimizing
the number of operator to produce less cost
but more delay
-
On
critical path ,operator can be Implemented with fastest gates.
-
ch#3
minimize with algebraic manipulation
-
ch#4
minimize with systematic techniques
4.1
The Map Representation
-
Boolean cubes (
P051 )
each vertex
represent minterm
-
Representation of carry
& sum function (
P123 )
-
Prime implicant (PI)
: Subcube that is not contained within
any other subcube (largest possible subcubes)
-
essential prime implicant
(EPI) : subcube
that includes a 1-minterm that is not included
in any other sub cube
-
Karnaugh
map : 2-D form of cube
-
Boolean
cube and corresponding karnagh map
( P124A )
-
Two - variable map (
P124B )
-
Three - variable map (
P125A )
-
Map of 2 - variable function
( P125B )
-
Map of carry &
sum function ( P126 )
-
Four - variable map (
P127 )
-
Greater - than & less
- than function ( P128A )
-
Five - variable map (
P128B )
-
e.g. subcube of sizes
8 & 16 ( P129A )
-
Six - variable map (
P129B )
-
e.g. subcube of size 16
( P130 )
4.2
The Map Method Of Simplification
-
Four basic steps (
P131 )
1) Map Generation
2) Prime Implicant
Generation
3) Essential Implicant
Selection
4) Create Minimal
Cover
-
e.g. 4.1 F = w'y'z'
+ wz + xyz + w'y ( P132 )
-
e.g. 4.2 F = w'x'yz'
+ w'xy + wxz + wx'y' + w'x'y'z' ( P133
)
4.3
Don't-Care Conditions
-
Don't - care condition
-
e.g. 4.3 don't - care
condition ( P136 )
4.4
The Tabulation Method
@
4.4.1 PI Generation
-
e.g. 4.4 PI Generation
( P139 )
@
4.4.2 Minimal Cover Generation
-
e.g. 4.5 EPI selection
( P142 )
-
e.g. 4.6 Minimal cover
generation ( P144 )
1) EPI : p1 and p2
uncover m7, m13, m15
2) m7 covered by p3
or p5
3) m13 covered by
p4 or p6
4) m15 covered by
p5 or p6
5) (p3 + p5) (p4 +
p6) (p5 + p6)
6) (p3 + p5) (p4p5
+ p5p6 + p4p6 + p6)
7) (p3 + p5) (p4p5
+ p6)
8) p3p4p5 + p4p5 +
p3p6 + p5p6
9) To cover m7, m13,
m15
by using p4 and p5 or p3 and p6
or p5 and p6
4.5
Technology Mapping For Gate Arrays
-
Conversion & optimization Rules (
P146A )
-
Translation of SoP & PoS to NAND & NOR(
P146B )
-
e.g. 4.7 conversion to NAND (NOR) gates (
P147 )
-
e.g. 4.8 Gate decomposition
(10-input to 3-input) (
P149 )
-
e.g. 4.9 Technology mapping
for gate arrays ( P151 )
-
e.g. 4.10 Design retiming
* Q : Implement the
carry-look-ahead function C4
using 3-input NAND gates
* A : gi
= xi yi
pi = xi + yi
ci+1
= xi yi + xi ci + yi ci
= xi yi + ( xi + yi ) ci
= gi + pi ci
c1 = g0 + p0 c0
c2 = g1 + p1 c1
c3 = g2 + p2 c2
c4 = g3 + p3 c3
= g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1
p0 c0
* Two - Implement
( P153 ) (Note
: Fig (c) lack one NOT)
* Mapping Procedure
( P154 )
1) decomposition
2) conversion
3) elimination
4) retiming
4.6
Technology Mapping For Custom Libraries
-
F = w'z' + z(w+y)
-
Technology mapping for
custom libraries ( P156
)
-
Conversion procedure for
custom libraries ( P157
)
4.7
Hazard-Free design
-
Design with static-1-hazard
( P159 )
-
Hazard-free design
( P160 )
-
Dynamic hazard
( P162 )
4.8
Chapter Summary
4.9
Further Readings
4.10
Problems
-
4.3
(d), 4.4 (c), 4.5 (d), 4.6 (d),
4.9 (c),
4.10
(b), 4.11 (a), 4.13 (a), 4.17,
4.18
