Design of Gate Networks - ch. 5

ucla | CS M51A | 2023-01-19T14:23

---

Table of Contents

• Definitions
• Big Ideas
  • 2 Level Networks@import url(‘https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css’)$$\begin{gathered} \text{AND-OR}⟺\text{NAND-NAND}⟹\text{SOP} \\ textOR-AND⟺\text{NOR-NOR }⟹\text{POS} \end{gathered}$$
    • Characteristics of Minimal 2 Level Networks
    • Equivalence ≠ Equal Cost
  • Karnaugh Maps
    • Characteristics of Karnaugh Maps
    • One-Set, Zero-Set, DC-Set
    • SOP and POS from K-Maps
    • Essential and Prime Implicants (SOP) (3rd video)
    • Essential and Prime Implicates (POS)
• Resources

Definitions

---

Big Ideas

---

2 Level Networks@import url(‘https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css’)$$\begin{gathered} \text{AND-OR}⟺\text{NAND-NAND}⟹\text{SOP} \\ textOR-AND⟺\text{NOR-NOR }⟹\text{POS} \end{gathered}$$

• L1: Inputs and (optional) NOT gates - Literals (un/complemented variables)
• L2: AND gates - Products
• L3: OR gates - Sums
• Multi-output networks: an OR gate for each output

Characteristics of Minimal 2 Level Networks

• Inputs: uncomplemented and/or complemented
• Fan-in - unlimited or finite
• Single-output
• Minimal: minimum # of gates w/ minimum iinputs

Equivalence ≠ Equal Cost

• a network in SOP and POS

• the switching functions

Karnaugh Maps

• a way to graphically represent switching functions

Characteristics of Karnaugh Maps

• 2-dim array of cells
• $n$ variables $\to 2^n$ cells
• cell $i⟷$ assignment $i$
• adjacency condition
  • any set of $2^r$ adjacent rows/columns → assignments differ by $r$ variables
• groups of 1,2,4,8,… adjacent “high” values can be “pooled” to find the minterms
• similarly, form groups of “low” values to find maxterms
• NO WAY TO EXPLAIN THIS → WATCH FIRST LINKED VIDEO

One-Set, Zero-Set, DC-Set

• given aa switching function as a high-low set:

SOP and POS from K-Maps

• SOP: watch first linked video
• POS: watch second linked video

Essential and Prime Implicants (SOP) (3rd video)

• Implicant: product term (maxterm) for which the SF=1

• e.g. implicants
• Prime Implicants (PIs): largest possible group of “high” values in the K-map explained by a maxterm

• e.g. prime implicants
• Essential Prime Implicants (EPIs): the minimal PIs required to describe the K-map i.e. a PI for which ALL its implicants that cannot be grouped in any other possible way

• e.g. EPIs

Essential and Prime Implicates (POS)

• similar to implicants but the OPPOSITE
• Implicate: sum term (minterm) for which SF=0
• Prime Implicate: implicate not covered by another implicate
• Essential prime implicate: similar as EPI but for 0s

Resources

---

https://youtu.be/RO5alU6PpSU

https://youtu.be/iBSMoDLhxB4

https://youtu.be/fmAwCosFSRs

📌

**SUMMARY
**