1. Gate-Level Minimization and Cost Criteria

Gate-level minimization is the design task of finding an optimal gate-level implementation of the Boolean functions of a circuit. “Optimal” needs a cost criterion:

CriterionSymbolCounts
Literal costliterals in the expression
Gate input costinputs of all gates, excluding inverters
Gate input cost with NOTsinputs of all gates, including inverters

Definition – Literal Cost

A literal is a variable or its complement. = number of literal occurrences in the expression.

Definition – Gate Input Cost

For an SoP or PoS expression:

(each multi-literal term is a first-level gate whose output is one more input to the second-level gate).

Definition – Gate Input Cost with Inverters

(one inverter per variable that appears complemented — each inverter has one input).

Example – Comparing Three Expressions

Expression
8 ()
11
10

The first expression is the cheapest on every criterion.

Example – Same , Different

Both expressions below describe the same function and have :

66

ABCA’B’C’F = ABC + A’B’C’

AC’B’CA’BF = (A+C’)(B’+C)(A’+B)

The SoP has better and → choose it.

⚠️ alone can tie; use (then ) to break ties.


2. Why K-Maps?

Algebraic simplification works, but it is hard to know when to stop and whether the result is optimal. The Karnaugh map (K-map) is a graphical method that finds an optimal (or near-optimal) two-level SoP or PoS for functions of fewer than 6 variables.

  • The result is always an SoP or a PoS (AND–OR or OR–AND circuit).
  • The minimal expression is not always unique — any one that meets the criteria is acceptable.

3. K-Map Definition

Definition – K-Map

A K-map is the truth table drawn as a 2-D array: each truth-table row (minterm/maxterm) is one square. variables → rows → squares.

Definition – Logical Adjacency

Two terms are logically adjacent if they contain the same variables and differ in the form of exactly one variable. They merge:

(Maxterms work the same way: and are adjacent.)

Key Property

K-maps are built so that logically adjacent terms are geometrically adjacent — neighbouring squares differ in one variable. Rows and columns are ordered in Gray code (00, 01, 11, 10), and adjacency wraps around: the last row/column is adjacent to the first.

⚠️ The column order is 00, 01, 11, 10 — not 00, 01, 10, 11. Using binary order breaks adjacency and gives wrong groups.


4. K-Map Layouts

2 Variables (4 squares)

01
0
1

3 and 4 Variables – Square Numbers

The number in each square = row bits followed by column bits = the minterm index = the truth-table row.

xyz000111100101324576ABCD00011110000111100132457612131514891110

  • 3 variables: each square has 3 neighbours. Example: 101 (5) is adjacent to 100 (4), 111 (7), 001 (1); 110 (6) is adjacent to 111 (7), 100 (4), 010 (2).
  • 4 variables: each square has 4 neighbours (including wrap-around left↔right and top↔bottom).

Labelling

Label the map carefully — either with the Gray codes on the edges, or with bars showing where each variable is 1 (e.g. = the two right columns 11 and 10, = the two middle columns 01 and 11).

Filling

By convention, put a 1 in each square whose minterm belongs to and leave the others empty (or 0).


5. Grouping Squares

Groups are rectangles of squares (1, 2, 4, 8, 16) containing only 1s. The bigger the group, the fewer the literals.

Map1 square2 squares4 squares8 squaresall
2 variables2 literals1 literal—— (4)
3 variables3 literals2 literals1 literal
4 variables4 literals3 literals2 literals1 literal (16)

Rule – Reading a Group

A variable that takes both values inside the rectangle disappears. The variables that stay constant remain — normal if constant 1, complemented if constant 0.

Example – 2 Variables:

xy010100112131F = x + y

Row gives ; column gives → .

Algebraic check: ✓ (T9).

Example – 3 Variables:

xyz0001111001013121457161F = Σm(2,3,6,7) = y

The 4-square group covers and but only → .

Check: ✓

Example – 3 Variables: Two Functions

xyz0001111001013121415176F = x’y + xy’abc0001111001013124157161G = bc + ac’

  • — the pair wraps around (columns 00 and 10 are adjacent).

Example – 3-Variable Groups of 2 and 4

xyz0001111001013241517161xz’ and xzxyz0001111001011321415761z’ (wrap-around)

  • (row , ) → ; → .
  • (the two outer columns, both with ) → .

Example – 4-Variable Groups

ABCD000111100001111001132145761213151481911101B’D’ (4 corners)ABCD0001111000011110011312415171611211315141891110BD’ and A’DABCD00011110000111100132457612113115141819111101AB’D’, AC’D, ABD’

  • 4 corners → (rows 00/10 ⇒ ; columns 00/10 ⇒ ).
  • → ; → .
  • Pairs: → ; → ; → .
  • Other slide examples: one square → , , ; 4 squares → (row 11); 8 squares → (two right columns), (two outer columns), (rows 00 and 10).

⚠️ The four corners of a 4-variable map form one valid group — the map is a torus. Beginners often miss this and the edge-wrap groups.

⚠️ Group sizes must be powers of 2 and shapes must be rectangles: 3 or 6 squares, or an L-shape, are not valid groups.


Exercises: none assigned in Part A; the algorithm and its exercises are in 5B – Gate-Level Minimization (Algorithm and Don’t Cares).