KARNAUGH MAP (K-MAP) In Digital Systems

KARNAUGH MAP (K-MAP) In Digital systems

 

One way to simplify Boolean algebra equations is the K-Map. In this article we will learn how to build a K-Map .

K-Map  Variable

Two Variables of  K-Map

Suppose we have a truth table as in table 1, the following shows how to construct a K-Map for that table. Starting by painting Figure 1, the vertical column(s) consists of B’ and B, while the horizontal row is filled with A’ and A. Then, find the output of 1 in table 1. The first output 1 corresponds to the inputs A=1 and B=0. The fundamental product of these states is AB’. The same thing is obtained when A=1 and B= 1. The fundamental product is AB. Next, the number 1 is written in the box that corresponds to the fundamental product, and the remainder is filled in with the number 0, then a K-Map is obtained as shown in Figure 2.

Next we see another example of  2 Variables K-Map. From truth table 2 it can be read that the fundamental product contained here in is A’B and AB’. If we write down the number 1 for the product and the number 0 in the remaining places, then we get a K-Map as shown in Figure 3.

Table 1

Table 2

Figure 1 – 2 variable of K-MAP

Figure 2 – K- MAP ( Example 1)

Figure 3 – K- MAP ( Example 2)

 

Three Variables of  K-Map

Suppose we have a truth table like table 3 So start by drawing picture 4 Horizontal rows are marked A’B’, A’B, AB and AB’, columns are marked C’D’, C’D, CD, and CD’ as shown in Figure 4 Next, look for output 1 in table 3 and obtain the fundamental product for it, namely: A’BC’, ABC’ and ABC. Then write the number 1 on the K-Map in the appropriate places with fundamental products, and the remainder is filled with 0, then a K-Map is obtained as shown in Figure 5.

Table 3

Figure 4 –    3 variable of K-MAP

Figure 5 –    3 variable of K-MAP Case with Table 3

Four-variable of  K-Map

An example of a four-variable K-Map will be described below. Look at Table 4. The first step, create an empty K-Map as shown in Figure 6. The horizon rows are marked A’B’, A’B, AB, and AB’, while the columns are marked C’D’, C’D, CD, and CD’. In Table 4, the output

value of 1 gives the fundamental product: A’B’C’D, A’BCD’, A’BCD, and ABCD’. After filling in the number 1 according to the product of 4 fundamentals on the K-Map and 0 on the rest, we get K=Map as shown in Figure 7.

Table 4

Figure 6 –     4 Variable of K – MAP


Figure 7 –     4 Variable of K – MAP Case with Table 4

 

Pair, Dual, Quad and Octet

The main function of the K-Map is to be used in simplifying logic circuits. But before we understand how this is done, it is necessary to first study the notions of pairs, quads (groups of four) and octets (groups of eight).

Dual

In K-Map the number 1 can be combined to form a pair, two (dual), four (quad), and eight (octet). Joints are allowed both in the vertical direction, and in the horizontal direction. As shown in Figure 6.8, the first 1 represents the multiplication of ABCD, the second represents the multiplication of ABCD. Furthermore, the pair is marked with a box to form a dual pair. Similarly, box A’B’C’D’ joins box A’B’CD’ to form a dual pair.

As shown in Figure 9, all the numbers in the first row of squares form a square pair, as well as the 1s in the squares ABC’D, ABCD, AB’C’D, and AB’CD to form the second square.

Figure 10 shows an octet pair, which is made up of all the 1s in the first and fourth rows. The second octet is formed from all thein column 3 and column 4.

Figure 8

Figure 9

Figure 10

Look at Figure 8, a dual pair, there are variables that change (from D to D’), while other variables do not change shape (A, B, and C remain the same as before). If this is the case, we can delete the changed variable so that the product is ABC. Algebraically this can be proven. The equation for the number of products corresponding to the dual pair in Figure 8 is:

Y = ABCD + ABCD’

Factorization produces:

Y = ABC ( D+D’ )

According to the laws of boolean algebra, D+D’=1, then the above equation can be reduced to:

Y = ABC

To facilitate identification, usually adjacent pairs of numbers 1 are marked with a square or circle, as shown in Figure 8. In this way, we can easily recognize the existence of variables and their complements that can be omitted.

Another pair is a pair of squares A’B’C’D’ with A’B’CD’ forming a vertical dual pair. In this pair the variable C changes to its complement (C to C’) while the other variables A’, B’, and D’ do not change. Therefore, C and C’ can be removed, and the dual pair in Figure 8 represents the product A’B’D’.

If there is more than one pair in a K-Map, we can perform the OR operation on the simplified product to obtain the corresponding Boolean equation. For example, in Figure 8, there are 2 pairs whose product is ABC and A’B’D’. The corresponding Boolean equation for this K-Map is:

Y = ABC + A’B’D’

Quad

Quad is a group consisting of four numbers 1 arranged side by side from end to end or groups that form a rectangular arrangement as shown in Figure 9. The existence of a square pair means that the two variables and their complements are removed from the corresponding Boolean equation.

This can be explained as follows. Think of the four 1s from Figure 9 as a combination of two dual pairs. The first pair has A’B’C’, and the second pair has A’B’C. The Boolean equation for these two pairs is:

Y = A’B’C’ + A’B’C

Factorization of the equation results in

Y = A’B’ ( C’+C )

So we get a simpler form

Y = A’B’

Explain that the Quad in the first row of Figure 6.9 expresses a product that has been simplified by removing the two variables and their complement.

Octets

An octet is a group of eight adjacent 1s as shown in figure 10. An octet always means the removal of three variables and their complements from the corresponding Boolean equation. For clarity, we follow the following description. View the octet in Figure 10 as two squares. The equation for these two quads is

Y = A’B’ + AB’

Factorization gives

Y = B’ ( A + A’ )

But this is none other than

Y =B’

So, the octet in Figure 10 means that three variables and complements -its complement will be removed from the corresponding product. Similar proofs apply to other octet forms. Next, we’re not going to mess around with the complexities of algebra. The only step needed is to determine the number 1 of the octet and look for three variables that change shape. These variables will be removed from the equation.

Simplification of K-Map

It has been explained how a number 1, a Dual, a quad, and an octet can eliminate one, two, and three variables, respectively. For this reason, in order to simplify the Boolean equation, we must identify starting by circling the octet, then the square, and finally the pair of numbers 1. Through this step, the maximum simplification can be achieved.

Example:

Suppose you have translated an output table into the K-Map shown in Figure 11. First, look for the octet in the K-Map. It turns out that there are no octets in the K-Map. Then, find a quad. You will find two quads. And finally, look for pairs of numbers 1, and we will find a pair.

Figure 5.11 

 

pair represents the simplified multiplication A’B’D, the bottom quadrant represents the product AC’, and the square on the right represents the multiplication of CD’. Executing the OR operation between these simplified products, will produce a Boolean equation as follows.

Y = A’B’D + AC ‘+ CD’

Group overlapping (overlapping)

When we circled the groups in K-Map, we are allowed to wear a particular item 1 more than once. Figure 12 explains this statement.

Figure 6.12

The simplified equations are each dual with the product of BC’D and the octet with the product of A. These two products are then added together and produce the following output.

Y=A+BCD

SolvingProblems

Example 1.

Simplify with the K-Map the cases given in the correct table below:

 

The first step is to translate the table into a K-Map. There are 4 numbers 1 (A’B’C’, A’B’C, A’BC’ and ABC’). If these four conditions are included in the K-Map, the results are as shown in Figure 13.

Figure 13

The final result is obtained:

Dual 1 with product A’B’ and dual 2 with product BC’, so that the output equation of Table 9 is:

Y = A’B’ + BC’

Return to Table 9, if solved by Boolean Algebra obtained: Y = (A’B’C’ + A’B’C + A’BC’ +ABC’)

Simplified to:

Y = A’B'(C’+C) + BC'(A’+A)

Y = A’B’+BC’

Example 2

Simplify with the K-Map the cases given in the correct table below:

In this case, there are also 4 numbers 1 (A’B’C’D, A’BC’D, ABC’D and ABCD). If these four conditions are included in the K-Map, the results are as shown in Figure 14.

Figure 14

The final result is obtained:

Dual 1 with the product of A’C’D and dual 2 with the product of ABD, so that the output equation of Table 9 is:

Y = A’C’D +ABD

Back to Table 10, if solved by Boolean Algebra we get: Y = A’B’C’D + A’BC’D + ABC’D + ABCD

Simplified to:

Y = A’C’D(B’+ B ) + ABD(C’+C)

Y = A’C’D +ABD

Conclusion

  1. A complex logic problem can be simplified easily through K-Map
  2. K -Map is a tool for simplification of logical algebra