ELEN500

Homework 6 Chapter 10 SOLUTIONS

1. Maximally factor f = abde + abfg + cde + cfg + aef + gh using weak division.

SOLUTION:

	abde	abfg	cde	cfg	aef
abfg	ab
cde	de	-
cfg	-	fg	c
aef	ae	af	e	f
gh	-	g	-	g	-

Kernel	Co-Kernel
fg+de	ab
c+ab	de
f+bd	ae
c+ab	fg
e+bg	af
fg+de	c
af+cd	e
ae+cg	f
h+abf+cf	g

Using the heuristic of choosing the 0-level kernel with the most literals as a divisor, we could choose fg+de, af+cd, or ae+cg. (Note that h+abf+cf is a level-1 kernel since the literal f appears in two cubes)

Using weak division and choosing fg+de as the divisor we obtain:

f	V^fg	V^de
abde	-	ab
abfg	ab	-
cde	-	c
cfg	c	-
aef	-	-
gh	-	-

Q is the intersection of the cubes in V^fg and V^de. Q = ab + c

R is the sum of the unused cubes in f. R = aef + gh

The factored form of f = DQ+R = (fg+de)(ab+c) + (aef + gh)

2. Compute the cost function (number of literals) for f in both the unfactored SOP form and the factored form.

Unfactored, f has 19 literals.

Factored, f has 12 literals.