From Truth Tables to Karnaugh Maps
For two-variable functions
- Values are plotted along two axes
- Adjacent cells differ by only one variable value
For a truth table :
| x | y | f(x, y) |
|---|---|---|
| 0 | 0 | f(0,0) |
| 0 | 1 | f(0,1) |
| 1 | 0 | f(1, 0) |
| 1 | 1 | f(1, 1) |
| We get the associated Karnaugh map : |
| x\y | 0 | 1 |
|---|---|---|
| 0 | f(0,0) | f(0,1) |
| 1 | f(1,0) | f(1,1) |
| We can have this map as a single axis representation: |
| 00 | 01 | 11 | 10 |
|---|---|---|---|
| f(0,0) | f(0,1) | f(1,1) | f(1,0) |
We can then turn this into a three-variable by adding another row to the Karnaugh map !
| 00 | 01 | 11 | 10 | |
|---|---|---|---|---|
| 0 | f(0,0,0) | f(0,1,0) | f(1,1,0) | f(1,0,0) |
| 1 | f(0,0,1) | f(0,1,1) | f(1,1,1) | f(1,0,1) |
We have the cells at the opposite "ends" of the map as adjacent
We will mostly label the colums by their variable name when the variable is equal to ⇒ instead of writing
For 4-variable maps, we have a size If we add a 5th variable, we need to add a whole new map → Less practical
Combining minterms
Karnaugh maps allow us to easily and visually spot simplifications, whereas we had to use boolean algebra to simplify minterms with truth tables.
We simplify our map by grouping cells together
Implicants and Prime Implicants
- Implicant
- A product term that represents all the inputs for which the function results to → ex. minterms
- Prime implicant
- An implicant that cannot be combined more → in K-maps: largest group of ones
- Grouping Rule
- A group can only contain a power-of-two cells
- Cover
- A set of implicants that cover all input combinations
- Essential Implicant
- A prime implicant, that covers at least one minterm, not covered by any prime implicants
- Because there is no covering implicant ⇒ it is essential to the function and has to be included
To have an optimized cover, it is better to keep bigger implicants. Multiple valid covers can exist
Incompletely Defined Functions
If a value/configuration cannot be reached, then we dont-care aka the resulting output can be anything ⇒ Can be for our convenience !