Karnaugh Maps - Engineering - ثاني ثانوي
1. Engineering Fundamentals
2. Electrical Engineering
3. Digital Circuits
4. Circuit Simulation with Tinkercad Circuits
5. Simulating a microcontroller- based system
Lesson 2 Karnaugh Maps Link to digital lesson www.ien.edu.sa Karnaugh Maps Karnaugh maps were introduced by Maurice Karnaugh in 1953 at Bell Labs and are used to simplify the design of digital circuits. Karnaugh maps are used to clearly depict the output results of a complex digital circuit. They are especially helpful when we have a circuit with more than 2 inputs. If we were to use a truth table for this task, it would use a lot of space and it would be difficult to read. Karnaugh maps depict the same information in a more compact format. The following is a depiction of a truth table and a Karnaugh map. For a function with two inputs, we can see how to place the corresponding results of function Y in positions 1, 2, 3 and 4 of the Karnaugh map. Input A Input B Output Y 0 0 0 1 1 0 1 1 A A B 1 2 B 3 4 Karnaugh maps are used to group Boolean expressions instead of going through the Boolean algebra calculations for multiple variable inputs. • Let's see an example of the function Y = A · B + A B+ A · B to see how we create a Karnaugh map. Example A A A.B A 0 1 B In a Karnaugh map, the variables are replaced by 1 and their complement by 0. BO 0 1 B 1 1 1 A.B وزارة التعليم Ministry of Education 80 2024-1446 A.B When placing the variables A and B in the Karnaugh map, it is your choice which will be horizontal and which will be vertical.
Karnaugh Maps
In a Karnaugh map, the variables are replaced by 1 and their complement by 0.
Then with the help of the Karnaugh map, we can simplify the function Y = A B+ A B+ A B using fewer terms. Example A 0 1 B 0 0 1 A 1 1 1 Y = A + B B The aces you merge must always be an even number. Here we are deleting terms that contain a term and its complement in a loop. In the vertical loop, we notice that the term B changes and is therefore eliminated, and the result becomes only the term A. Terms of the Function The terms of the function are referred to as minterms. That is, a term A · B is called minterm, while a term A + B is called maxterm. . 1 The procedure for simplification of the above Boolean function has been completed. We could summarize the process in the following steps: Find the minimum terms of the function. Function: A · B + A B+ A.B B A 01 0 1 A.B 2 Find the aces (1) and place them in the Karnaugh map. 1 1 1 A.B 3 1 Create loops around adjacent aces (1) in an even number of squares (2,4 or 8). B A.B 01 001 4 A.B We simplify the minimum terms that result by deleting terms that contain a term and its complement in a loop. 1 1 1 Deleted terms: A B, A B • • A A 5. B 0 1 The remaining terms, one from each loop, are linked by the operation OR (+) in the final form of the function. B 1 1 وزارة التعليم Ministry of Education 2024-1446 Final form of the function: Y=A+B 81
The procedure for simplification of the above Boolean function has been completed. We could summarize the process in the following steps:
Let's see how the Y function can be implemented with far fewer logic gates after its simplification. . Y = A B+ A B+ A B . AND1 A B NOT₁ A AND₂ A.B NOT, 2 B AND 3 A. B D A A. B A 01 A B B 001 1 1│1 وزارة التعليم Ministry of Education 82 2024-1446 OR1 A B+ A B OR INFORMATION It is not usual to use the Karnaugh map for 2 inputs because the simplification can be achieved very easily with Boolean algebra, but for 3 or more inputs it can be extremely helpful. OR 2 Y = A B+ A B+ A B . Y = A + B
Let's see how the Y function can be implemented with far fewer logic gates after its simplification.
It is not necessary to use a Karnaugh map for two-input logic gate functions, as they are usually simplified using Boolean algebra. However, in cases when we have functions that have logic gates with more than two inputs, the Karnaugh map helps to simplify the circuit. Let's look at an example of a Karnaugh map with 3 inputs (A, B, and C). Example AB In the horizontal row, we place in pairs the 0 and 1 for the variables A and B so that in successive squares the value of only one variable changes. AB AB 00 01 AB AB 11 10 CO Choose 2 inputs in the row and 1 input in the column C 1 Let's see where the aces (1) will be placed in the Karnaugh map for the following function: The term A C lacks the variable B. So according to Boolean algebra, the term A C A B C+A.B.C. B+B=1 • The term B C lacks the variable A. So according to Boolean algebra, the term B C A B C+A B.C. . = . . وزارة التعليم Ministry of Education 2024-1446 The new minimum terms may lead you to cells that already have an ace. A + A = 1 AB C 00 01 11 10 0 1 1 1 1 A B C A B C AB C 00 01 11 10 00011 1 0 1 1 0 A.B.C • A B C • AB C 00 01 11 10 0 1 YB C+A.C 1 1 B.C A.C 83
It is not necessary to use a Karnaugh map for two-input logic gate functions,
Now let's look at an example with 4 variables (A, B, C and D). We will simplify the function using a Karnaugh map: Example Y=A·B·C·D+A · B · C · D + A · B · C · D + A · B · C · D After simplifying the function, using the Karnaugh map, we get the following function: AB CD 00 01 11 10 00 000 1 01 0001 11 0001 Y = A.B 10 00 0 1 Aces that appear at the edges of the map are considered adjacent to those at the opposite edge. Let's see some examples : Example Example Y=A B C D+A· B · C ·D+A · B · C · D+A · B · C · D+A· B.C.D Y=A B C D+A.B.C.D AB CD 00 01 11 10 AB CD 00 00 0 。。 0 1 1 00 A B C 01 1 01 00 0 0 0 1 11 000 0 1000 1│1 After simplifying the function using the Karnaugh map, we obtain the following result: Y A D A B C وزارة التعليم Ministry of Education 84 2024-1446 01 11 10 。。。。 0 0 1 000 00 11 0 A.D 10 0 0 After simplifying the function using the Karnaugh map, we obtain the following result: Y = B.C.D
Now let's look at an example with 4 variables (A, B, C and D). We will simplify the function using a Karnaugh map:
Aces that appear at the edges of the map are considered adjacent to those at the opposite edge.
Exercises 1 Why do you use the Karnaugh map in digital circuits? 2 Use the following numbered positions of the output Y to complete the Karnaugh map below. Input A Input B Input C Output Y 0 0 0 1 AB 0 0 1 2 C 00 01 11 10 0 1 0 3 0 1 0 1 1 4 1 0 0 5 1 1 0 1 6 1 1 0 7 1 1 1 8 3 Using the given function, circle the errors in the Karnaugh map. وزارة التعليم Ministry of Education 2024-1446 Y=A.B.C+A·B·C+A·B·C AB 00 01 11 10 01000 1 0 1 0 1 85
Why do you use the Karnaugh map in digital circuits?
Use the following numbered positions of the output Y to complete the Karnaugh map below.
Using the given function, circle the errors in the Karnaugh map.
4 5 Use the Karnaugh map to find the minimum function from three inputs. AB C 01 00 11 10 0 0 0011 Y = 1 101 1 Use the Karnaugh map to find the minimum function from four inputs. AB CD 00 11 00 01 000 10 001 10 01 1001 11 1001 10 0 0 10 Y = 6 When we have each of the binary numbers (000), (100), (110) and (111) as inputs (A, B and C) in a circuit, then (1) appears at the output. Place the aces on the Karnaugh map and find the simplified function. AB C 00 01 11 10 وزارة التعليم Ministry of Education 86 2024-1446 0 Y =
Use the Karnaugh map to find the minimum function from three inputs.
Use the Karnaugh map to find the minimum function from four inputs.
Place the aces on the Karnaugh map and find the simplified function.
After you have found the simplified function, draw the corresponding digital circuit. وزارة التعليم Ministry of Education 2024-1446 87
After you have found the simplified function, draw the corresponding digital circuit.
