:PROPERTIES: :ID: c3126ca5-44cb-4b50-b8b1-1ce56cc50a6d :mtime: 20231009031512 :ctime: 20231009031451 :END: #+title: Karnaugh Map #+filetags: :public:project: * Definition A Karnaugh map, also called a k-map is a technique for simplifying digital circuits. A Karnaugh map works by visually representing a truth table, so you can simplify the boolean expression by recognizing large blocks or patterns in the Karnaugh map. * Steps to make a Karnaugh Map from a Truth Table 1) Plot the 1s of the truth table on the Karnaugh Map 2) Find groups with size equal to a power of two 3) larger groups are best because they require fewer variables 4) groups are allowed to wrap around edges and corners * Rules for Forming Groups - Find groups with size equal to a power of two - larger groups are best because they require fewer variables - groups are allowed to wrap around edges and corners * On Wikipedia Look at https://en.wikipedia.org/wiki/Karnaugh_map * Gray Code Make sure that only one variable changes at a time. This means that the transitions must follow a Gray code. Perhaps it would be a smart idea to memorize Gray code so you can easily reproduce it. * Group by 1 vs Group by 0 You should note that the result of a Karnaugh map is a [[id:c167b95c-027b-420c-ae74-977c422c16f7][disjunctive normal form]] if you group by 1s, but it is a [[id:44556352-e5a4-4054-afda-820829edb9d7][conjunctive normal form]] if you group by 0s and then apply DeMorgan's Law. * With Don't Care Conditions If you are simplifying with [[id:cd789888-4964-4249-82e5-359c9424c5ed][Don't Care Conditions]], put an $X$ in the table to represent how this entry could be a 0 or a 1. Choose the most convenient number when you get there.