DLD Presentation – K-Map (2 & 3 Variable).pptx

A Digital Logic Design Presentation focusing on the Karnaugh Map for simplifying Boolean Algebra expressions

1. I n the Name of Allah Who I s the Most Compassionate and the Most Merciful

2. • DLD Presentation • Lecturer: P. Ali Mosavi • Group 1: Ahmad Sha Zadran, Azizullah Yosufi, Rooheen Sayeedi & Najeebullah Karimi • Semester 2, October 2023

3. K-Map (2 & 3 Variable)

4. What is the K-Map? A K-Map, or Karnaugh map in full, is a visual method or a graphical tool that can be used to simplify Boolean algebra expressions without having to resort to complex theorems or equation manipulations. A K-Map can be thought of as a special truth table that makes it easier to map out parameter values and arrive at a simplified Boolean expression. There are two ways to simplify Boolean expressions: using Boolean algebra laws or the K-Map; both roads lead to Rome, but the second simpler & quicker at most times. It is named after Maurice Karnaugh , who introduced it in 1953 as a refinement of Edward W. Veitch’s 1952 Veitch chart; therefore, K-Maps are also sometimes referred to as Karnaugh- Veitch maps ( KV-Maps ).

5. What is the K-Map? (cont.) The K-Map reduces the need for extensive calculations by taking advantage of humans’ pattern-recognition capability. They are used to simplify real-world logic requirements so that they can be implemented using a minimum number of logic gates. A sum-of-products expression ( SOP ) can always be implemented using AND gates feeding into an OR gate, and a product-of-sums expression ( POS ) leads to OR gates feeding an AND gate. K-Maps can also be used to simplify logical expressions in software design . Boolean conditions, as used for example in conditional statements, can get very complicated, which end up making the code difficult to read and to maintain. Once minimized, canonical SOP & POS expressions can be implemented directly using AND & OR logic operators.

6. How to use the K-Map? A K-Map is best suited for functions having two to four variables . Although they can be used for those with five or six, too, but the process is more difficult as talking seven or more variables, it’s extremely difficult — if not impossible. To draw a K-Map, we should follow the following steps : S#1) Select a table according to the number of variables in the expression, which we can identify using 2 n where n stands for the total number of variables in the expression. For example, a 2-variable expression (2 2 ) would use 4 cells, hence a 2×2 table, while a 3-variable expression (2 3 ) would use 8 cells & a 4×2 table and so on. S#2) Label the rows and columns of the table with the variables and their complements in Gray code order. Gray code is a binary code that changes only one bit at a time. E.g., for a 3-variable K-Map, the rows would be labeled as 00, 01, 11, 10 and the columns would be labeled as 0, 1.

7. How to use the K-Map? (cont.) S#3) Fill in the cells of the K-Map with the output values of the expression for each combination of input values. We can use a truth table to find these values.

8. How to use the K-Map? (cont.) After our K-Map is ready, we should follow the hereunder rules to obtain the minimal expression: R#1) Identify groups of adjacent cells having the same value. We can either group 0’s with 0’s (POS) or 1’s with 1’s (SOP). R#2) The groups must contain a power of two number of cells such as 1, 2, 4, 8 & so on. In other words, a group can only include 2 n number of cells. The larger the group, the simpler the expression, so each group should be as large as possible, minimizing the end total of groups.

9. How to use the K-Map? (cont.) R#3) When grouping, the total number of cells isn’t the only thing we should consider as the grouping direction is also of much importance. Groups can be either horizontal or vertical as opposite & corner grouping is also allowed, which means that we can’t make groups in diagonal or any other shape. Groups may also overlap each other.

10. How to use the K-Map? (cont.) Opposite Grouping Corner Grouping

11. How to use the K-Map? (cont.) R#4) After all the groups are ready, one final thing to do is to analyze each group and find the common & consistent factor(s) among the variables that correspond to that very group. Taking SOP as our default method, subsequent to validly grouping the 1’s & spotting the factors, we write the final, simplified expression by multiplying the factors of the same group using AND (to make product terms) and adding the product terms created from different groups together with OR (to get the ultimate sum of products — multiple AND gates feeding to an OR). Including the common factors whose values are 1 with no changes, we shouldn’t forget to take a complement of those having 0 while writing the product terms.

12. Two-variable K-Map Needless to say, this K-Map is drawn for a Boolean expression composed of only two variables. As explained before, with 2 n equaling 4, we need 4 cells & a 2×2 table.

13. Two-variable K-Map (cont.) Exercise: Extract the Boolean function from the following truth table & proceed to minimize it using the K-Map. A B F 1 1 1 1 1 1 The final answer is F(A,B) = ~A (not A).

14. Three-variable K-Map Obviously, this K-Map is drawn for a Boolean expression with three variables. This time around, with 2 n equaling 8, we need 8 cells & a 4×2 table.

15. Three-variable K-Map (cont.) Exercise: Minimize the following Boolean expressions through the K-Map. F(A,B,C) = Σ (1,3,5,7) The final answer is F(A,B,C) = C. F(A,B,C) = Σ (2,4,5,6,7) The final answer is F(A,B,C) = A+BC`.

16. 1000001 1101110 1111001 100000 1010001 1110101 1100101 1110011 1110100 1101001 1101111 1101110 1110011 111111 = Any Questions?

17. • P. Ali Mosavi’s slides, DLD Chapter 03, Fall 1402 • Bing Chat by Microsoft • Template Design by SmileTemplates.com © Sources

18. Thanks a lot; I’m very grateful!