Karnaugh Mapping

• Karnaugh mapping is an easy-to-use graphical method of simplifying Boolean expressions.
• Consider the following truth table and its corresponding Karnaugh map (K-Map)
  
• The K-Map consists of one square for each possible minterm in a function.
• Therefore, a two-variable map has $2^2=4$ squares, a three-variable map has $2^3=8$ squares, and a four-variable map has $2^4=16$ squares.

Basic Structure of K-Maps

Minimum SOP Expression using K-Map

1. Start with a truth table or a Boolean expression in SOP form.
2. Convert into a Karnaugh map.
3. Form groups around adjacent 1’s according to K-map rules
4. Simplify each group by removing literals appear in both complemented and uncomplemented forms
5. OR the remaining terms back together

Rules for Grouping in K-Maps

1. The number of 1’s in each group must be a power of two (i.e. 1, 2, 4, 8, 16, etc. squares).
2. Only side-adjacent 1’s can be grouped together into squares or rectangles (i.e. no diagonals).
3. Enlarge each group as much as possible while reducing the total number of groups.
4. Partial overlapping of groups is permitted, but no group should be entirely inside another group(s).
5. All 1’s have to be included in at least one group.
   Don’t ignore any 1’s, even if by itself.
6. K-map can be considered as wrapped in a cylinder (i.e. top and bottom, left and right edges are connected).

Example of Five-Variable K-Map

#NotOnTheExam

• It is also possible to a five-variable (or more) problem.In this case, the Karnaugh map would consist of multiple layers of four-variable K-maps stacked on top of each other.
• The same rules for grouping adjacent squares and determining minimum SOP expression are applied, with additional consideration that of multi-layer groups.

Minimum POS Expression using K-Map

1. Construct a Karnaugh map of the complement of the function
2. Find the minimum SOP expression (using K-map) of the complement of the function
3. Apply the involution law and De Morgan’s Theorem to the complement of the function to obtain the POS form of the original function.

อันนี้ทำคล้าย ๆ เดิม ก็ใส่ 1 ในช่องที่ปกติใส่ 0 อะ แล้วก็ใช้ K-Map grouping ให้ถูกต้อง แล้วออกมาจะได้เป็น $\overline{X}$ ก็อย่าลืมว่าต้องเปลี่ยนเป็น $X$ ธรรมดาก่อน ใช้ Involution & De Morgan’s ตามนั้น
**ออกสอบแน่ ๆ อย่าลืมล่ะ

K-Maps with Don’t Care Conditions

• In some systems, the value of the output is specified for only some of the input conditions. For the remaining input combinations, it does not matter what the output is (i.e. we don’t care!).
• In a truth table, don’t care conditions are indicated by an $X$.
  
• When we design such a system, we can make the output either 0 or 1 for each minterm corresponding to a don’t care condition.
• This allows us to choose the implementation that is least costly (i.e. simplest).

Make Sense มาก ๆ ถ้ามี Output นึงเป็นผลลัพท์ที่เราไม่ได้สนใจว่าจะเป็นไร จะเป็น 0 จะเป็น 1 เราก็ไม่ได้สนใจ แล้วจะไปให้ค่าทำไม ก็ใส่ $X$ (Don’t care) ไปเลย! เวลาเรา Build circuit ก็จะได้เสียเงินน้อยลง ไม่ต้องไปคำนึงถึงทุก Output!

• Don’t care จะอยู่ที่เดิมนะ ไม่ว่าจะทำ SOP/POS Form