Karnaugh map: Difference between revisions
No edit summary |
|||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
The '''Karnaugh map (Kmap)''' is a matrix that represent output values of a boolean function. It is primarily used to | The '''Karnaugh map (Kmap)''' is a matrix that represent output values of a boolean function. It is primarily used to ''minimize the number of gates'' in a circuit. For this conversation, ''all gates are considered equal'' in value. | ||
= Matrix = | = Matrix = | ||
Kmap minimize equations graphically. Each cell represent | Kmap minimize equations graphically. Each cell represent a [[minterm]] and its output. There cannot be more than one bit change from one column to the next. | ||
If there are more variables, multiple is placed for an axis. Note the restriction regarding bit change means that conventional order of inputs is invalid. | If there are more variables, multiple is placed for an axis. Note the restriction regarding bit change means that conventional order of inputs is invalid. | ||
= Simplify = | = Simplify = | ||
Circle 1's in adjacent squares. Every grouping represents a term. A grouping has to be a power of 2 and be as large as possible. | Circle 1's in adjacent squares. Every grouping represents a term. A grouping has to be a power of 2 and be as large as possible. A grouping can wrap around edges. | ||
Don't-cares can be included or excluded depending on whether it minimizes the equation. | Don't-cares can be included or excluded depending on whether it minimizes the equation. | ||
= How it works = | Groupings can also include only 0's, using product of sums instead of sums of products. | ||
Ǐ= How it works = | |||
Adjacent columns/rows have one bit difference. If two 1's are adjacent, it means that that particular one bit difference does not matter for a particular term. A simplification is then found. | Adjacent columns/rows have one bit difference. If two 1's are adjacent, it means that that particular one bit difference does not matter for a particular term. A simplification is then found. | ||
[[Category:Computer Architecture]] | [[Category:Computer Architecture]][[Category:ECS154A Midterm]] | ||
Latest revision as of 21:48, 9 May 2024
The Karnaugh map (Kmap) is a matrix that represent output values of a boolean function. It is primarily used to minimize the number of gates in a circuit. For this conversation, all gates are considered equal in value.
Matrix
Kmap minimize equations graphically. Each cell represent a minterm and its output. There cannot be more than one bit change from one column to the next.
If there are more variables, multiple is placed for an axis. Note the restriction regarding bit change means that conventional order of inputs is invalid.
Simplify
Circle 1's in adjacent squares. Every grouping represents a term. A grouping has to be a power of 2 and be as large as possible. A grouping can wrap around edges.
Don't-cares can be included or excluded depending on whether it minimizes the equation.
Groupings can also include only 0's, using product of sums instead of sums of products.
Ǐ= How it works = Adjacent columns/rows have one bit difference. If two 1's are adjacent, it means that that particular one bit difference does not matter for a particular term. A simplification is then found.
