diff options
author | lshprung <lshprung@yahoo.com> | 2020-09-28 12:08:27 -0700 |
---|---|---|
committer | lshprung <lshprung@yahoo.com> | 2020-09-28 12:08:27 -0700 |
commit | 7123e4296304b21d206a8aacf3aaaaf4bf9cc24c (patch) | |
tree | 57a1717ba27648594a2219a3e7f6c6557497db12 | |
parent | d95532688cef1b12922d3f6e51eb27dc1d00f634 (diff) |
Post-class 09/28
-rw-r--r-- | 3.md | 4 | ||||
-rw-r--r-- | 4.1.png | bin | 0 -> 11888 bytes | |||
-rw-r--r-- | 4.2.png | bin | 0 -> 6456 bytes | |||
-rw-r--r-- | 4.3.png | bin | 0 -> 7145 bytes | |||
-rw-r--r-- | 4.4.png | bin | 0 -> 19253 bytes | |||
-rw-r--r-- | 4.5.png | bin | 0 -> 37022 bytes | |||
-rw-r--r-- | 4.6.png | bin | 0 -> 113363 bytes | |||
-rw-r--r-- | 4.7.png | bin | 0 -> 12960 bytes | |||
-rw-r--r-- | 4.8.png | bin | 0 -> 19968 bytes | |||
-rw-r--r-- | 4.md | 148 |
10 files changed, 152 insertions, 0 deletions
@@ -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) Binary files differBinary files differBinary files differBinary files differBinary files differBinary files differBinary files differBinary files differ@@ -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 |