lecture_EE1D1_lec4_logic_minimization_2025-09-09

📌 Overview

Canonical expressions are a way of writing truth tables with a numeric system using $\sum$ (for summation of and statement) or $\prod$ (for and statements with or inside)

---

🎯Learning Objectives

• To use canonical expression (i.e., sum-of products and products-of-sum) to represent logic functions. ✅ 2025-09-11
• Minimize logic expressions using Karnaugh maps ✅ 2025-09-28
• Take advantage of don’t care inputs to minimize logic expressions ✅ 2025-09-28
• Convert two-level and multi-level circuits to NAND or NOR equivalents ✅ 2025-10-02
• Map expressions to And-Or-Invert circuits and Or-And-Invert ✅ 2025-10-02
• Analyze the timing behaviour of circuits ✅ 2025-10-02

---

💡Key Concepts & Definitions

➗ Formulas

---

✍️ Notes

Canonical expressions

• Expression in unique standard
• truth table → unique canonical expression

Don’t Cares in K-maps

NAND and NOR Implementation

📝 Summary

NAND and NOR gates are known as “universal gates” because any Boolean function can be implemented using only NAND gates or only NOR gates. Due to their simpler implementation in silicon, they are often preferred over AND and OR gates in circuit design.

---

💡 Explanation

The ability to create any logic function from a single type of gate simplifies the manufacturing process. The conversion from AND/OR logic to NAND/NOR logic is based on De Morgan’s laws.

De Morgan’s Laws

• (A • B)' = A' + B'
• (A + B)' = A' • B'

Conversion Rules

• AND/OR to NAND/NAND: A two-level AND-OR circuit can be directly converted to a two-level NAND-NAND circuit. This is done by replacing every AND and OR gate with a NAND gate.
• OR/AND to NOR/NOR: A two-level OR-AND circuit can be directly converted to a two-level NOR-NOR circuit by replacing every OR and AND gate with a NOR gate.

Example: AND/OR to NAND/NAND

An expression in Sum-of-Products form, like F = AB + CD, is implemented with AND gates followed by an OR gate.

This can be converted to a NAND-NAND implementation:

---

📚 Related Resources

📝 Summary

Karnaugh maps (K-maps) are a graphical method used to simplify Boolean algebra expressions. They provide a systematic way to find the simplest sum-of-products or product-of-sums expression for a given function.

---

💡 Explanation

K-maps are a visual representation of a truth table, but the cells are arranged in a special order (Gray code) so that only a single input variable changes between adjacent cells. This property allows for easy identification of groups of 1s (or 0s) that can be combined to eliminate variables, thus simplifying the logic expression.

The goal is to cover all the 1s in the map using the largest possible rectangular groups of 1, 2, 4, 8, etc., cells. Each group corresponds to a simplified product term.

2-Variable K-map

For a 2-variable function F(A, B), the K-map is a 2x2 grid.

• Example: Simplify F = A'B' + A'B + AB

From the K-map, we can group the 1s:

1. The red group covers m0 and m1, where B changes but A is constant at 0. This simplifies to A'.
2. The blue group covers m1 and m3, where A changes but B is constant at 1. This simplifies to B.

The simplified expression is F = A' + B.

3-Variable K-map

For a 3-variable function F(A, B, C), the K-map is a 2x4 grid. The columns are ordered using Gray code (00, 01, 11, 10) to ensure only one variable changes between adjacent cells.

• Example: Simplify F(A,B,C) = Σm(3,4,5,6,7)

1. The red group is a group of four 1s where B and C change, but A is constant at 1. This simplifies to A.
2. The blue group is a group of two 1s where A changes, but B and C are constant at 1. This simplifies to BC.

The simplified expression is F = A + BC.

4-Variable K-map

• Example: F(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15)

By using the don’t cares as 1s, we can form two large groups:

1. Red group: D
2. Blue group: A'C'

The simplified expression is F = A'C' + D. Without don’t cares, the expression would be F = A'D + B'C'D.

A	B	C	Minterms	F
0	0	0	$A^{\prime }{B}^{\prime }{C}^{\prime }=m_0$	0
0	0	1	$A^{\prime }{B}^{\prime }C=m_1$	0
0	1	0	$A^{\prime }B{C}^{\prime }=m_2$	0
0	1	1	$A^{\prime }BC=m_3$	1
1	0	0	$A{B}^{\prime }{C}^{\prime }=m_4$	1
1	0	1	$A{B}^{\prime }C=m_5$	1
1	1	0	$AB{C}^{\prime }=m_6$	1
1	1	1	$ABC=m_7$	1

$$\begin{array}{rl}{F}^{\prime }& =A^{\prime }B’C’+A’B^{\prime }C+A’BC’\\ & =m_1+m_2+m_3\\ & =\sum m(0,1,2)\\ & =(A+B^{\prime }+C^{\prime })(A^{\prime }+B+C)(A^{\prime }+B+C^{\prime })(A^{\prime }+B^{\prime }+C)(A^{\prime }+B^{\prime }+C^{\prime })\\ & =M_3{M}_4{M}_5{M}_6{M}_7\\ & =\prod M(3,4,5,6,7)\\ & \\ F& =A^{\prime }BC+A{B}^{\prime }C’+A{B}^{\prime }C+AB{C}^{\prime }+ABC\\ & =m_3+m_4+m_5+m_6+m_7\\ & =\sum (3,4,5,6,7)\\ & =(A+B+C)\cdot (A+B+C^{\prime })\cdot (A+B^{\prime }+C)\\ & =M_0{M}_1{M}_2\\ & =\prod M(0,1,2)\end{array}$$

Two level simplification

• Example: F(A,B,C) = Σm(3,4,5,6,7) simplifies to F = A + BC

Multi-Level Simplification

Multi-Level Simplification

📝 Summary

Multi-level logic simplification, often achieved through factoring, is a technique used to transform a two-level logic expression (Sum-of-Products or Product-of-Sums) into a multi-level circuit. While this may increase the delay through the circuit, it can often significantly reduce the number of gates and interconnections required.

---

💡 Explanation

While two-level simplification using K-maps provides a systematic way to find a minimal expression, it is not always the most efficient implementation in terms of gate count. Factoring can be used to identify common terms in an expression and implement them once.

Example

Consider the following two-level expression: X = ADF + AEF + BDF + BEF + CDF + CEF + G

This expression would require six 3-input AND gates and one 7-input OR gate.

By factoring out common terms, we can simplify this expression: X = (A + B + C)(D + E)F + G

This factored form can be implemented with:

• One 3-input OR gate
• Two 2-input OR gates
• One 3-input AND gate

This results in a circuit with fewer gates and connections.

---

• Example: X = ADF + AEF + BDF + BEF + CDF + CEF + G can be factored to X = (A + B + C)(D + E)F + G

---

🔗 Resources

• Presentation:

---

❓ Post lecture

---

📖 Homework