CSEE 3827: Fundamentals of Computer Systems

Boolean Algebra M&K 2.3-2.5

Agenda
Standard Forms Product-of-Sums (PoS) Sum-of-Products (SoP) conversion between Min-terms and Max-terms Simplication via Karnaugh Maps (K-maps) 2, 3, and 4 variable Implicants, Prime Implicants, Essential Prime Implicants Using K-maps to reduce PoS form Dont Care Conditions
2

Standard Forms
There are many ways to express a boolean expression

F = XYZ + XYZ + XZ = XY(Z + Z) + XZ = XY + XZ

It is useful to have a standard or canonical way Derived from truth table Generally not the simplest form

Two principle standard forms

Sum-of-products (SOP) Product-of-sums (POS)

Product and sum terms

Product term: logical AND of literals (e.g., XYZ) Sum term: logical OR of literals (e.g., A + B + C)

PoS & SoP

Sum of products (SoP): OR of ANDs

e.g., F = Y + XYZ + XY

Product of sums (PoS): AND of ORs

e.g., G = X(Y + Z)(X + Y + Z)

Converting from PoS (or any form) to SoP

Just multiply through and simplify, e.g.,

G = X(Y + Z)(X + Y + Z) = XYX + XYY + XYZ + XZX + XZY + XZZ = XY + XY + XYZ + XZ + XZY + XZ = XY + XZ

Converting from SoP to PoS

Complement, multiply through, complement via DeMorgan, e.g.,

Note: X = X F = YZ + XYZ + XYZ F' = (Y+Z)(X+Y+Z)(X+Y+Z) = YZ + XY + XZ (after lots of simplication)

F = (Y+Z)(X+Y)(X+Z)

Minterms
e.g., Minterms for 3 variables A,B,C
A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 minterm m0 ABC m1 ABC m2 ABC m3 ABC m4 ABC m5 ABC m6 ABC m7 ABC

A product term in which all variables appear once, either complemented or uncomplemented (i.e., an entry in the truth table). Each minterm evaluates to 1 for exactly one variable assignment, 0 for all others. Denoted by mX where X corresponds to the variable assignment for which mX = 1.

Minterms to describe a function

sometimes also called a minterm expansion or disjunctive normal form (DNF)

This term is TRUE when A=0,B=1,C=0

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

F = ABC + ABC + ABC + ABC + ABC

1 1 1 0 1 1 0 0

0 0 0 1 0 0 1 1

F = ABC + ABC + ABC

Minterm example, seen another way

The logical OR of all minterms for which F = 1.
A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 minterm m0 ABC m1 ABC m2 ABC m3 ABC m4 ABC m5 ABC m6 ABC m7 ABC F 1 1 1 0 1 1 0 0

m0 1 0 0 0 0 0 0 0

m1

m2 0 0 1 0 0 0 0 0

m3 0 0 0 1 0 0 0 0

m4 0 0 0 0 1 0 0 0

m5

m6 0 0 0 0 0 0 1 0

m7 0 0 0 0 0 0 0 1

+ + + + + + + +

0+ 1+ 0+ 0+ 0+ 0+ 0+ 0+

+ + + + + + + +

0 0 0 0 0 1 0 0

11

Minterm example, conclusion

(variables appear once in each minterm)
A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1
F F

minterm m0 ABC m1 ABC m2 ABC m3 ABC m4 ABC m5 ABC m6 ABC m7 ABC

1 1 1 0 1 1 0 0

0 0 0 1 0 0 1 1

F = ABC + ABC + ABC + ABC + ABC = m0 + m1 + m2 + m4 + m5 = m(0,1,2,4,5) F = ABC + ABC + ABC = m3 + m6 + m7 = m(3,6,7)

Minterms as a circuit
A B C

F = ABC + ABC + ABC + ABC + ABC = m0 + m1 + m2 + m4 + m5 = m(0,1,2,4,5)

Standard form is not minimal form!

Maxterms

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

maxterm M0 A+B+C M1 A+B+C M2 A+B+C M3 A+B+C M4 A+B+C M5 A+B+C M6 A+B+C M7 A+B+C

A sum term in which all variables appear once, either complemented or uncomplemented. Each maxterm evaluates to 0 for exactly one variable assignment, 1 for all others. Denoted by MX where X corresponds to the variable assignment for which MX = 0.

14

Maxterm description of a function

sometimes also called a maxterm expansion or conjunctive normal form (CNF)

This term is FALSE when A=1,B=1,C=0

F = (A+B+C) (A+B+C) (A+B+C)

A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1
F F

1 1 1 0 1 1 0 0

0 0 0 1 0 0 1 1

Force to 0

Maxterm example, seen another way

The logical AND of all maxterms for which F = 0.

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

maxterm M0 A+B+C M1 A+B+C M2 A+B+C M3 A+B+C M4 A+B+C M5 A+B+C M6 A+B+C M7 A+B+C

F 1 1 1 0 1 1 0 0

M0 0 1 1 1 1 1 1 1

M1 1 0 1 1 1 1 1 1

M2 1 1 0 1 1 1 1 1

M3 1 1 1 0 1 1 1 1

M4 1 1 1 1 0 1 1 1

M5 1 1 1 1 1 0 1 1

M6 1 1 1 1 1 1 0 1

M7 1 1 1 1 1 1 1 0

16

Maxterm example, conclusion

The logical AND of all maxterms for which F = 0.

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

maxterm M0 A+B+C M1 A+B+C M2 A+B+C M3 A+B+C M4 A+B+C M5 A+B+C M6 A+B+C M7 A+B+C

F 1 1 1 0 1 1 0 0

F = (A+B+C) (A+B+C) (A+B+C) = (M0) (M4) (M5) (M6) (M7) = M(0,4,5,6,7)

17

One nal example

A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1
F F

0 1 0 1 0 1 1 0

1 0 1 0 1 0 0 1

F
Minterms (SOP) Maxterms (POS)

Summary of Minterms and Maxterms

F
Minterms (SOP) Maxterms (POS) m(F = 1)
M(F = 0)

F
m(F = 0)
M(F = 1)

Relations between standard forms

sum of products

product of sums

DeMorgans

sum of minterms

product of maxterms

all boolean expressions

20

Simplication with Karnaugh Maps

Cost criteria
Literal cost: the number of literals in an expression Gate-input cost: the literal cost + all terms with more than one literal + (optionally) the number of distinct, complemented single literals
Roughly proportional to the number of transistors and wires in an AND/OR/NOT circuits. Does not apply, to more complex gates, for example XOR.

Literal cost
G = ABCD + ABCD G = (A+B)(B+C)(C+D)(D+A)

Gate-input cost 8 + 2 + (4) 8 + 5 + (4)

8 8

22

Karnaugh maps (a.k.a., K-maps)

All functions can be expressed with a map There is one square in the map for each minterm in a functions truth table
X 0 0 1 1 Y 0 1 0 1 F m0 m1 m2 m3

Y X
0 1 0 m0 XY m2 XY 1 m1 XY m3 XY

23

Karnaugh maps express functions

Fill out table with value of a function

X 0 0 1 1

Y 0 1 0 1

F 0 1 1 1

Y X
0

24

Simplication using a k-map

Whenever two squares share an edge and both are 1, those two terms can be combined to form a single term with one less variable Y X
0 0 0 1 1 1 1

Y X
0 1

0 0 1

1 1 1

Y X
0 1

0 0 1

1 1 1

F = Y + XY
Y X
0 1 0 0 1 1 1 1

F = XY + XY + XY

F=X+Y

F = X + XY
25

Simplication using a k-map (2)

Circle contiguous groups of 1s (circle sizes must be a power of 2) There is a correspondence between circles on a k-map and terms in a function expression The bigger the circle, the simpler the term Add circles (and terms) until all 1s on the k-map are circled Y X
0 1 0 0 1 1 1 1

F=X+Y
26

3-variable Karnaugh maps

Use gray ordering on edges with multiple variables Gray encoding: order of values such that only one bit changes at a time Two minterms are considered adjacent if they differ in only one variable (this means maps wrap)

YZ X 00
m0 0 XYZ 01 m1 XYZ m5 XYZ

Y=1
11 m3 XYZ m7 XYZ 10 m2 XYZ m6 XYZ

X=1

m4 1 XYZ

Z=1
27

4-variable Karnaugh maps

Extension of 3-variable maps

YZ WX
00
0 0 m0 0 1 m4 01 m1 m5 11 m3 m7

Y
10 m2 m6

1 1 m12 m13 m15 m14 1 0 m8 m9 m11 m10

28

Implicants
Implicant: a product term, which, viewed in a K-Map is a 2i x 2j size rectangle (possibly wrapping around) where i=0,1,2, j=0,1,2

YZ WX
00
0 0 m0 0 1 m4 01 m1 m5 11 m3 m7

Y
10 m2 m6

1 1 m12 m13 m15 m14 1 0 m8 m9 m11 m10

Note: bigger rectangles = fewer literals

29

4-variable Karnaugh map example

W X 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 Y 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Z 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0

YZ WX
00 01

Y
00
01 11 10

11 10

30

Implicant terminology
implicant: a product term, which, viewed in a K-Map is a 2i x 2j size rectangle (possibly wrapping around) where i=0,1,2, j=0,1,2 prime implicant: An implicant not contained within another implicant. essential prime implicant: a prime implicant that is the only prime implicant to cover some minterm.

31

4-variable Karnaugh maps (3)

List all of the prime implicants for this function Is any of them an essential prime implicant? What is a simplied expression for this function?

YZ WX
00 01

Y
00
0 1 0 0 01 0 1 1 1 11 1 1 1 0 10 0 0 1 0

11 10

Z
32

Using K-maps to build simplied circuits

Step 1: Identify all PIs and essential PIs Step 2: Include all Essential PIs in the circuit (Why?) Step 3: If any 1-valued minterms are uncovered by EPIs, choose PIs that are big and do a good job covering

1 0 1 1

1 1 1 1

1 1 1 0

0 0 1 1

1 0 0 1

1 1 0 0

0 1 1 0

0 0 1 1
33

Design example : 2-bit multiplier

a1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

a0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

b1 b0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

z3

z2

z1

z0

two 2-bit #s multiplied together to give a 4-bit solution e.g., a1a0 = 10, b1b0 = 11, z3z2z1z0 = 0110

34

K-Maps: Complements, PoS, dont care conditions

Finding F
Find prime implicants corresponding to the 0s on a k-map

YZ WX
00 01 11 10

YZ
00
1 1 1 1 01 1 1 1 1 11 0 0 0 0 10 1 1 0 1

WX
00 01 11 10

00
0 0 0 0

01 0 0 0 0

11 1 1 1 1

10 0 0 1 0

F = Y + XZ + WZ

F = YZ + WXY
36

PoS expressions from a k-map

Find F as SoP and then apply DeMorgans

YZ WX
00 01 11 10

00
1 1 1 1

01 1 0 0 1

11 0 0 0 0

10 1 0 0 1

F = YZ + XZ + YX DeMorgans F = (Y+Z)(Z+X)(Y+X)

37

Dont care conditions

There are circumstances in which the value of an output doesnt matter
For example, in that 2-bit multiplier, what if we are told that a and b will be non-0? We dont care what the output looks like for the input cases that should not occur Dont care situations are denoted by an X in a truth table and in Karnaugh maps. Can also be expressed in minterm form: During minimization can be treated as either a 1 or a 0
a1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 b1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 b0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 z3 X X X X X 0 0 0 X 0 0 0 X 0 0 1 z2 X X X X X 0 0 0 X 0 1 1 X 0 1 0 z1 X X X X X 0 1 1 X 1 0 1 X 1 1 0 z0 X X X X X 1 0 1 X 0 0 0 X 1 0 1
38

z2 = m(10,11,14) d2 = m(0,1,2,3,4,8,12)

2-bit multiplier non-0 multiplier

a1 a0 b1 b0 z3 z2 z1 z0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 X X X X X 0 0 0 X 0 0 0 X 0 0 1 X X X X X 0 0 0 X 0 1 1 X 0 1 0 X X X X X 0 1 1 X 1 0 1 X 1 1 0 X X X X X 1 0 1 X 0 0 0 X 1 0 1
39

1s must be covered 0s must not be covered Xs are optionally covered

b0
X X X X X 0 0 0 X 0 1 0 X 0 0 0

b0
X X X X

a0 a1

a1

X 0 0 0 a0 X 0 0 1 X 0 1 1

b1
z3 = z2 =

b1

2-bit multiplier non-0 multiplier (2)

a1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 b1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 b0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 z3 X X X X X 0 0 0 X 0 0 0 X 0 0 1 z2 X X X X X 0 0 0 X 0 1 1 X 0 1 0 z1 X X X X X 0 1 1 X 1 0 1 X 1 1 0 z0 X X X X X 1 0 1 X 0 0 0 X 1 0 1

b0
X X X X X 0 1 1 X 1 0 1 X 1 1 0

b0
X X X X

a1

a0

X 1 1 0

a1

X 1 1 0 X 0 0 0

a0

b1
z1 = z0 =

b1

40

Final thoughts on Dont care conditions

Sometimes dont cares greatly simplify circuitry

D
1 X X X X 1 X X

0 0 1 X 0 0 X 1

C
ABCD + ABCD + ABCD + ABCD vs. A + C

41

Glitches and Hazards

Glitches and hazards

Glitch: an unintended change in circuit output Hazard: the hardware structures that cause a glitch to occur Caused by multiple path delays through a circuit Example: AB + BC Avoidance Synchronous design (coming later) Extra implicants

43