Chapter 3: Gate-Level Minimization

Source files used: ELEC205 Week 3 slides (slides 40-60), Week 4 slides, Week 5 slides (slides 1-15); textbook Chapter 3 as support. No worked examples are included.

1. Big Picture

Chapter 3 is about making a circuit as cheap as possible.

Chapter 2 asked: how do we turn any truth table into gates? Chapter 3 asks: how do we get the cheapest two-level circuit for it?

\boxed{\text{Find a minimum-cost SOP or POS for }F\text{, then count its cost.}}

New ideas in this chapter:

cost measures: literal cost $L$ , gate input cost $G$ and $GN$ ,
Karnaugh maps (K-maps) for 2, 3, 4 and 5 variables,
prime implicants and essential prime implicants,
the optimization algorithm and the selection rule,
POS simplification from the 0’s,
don’t-care conditions.

Erzin’s exam-style K-map questions use four steps: find all prime implicants, identify the essential ones, find the optimal SOP (or POS), compute $G$ .

2. Core Ideas

2.1 Optimization Needs a Cost

Simplification is informal. Optimization uses a fixed procedure and a cost criterion. The course minimizes the gate input cost of a set of Boolean equations. Two-level SOP and POS circuits give optimum or near-optimum cost.

2.2 Algebraic Simplification

Repeatedly apply $XY+XY'=X$ to pairs of minterms that differ in one variable. It works, but it is easy to miss pairs and there is no clear stopping point. The K-map makes those pairs visible.

2.3 What a K-Map Is

Each square is one minterm.
Adjacent squares differ in exactly one variable.
It is a reorganized truth table (also a “warped” Venn diagram).
Rows and columns follow Gray code order (00, 01, 11, 10), so neighbors differ by one bit.
The map wraps around: left edge touches right edge, top touches bottom (cylinder/torus).

Useful only for small numbers of variables; CAD tools handle larger problems.

2.4 Groups (Rectangles)

A group is a rectangle of 1’s whose size is a power of 2. Each doubling removes one variable. Rectangles may wrap across the edges, and the four corners of a 4-variable map are one valid group.

Inside a group, a variable that stays constant is kept (1 → plain, 0 → complemented). A variable that takes both values disappears.

2.5 Prime and Essential Prime Implicants

Implicant: a product term that covers only 1’s (and don’t-cares).
Prime implicant (PI): a group that cannot be made any larger.
Essential prime implicant (EPI): a PI that covers at least one minterm that no other PI covers.

Every EPI must be in the final answer.

2.6 Don’t-Care Conditions

Sometimes an input combination never occurs (e.g., BCD codes 1010-1111) or its output is never used. Its output is marked “x” (don’t care) and written as $d(\dots)$ .

Treat each x as a 1 if it makes a group bigger, otherwise as a 0. You never need to cover an x.

3. Main Governing Equations and Formulas

3.1 Literal Cost $L$

L=\text{number of literal appearances in the expression}

Examples from the slides: $F=BD+AB'C+AC'D'$ has $L=8$ ; $F=(A+B)(A+D)(B+C+D')(B'+C'+D)$ has $L=10$ .

3.2 Gate Input Cost $G$ and $GN$

For SOP or POS:

G=L+(\text{number of terms, excluding single-literal terms})

GN=G+(\text{number of distinct complemented single literals})

$G$ counts all gate inputs except inverters; $GN$ also counts inverter inputs.

Examples:

F=BD+AB'C+AC'D':\quad L=8,\ G=11,\ GN=14

F=A+BC+B'C':\quad L=5,\ G=7,\ GN=9

In the second one, $A$ is a single-literal term, so it is not counted again; only $BC$ and $B'C'$ add an OR input each. $GN$ adds the inverters for $B'$ and $C'$ .

Use $G$ as the course’s default cost unless a question asks for $L$ or $GN$ .

3.3 K-Map Cell Layout

Three variables (rows $x$ , columns $yz$ in Gray order):

\begin{array}{c|cccc} x\backslash yz & 00 & 01 & 11 & 10\\ \hline 0 & m_0 & m_1 & m_3 & m_2\\ 1 & m_4 & m_5 & m_7 & m_6 \end{array}

Four variables (rows $AB$ , columns $CD$ ):

\begin{array}{c|cccc} AB\backslash CD & 00 & 01 & 11 & 10\\ \hline 00 & 0 & 1 & 3 & 2\\ 01 & 4 & 5 & 7 & 6\\ 11 & 12 & 13 & 15 & 14\\ 10 & 8 & 9 & 11 & 10 \end{array}

Memorize these index positions. Notice columns 3 and 2 (and rows 11 and 10) are swapped relative to counting order.

3.4 Group Size vs Literals

\text{group of }2^k\text{ cells in an }n\text{-variable map}\ \Rightarrow\ \text{product term with }n-k\text{ literals}

3-variable map: 1 cell = 3 literals, 2 cells = 2, 4 cells = 1, 8 cells = constant 1.
4-variable map: 1 cell = 4 literals, 2 = 3, 4 = 2, 8 = 1, 16 = constant 1.

Use to sanity-check every term you read off a map.

3.5 Five-Variable Maps

Split on the first variable with the Shannon expansion:

F(V,W,X,Y,Z)=V'\cdot F(0,W,X,Y,Z)+V\cdot F(1,W,X,Y,Z)

Draw two 4-variable maps, one for $V=0$ and one for $V=1$ . Group inside each map; per the textbook, cells in the same position in the two maps are also adjacent, and a group covering both maps drops $V$ .

3.6 POS Simplification

F'=\text{SOP from grouping the 0's}\qquad\Rightarrow\qquad F=(F')'=\text{POS via DeMorgan}

The slide procedure (for a NOR-only implementation):

Write $F'$ as a minimum sum of products (group the 0’s).
Complement $F'$ .
Write $F$ as a product of sums.

4. Problem-Solving Workflow

4.1 Minimum SOP with a K-Map

Plot a 1 for each minterm (and x for each don’t-care). Leave the rest blank (0).
Find all prime implicants: circle the largest possible power-of-2 rectangles, checking edge wrap and corners.
Mark the essential PIs: look for 1’s covered by only one PI.
Include every essential PI.
Cover the remaining 1’s with a minimum-cost set of the other PIs, following the selection rule (Section 5.2).
Read off one product term per group.
Compute $L$ , $G$ (and $GN$ if asked).

4.2 Minimum POS

Plot the function; mark the 0’s (cells not in the minterm list and not don’t-cares).
Group the 0’s exactly as in Section 4.1 to get a minimum SOP for $F'$ .
Apply DeMorgan: each product term of $F'$ becomes a sum term of $F$ with every literal complemented.
Count the cost. Compare with the SOP if the question asks which is cheaper.

4.3 With Don’t-Cares

Enter the x’s from $d(\dots)$ .
Use x’s only to enlarge groups of 1’s (SOP) or of 0’s (POS).
Never create a group made only of x’s.
Essential PIs are decided by the real 1’s only.

5. Decision Rules / Decision Trees

5.1 Reading a Variable from a Group

Variable is 1 across the whole group? → include the variable

Variable is 0 across the whole group? → include its complement

Variable is both 0 and 1 inside the group? → drop it

5.2 Selection Rule (Non-Essential PIs)

A 1 is covered by only one PI? → that PI is essential, take it

All remaining 1’s are covered by several PIs? → pick PIs that minimize overlap → every selected PI must cover at least one minterm no other selected PI covers → among equal choices, prefer larger groups (fewer literals)

5.3 SOP or POS?

Asked for “optimal SoP”? → group the 1’s

Asked for “optimal PoS” or NOR-only? → group the 0’s for $F'$ , then DeMorgan

Asked which is cheaper? → do both, compare $G$

5.4 Don’t-Care Usage

An x lets a group double in size? → treat it as 1

An x is not needed for any group? → leave it out (treat as 0)

6. Important Tables / Correlations Needed

6.1 Cost Quick Reference

Measure	Counts
$L$	every literal appearance
$G$	$L$ + one input per multi-literal term at the second-level gate
$GN$	$G$ + one inverter input per distinct complemented literal

6.2 Common Group Shapes

Map	Shape	Result
3-var	full row of 4	1 literal ( $x$ or $x'$ )
3-var	2x2 square, incl. wrap columns 00 and 10	1 literal ( $z'$ )
4-var	four corners (0, 2, 8, 10)	$B'D'$
4-var	full row or column	2 literals
4-var	outer columns 00 and 10	$D'$

6.3 Slide Functions Worth Recognizing

Function	Note
$F=\sum m(2,3,5,7,11,13)$	4-bit prime detector; minimum SOP has four 3-literal terms, $G=12+4=16$
$F=\sum m(2,3,5,7)$ , $d=\sum m(10,\dots,15)$	BCD prime detector; don’t-cares shrink it to $A_2'A_1+A_2A_0$
BCD inputs	codes 1010-1111 are always don’t-cares

The prime detector shows why don’t-cares matter: the same primes with the unused codes free drop from $G=16$ to $G=6$ .

7. Key Takeaways

The course cost is $G$ = literals + inputs to the second-level gate (single-literal terms not double-counted); $GN$ adds inverters.
K-map rows and columns use Gray order 00, 01, 11, 10; know where every minterm index sits.
Groups are rectangles of size $2^k$ ; each doubling removes one variable.
Edges wrap; the four corners of a 4-variable map form one group.
Prime implicant = largest possible group; essential = only PI covering some 1.
Algorithm: all PIs, then all EPIs, then the fewest extra PIs (minimum overlap).
POS: group the 0’s to get $F'$ , then DeMorgan.
Don’t-cares are used only if they enlarge a group; never cover an x on its own.
Five variables: two 4-variable maps split on $V$ (Shannon expansion).
Trap: missing a wrap-around or corner group gives a correct but non-minimal answer.