From 7123e4296304b21d206a8aacf3aaaaf4bf9cc24c Mon Sep 17 00:00:00 2001 From: lshprung Date: Mon, 28 Sep 2020 12:08:27 -0700 Subject: Post-class 09/28 --- 3.md | 4 ++ 4.1.png | Bin 0 -> 11888 bytes 4.2.png | Bin 0 -> 6456 bytes 4.3.png | Bin 0 -> 7145 bytes 4.4.png | Bin 0 -> 19253 bytes 4.5.png | Bin 0 -> 37022 bytes 4.6.png | Bin 0 -> 113363 bytes 4.7.png | Bin 0 -> 12960 bytes 4.8.png | Bin 0 -> 19968 bytes 4.md | 148 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 152 insertions(+) create mode 100644 4.1.png create mode 100644 4.2.png create mode 100644 4.3.png create mode 100644 4.4.png create mode 100644 4.5.png create mode 100644 4.6.png create mode 100644 4.7.png create mode 100644 4.8.png create mode 100644 4.md diff --git a/3.md b/3.md index c31376b..fb54e4c 100644 --- a/3.md +++ b/3.md @@ -122,3 +122,7 @@ - The best answer yet, but it can be hard to see these reductions in equation form ![diagram](3.7.png) + +--- + +[Karnaugh Maps, Prime Implicants ->](4.md) diff --git a/4.1.png b/4.1.png new file mode 100644 index 0000000..11b3ed2 Binary files /dev/null and b/4.1.png differ diff --git a/4.2.png b/4.2.png new file mode 100644 index 0000000..b1e8e86 Binary files /dev/null and b/4.2.png differ diff --git a/4.3.png b/4.3.png new file mode 100644 index 0000000..4758315 Binary files /dev/null and b/4.3.png differ diff --git a/4.4.png b/4.4.png new file mode 100644 index 0000000..d373469 Binary files /dev/null and b/4.4.png differ diff --git a/4.5.png b/4.5.png new file mode 100644 index 0000000..0bf5e14 Binary files /dev/null and b/4.5.png differ diff --git a/4.6.png b/4.6.png new file mode 100644 index 0000000..dfa40aa Binary files /dev/null and b/4.6.png differ diff --git a/4.7.png b/4.7.png new file mode 100644 index 0000000..de24bdb Binary files /dev/null and b/4.7.png differ diff --git a/4.8.png b/4.8.png new file mode 100644 index 0000000..aca70c4 Binary files /dev/null and b/4.8.png differ diff --git a/4.md b/4.md new file mode 100644 index 0000000..bebaa4a --- /dev/null +++ b/4.md @@ -0,0 +1,148 @@ +[\<- Boolean Algebra and DeMorgan's Theorem](3.md) + +--- + +# Karnaugh Maps, Prime Implicants + +## K-map structure, implicants, prime implicants + +### Karnaugh Maps (K-Maps for short) + +- Expresses same info as truth table but in different form + +![diagram](4.1.png) + +### Implicants + +- Any product term that evaluates to true +- Two implicants that differ by just one variable (true and false) can be combined + - `X*Y + X*!Y` = `X` + - `X*Y*Z + X*Y*!Z` = `X*Y`] + - A "larger" implicant even though less variables +- An implicant that can't be combined with another is called a "prime" implicant (PI) + - Identifying the PI's allows us to synthesize simpler logic than canonical SOP + +--- + +## Basics of using a K-map, with a 2-input function + +### Minimizing with K Maps + +- Circling adjacent cells represents combining two implicants into one +- A circle that "covers both values of a variable means it's not needed in the term +- It's OK for implicants to overlap + +![diagram](4.2.png) + +### K-map for the OR function + +- We could define OR as F(A,B) = ∑m(1,2,3) +- If we synthesized using minterms we would get F = !A\*B + A\*!B + A\*B + - But we know OR is F=A+B +- Using a K-map identifies overlap + +![diagram](4.3.png) + +--- + +## Structure of a 3-input K-map + +### 3-input functions + +- One side must represent two variables + - Four values +- We want to keep the ability to circle adjacent cells to represent a larger implicant + - Enumerate as 00, 01, 11, 10 +- Opportunity to "cover" four cells +- Edge cells on opposite sides are still "adjacent" + - 00 and 10 differ by one value + +### Example 3-input K-map + +- Can be drawn veritcally or horizontally (the example below shows both options) +- Also, order of variables doesn't matter + - As long as you correctly apply the concepts + +![diagram](4.4.png) + +--- + +## Discerning product terms + +- Every implicant, prime or not, can be specified as a product term + - Individual cells are minterms +- A grouping of two means one of the variables is not needed because both the true and complement case are "covered" + - For the remaining two variables, llok to see if they are 0 or 1 for the two cells + - If 0, then the variable needs to be inverted before including in the product term +- A grouping of four reduces to one variable + +--- + +## A few more 3-input K-map examples + +- First map is "missing" a prime implicant + +![diagram](4.5.png) + +--- + +## 4-variable K-maps + +### Going to four variables + +- The vertical axis now covers two variables + - Same ordering considerations: 00 01 11 10 +- Now we can have prime implicants that cover 8 cells + - Can't do 6 + - Every time you're combining you're accounting for the true and false version of one of the variables + - Necessarily a power of 2 +- Wrap-arounds in both directions + +### 4-Input Examples + +- Another missing prime implicant, in the upper left map + - Can you find it? + +![diagram](4.6.png) + +- The missing prime implicant is the grouping of the 01-10 with the 11-10 + +--- + +## Essential prime implicants + +- Once **ALL** prime implicants (PI's) are identified, there is typically some amount of overlap +- Including all PI's in the solution equation might be unnecessary + - We'd like to find the simplest solution +- Some of the PI's will \*have\* to be in the solution equation -> they are essential + - Visually, they are the PI's that contain cells (minterms) not covered by any other PI + +### Visualizing essential PI's + +- K-map below has all PI's circled +- Only `!X3*!X4` is essential +- Minimal solution only needs to add greens + - Complete coverage with just 2 more terms + +![diagram](4.7.png) + +### K-map with no essentials + +- To fully illustrate the point, note this K-map has no essentials + - Solution equation will have four terms + +![diagram](4.8.png) + +--- + +## Summary of the K-map process + +### Synthesizing with K-maps + +- Identify \*all\* PI's + - Start with largest, to avoid non-primes + - Don't forget to look for wrap-arounds +- Identify which PI's are "essential" + - An essential PI contains cells that are not part of any other PI +- Write the SOP equation, starting with the essential PI's + - Add the minimum number of non-essential PI's needed to "cover" all cases where the function should evaluate to true -- cgit