Minimization of Circuits

Introduction

Circuit minimization is the process of simplifying Boolean functions to:

• Reduce number of gates
• Reduce number of gate inputs
• Lower cost
• Reduce power consumption
• Increase speed
• Improve reliability

Goal: Find the simplest equivalent Boolean expression.

Why Minimize?

Cost Reduction

Example: Original function with 5 gates vs. minimized with 3 gates

• Fewer chips needed
• Smaller circuit board
• Lower manufacturing cost

Performance

Fewer levels = Less delay

• 4-level circuit: 20 ns delay
• 2-level minimized: 10 ns delay
• 2x faster!

Power Consumption

Fewer gates = Less power

• Important for battery devices
• Reduced cooling requirements
• Environmental benefits

Reliability

Simpler circuits = More reliable

• Fewer components to fail
• Easier to test and debug

Methods of Minimization

1. Algebraic manipulation (manual)
2. Karnaugh Maps (K-maps) - visual, up to 4-6 variables
3. Quine-McCluskey method - algorithmic, any number of variables
4. Computer programs - for very large circuits

Method 1: Algebraic Minimization

Using Boolean Identities

Apply identities to simplify expressions.

Example 1: Simple Simplification

Given: f = AB + AB̄

Steps:

1. Factor out A: f = A(B + B̄)
2. Complement law: B + B̄ = 1
3. Identity law: A · 1 = A

Result: f = A

Savings: 2 AND gates + 1 OR gate → direct connection!

Example 2: Using Absorption

Given: f = A + AB

Apply absorption law: A + AB = A

Result: f = A

Example 3: More Complex

Given: f = ABC + ĀBC + ABC̄

Steps:

1. Factor BC from first two terms: f = BC(A + Ā) + ABC̄
2. Simplify: A + Ā = 1, so BC · 1 = BC
3. f = BC + ABC̄
4. Factor B: f = B(C + AC̄)
5. Apply: C + AC̄ = C + A (absorption variant)
6. f = B(C + A) = BC + AB

Result: f = AB + BC (minimized)

Limitations

• Requires skill and experience
• No systematic approach
• Easy to miss simplifications
• Difficult for complex functions

Method 2: Karnaugh Maps (K-Maps)

What is a K-Map?

A Karnaugh map is a visual tool for minimizing Boolean functions.

Features:

• 2D grid representing all input combinations
• Adjacent cells differ by only ONE variable
• Groups of 1s show simplification opportunities

Gray Code Ordering

K-maps use Gray code - adjacent cells differ by 1 bit only.

2-variable order: 00, 01, 11, 10 3-variable order: 000, 001, 011, 010, 110, 111, 101, 100

Why? Ensures adjacent cells can be combined!

2-Variable K-Map

Structure:

        y
      0   1
   0 [m0][m1]
x
   1 [m2][m3]

Example: f(x, y) = Σ(1, 3)

        y
      0   1
   0 [0] [1]  ← m1
x
   1 [0] [1]  ← m3

Group the 1s:

• Vertical group: y = 1 (covers m1, m3)

Minimized: f = y

3-Variable K-Map

Structure:

          yz
        00  01  11  10
   0   [m0][m1][m3][m2]
x
   1   [m4][m5][m7][m6]

Note the order: 00, 01, 11, 10 (Gray code!)

Example 1: 3-Variable Minimization

Given: f(x, y, z) = Σ(1, 3, 5, 7)

Truth table:

K-Map:

          yz
        00  01  11  10
   0   [0] [1] [1] [0]
x
   1   [0] [1] [1] [0]

Grouping:

• Vertical group of 4: covers m1, m3, m5, m7
• Variables that change: x, y
• Variable that stays constant: z = 1

Minimized: f = z

Verification:

• Original: 4 minterms = 12 literals
• Minimized: 1 literal!

Example 2: Multiple Groups

Given: f(x, y, z) = Σ(0, 2, 5, 7)

K-Map:

          yz
        00  01  11  10
   0   [1] [0] [0] [1]
x
   1   [0] [1] [1] [0]

Grouping:

• Horizontal group (top): m0, m2 → x̄z̄
• Horizontal group (bottom): m5, m7 → xz

Minimized: f = x̄z̄ + xz

Or using XOR: f = x ⊕ z

4-Variable K-Map

Structure:

            zw
          00  01  11  10
    00   [m0][m1][m3][m2]
xy  01   [m4][m5][m7][m6]
    11   [m12][m13][m15][m14]
    10   [m8][m9][m11][m10]

Gray code for both axes!

Example 3: 4-Variable Function

Given: f(w, x, y, z) = Σ(0, 1, 2, 5, 8, 9, 10)

K-Map:

            yz
          00  01  11  10
    00   [1] [1] [0] [1]   ← group of 2 (m0,m1), single m2
wx  01   [0] [1] [0] [0]   ← m5
    11   [0] [0] [0] [0]
    10   [1] [1] [0] [1]   ← group of 2 (m8,m9), single m10

Grouping:

1. Group m0, m1, m8, m9 (rectangle 2x2): wx̄ȳ simplifies to xz̄

   • w changes (0→1), x constant (0), y constant (0), z changes (0→1)
   • Result: x̄z̄

2. Group m0, m2 (horizontal pair): w̄x̄ȳ

3. Group m8, m10 (horizontal pair): wx̄z̄

4. Single m5: w̄xyz̄

Wait! Better grouping:

1. Corner group: m0, m2, m8, m10 (corners form a group!)

   • Variables constant: y = 0, z = 0
   • Result: ȳz̄

2. Pair: m0, m1

   • Result: w̄x̄ȳ

3. Pair: m8, m9

   • Result: wx̄ȳ

4. Single: m5

   • Result: w̄xȳz̄

Optimal grouping:

1. m0, m1, m2 (no valid group)
2. Better: m0, m2, m8, m10 → ȳz̄
3. m1, m9 (column) → x̄ȳz
4. m5 alone → w̄xȳz̄

Actually: Best: f = ȳz̄ + x̄ȳz + w̄xȳz̄

K-Map Grouping Rules

Rule 1: Group Sizes

Must be powers of 2: 1, 2, 4, 8, 16, …

Valid groups:

• 1 cell (no simplification)
• 2 cells (eliminate 1 variable)
• 4 cells (eliminate 2 variables)
• 8 cells (eliminate 3 variables)
• etc.

Invalid: 3, 5, 6, 7 cells

Rule 2: Group Shapes

Must be rectangular (including squares)

Valid:

• 1×1 (single cell)
• 1×2 or 2×1 (pair)
• 2×2 (quad)
• 1×4 or 4×1 (quad)
• 2×4 or 4×2 (oct)

Invalid: L-shapes, diagonals, scattered cells

Rule 3: Wrap-Around

Edges wrap around!

• Top edge connects to bottom edge
• Left edge connects to right edge
• Corners connect together

Example: Cells at positions (0,0) and (0,3) are adjacent!

Rule 4: Maximize Group Size

Larger groups → simpler expression

Group of 4 is better than two groups of 2 (if possible).

Rule 5: Minimize Number of Groups

Fewer groups → fewer terms

But don’t sacrifice group size.

Rule 6: Overlapping is OK

A cell can belong to multiple groups if it helps minimize.

Rule 7: Cover All 1s

Every 1 must be in at least one group.

Prime Implicants

Definitions

Implicant: A product term that covers one or more minterms of the function.

Prime Implicant (PI): An implicant that cannot be combined with another to eliminate a variable.

Essential Prime Implicant (EPI): A prime implicant that covers at least one minterm not covered by any other PI.

Finding Minimal Expression

Steps:

1. Find all prime implicants (largest possible groups)
2. Identify essential prime implicants (must be included)
3. Select minimum additional PIs to cover remaining 1s

Example

Given: f = Σ(0, 1, 2, 5, 6, 7)

K-Map:

          yz
        00  01  11  10
   0   [1] [1] [0] [1]
x
   1   [0] [1] [1] [1]

Prime Implicants:

1. m0, m1, m2 is NOT valid (not power of 2)
2. m0, m1 → x̄z̄
3. m0, m2 → x̄ȳ
4. m5, m7 → xz
5. m6, m7 → xy
6. m1, m5 → ȳz

Essential Prime Implicants:

• m0 only covered by m0,m1 and m0,m2
• m2 only covered by m0,m2 → EPI
• m6 only covered by m6,m7 → EPI

Solution: Need m0,m2 and m6,m7, then need to cover m1,m5,m7

Minimal: f = x̄ȳ + xy + ȳz

Don’t Care Conditions

What are Don’t Cares?

Symbol: X or d or -

Meaning: Output can be 0 or 1 (we don’t care which)

Uses:

• Undefined input combinations
• Impossible states
• Unused outputs

Using Don’t Cares in K-Maps

Strategy: Treat X as 1 if it helps grouping, as 0 otherwise.

Example: Don’t Cares

Given: f = Σ(1, 3, 7) + d(0, 5)

Meaning:

• f = 1 for minterms 1, 3, 7
• f = don’t care for minterms 0, 5
• f = 0 for others

K-Map:

          yz
        00  01  11  10
   0   [X] [1] [1] [0]
x
   1   [0] [X] [1] [0]

Without don’t cares: f = x̄z + xy

With don’t cares (use X as 1):

• Include m0 with m1: group of 2 → x̄ȳ
• Include m5 with m7: group of 2 → xz

Actually better:

• Group m0, m1, m3 is invalid
• Group m1, m3, m5, m7: all have z=1 → f = z

Optimized: f = z

Huge simplification! From 2 terms to just 1 literal!

Example Problems

Problem 1: Basic K-Map

Minimize: f(x, y, z) = Σ(0, 2, 4, 5, 6)

Solution:

K-Map:

          yz
        00  01  11  10
   0   [1] [0] [0] [1]
x
   1   [1] [1] [0] [1]

Groups:

1. m4, m5, m6 is not valid (3 cells)
2. m4, m5 → xz̄
3. m4, m6 → xȳ
4. m0, m2, m4, m6 (corner wrap) → ȳ

Minimal: f = ȳ (one group covers m0,m2,m4,m6) + need m5

Actually: Groups:

• m0, m2, m4, m6 → ȳ (4 cells, eliminates 2 vars)
• m4, m5 → xz̄

But m4 already covered, so: f = ȳ + xz̄ (covers all)

Wait, let me recheck:

• m0 in ȳ: yes
• m2 in ȳ: yes
• m4 in ȳ: yes
• m5 in ȳ: no (y=0 in row 1, z=1 for m5)
• m6 in ȳ: yes

So need another term for m5: f = ȳ + xȳz

Or: f = ȳ + xz̄ doesn’t cover m5

Correct:

• Group 1: m0, m2, m4, m6 → ȳ
• Group 2: m4, m5 → xz̄

Answer: f = ȳ + xz̄

Problem 2: With Don’t Cares

Minimize: f(A, B, C, D) = Σ(1, 3, 7, 11, 15) + d(0, 2, 5)

Strategy:

1. Mark 1s for minterms
2. Mark X for don’t cares
3. Group using X where helpful

Result: More compact expression than without don’t cares!

Problem 3: POS Minimization

K-maps can also minimize POS by:

1. Group the 0s instead of 1s
2. Each group gives a maxterm (sum)
3. AND all maxterms

Quine-McCluskey Method

Overview

Algorithmic method for minimization:

• Works for any number of variables
• Systematic procedure
• Computer-friendly
• Guaranteed to find minimal solution

Steps

1. List all minterms in binary
2. Group by number of 1s
3. Compare adjacent groups, combine if differ by 1 bit
4. Mark combined terms, repeat
5. Find prime implicants
6. Select minimal set covering all minterms

Example (Brief)

f = Σ(0, 1, 2, 5, 6, 7)

Step 1: Binary minterms

• m0: 000
• m1: 001
• m2: 010
• m5: 101
• m6: 110
• m7: 111

Step 2: Group by number of 1s

• 0 ones: 000
• 1 one: 001, 010
• 2 ones: 101, 110
• 3 ones: 111

Step 3: Combine (differ by 1 bit, mark with dash)

• 000, 001 → 00- (x̄ȳ)
• 000, 010 → 0-0 (x̄z̄)
• 001, 101 → -01 (ȳz)
• 101, 111 → 1-1 (xz)
• 110, 111 → 11- (xy)

Step 4: Try combining again, find prime implicants

Step 5: Select minimal cover

Result: f = x̄z̄ + xy + ȳz

Comparison of Methods

Key Points for Exams

1. K-map uses Gray code ordering (adjacent cells differ by 1 bit)
2. Group sizes: must be powers of 2 (1, 2, 4, 8, 16)
3. Shapes: rectangular only
4. Wrap-around: edges and corners connect
5. Larger groups → simpler terms
6. Fewer groups → fewer terms
7. Don’t cares (X): use to make larger groups
8. Prime implicant: cannot be combined further
9. Essential prime implicant: must be included
10. Each 1 must be covered at least once

Practice Problems

1. Minimize f(x,y,z) = Σ(0,1,2,3,7) using K-map

2. Minimize f(x,y,z) = Σ(1,3,4,6) using K-map

3. Minimize f(A,B,C,D) = Σ(0,1,3,7,8,9,11,15) using 4-variable K-map

4. Given f = Σ(2,3,6,7) + d(0,1), find minimal SOP

5. Draw K-map for f = xy + xz + yz and verify it’s minimal

6. What is the maximum group size in a 3-variable K-map?

7. How many prime implicants for f = Σ(0,1,2,4)?

8. Minimize f = x̄ȳz̄ + x̄yz + xȳz̄ + xyz algebraically

9. For f = Σ(1,5,9,13) in 4 variables, describe the optimal group

10. Why can corners of K-map be grouped together?