Several techniques have been developed to simplify a complex Boolean expression into its simplest form. K-Map or Karnaugh Map is one of such minimization or simplification techniques.
The K-Map or Karnaugh Map is a graph or chart which composed of an arrangement of adjacent cells. Where, each cell of the K-Map represents a particular combination of variables in either sum or product form. The K-map can be used to simplify Boolean functions involving any number of variables. But, the simplification of a Boolean function using K-map becomes tedious for problems involving five or more variables. Therefore, in actual practice, the K-map is limited to six variables.
The number of cells in a K-map depends upon the number of variables in the given Boolean function. A K-map will have 2n cells or squares, where n is the number of variables in the Boolean expression. Therefore, for a two variable function, the K-map will have 22 = 4 cells, for a three variable Boolean function, the K-map will have 23 = 8 cells, and for four variable Boolean function, the K-map will have 24 = 16 cells, and so on.
Here, we will discuss four variable K-Map and will use it to simplify Boolean functions in 4 variables.
Four Variable K-Map
A four variable K-map is used to simplify a complex Boolean expression in 4 variables. As we know, a four variable Boolean expression can have 24 = 16 possible combinations of variables.
For example, in SOP (Sum of Products) Form,
$$\mathrm{f(A,B,C,D) \: = \: \bar{A}\bar{B}\bar{C}\bar{D} \: + \: \bar{A}\bar{B}\bar{C}D \: + \: \bar{A}\bar{B}C\bar{D} \: + \: \dots \: + \: ABCD}$$
The minterm representation of this expression is as follows,
$$\mathrm{f(A,B,C,D) \: = \: m_{0} \: + \: m_{1} \: + \: m_{2} \: + \: \dotso \: + \: m_{15}}$$
In POS (Product of Sums) Form,
$$\mathrm{f(A,B,C,D) \: = \: (A \: + \: B \: + \: C \: + \: D)(A \: + \: B \: + \: C \: + \: \overline{D} )(A \: + \: B \: + \: \overline{C} \: + \: D) \: \dotso \: (\overline{A} \: + \: \overline{B} \: + \: \overline{C} \: + \: \overline{D})}$$
The maxterm representation of this expression is as,
$$\mathrm{f(A,B,C,D) \: = \: M_{0}\cdot M_{1}\cdot M_{2} \: \dotso \: M_{15}}$$
A 4 variable K-map has 16 cells, where each cell represents either a minterm or a maxterm of the function. The SOP (Sum of products) form and POS (Product of Sums) form of a four variable Boolean expression is shown in Figure 1.
Here, the binary number designations of the columns and rows are in the Gray code. This is known as adjacent ordering. In these K-maps, the binary numbers along the left side of the map indicate the conditions of variables A and B along any row, and the binary numbers along the top of the K-map indicate the conditions of the variables C and D along any column. The decimal numbers in the bottom right corners of the cells indicate the minterm or maxterm designation.
Now, let us consider an example to illustrate the utilization of the 4 variable K-map for simplification of a Boolean function.
Example 1
Simplify the following Boolean expression using the 4-variable K-map.
$$\mathrm{f \lgroup A,B,C,D \rgroup \: = \: \sum m \lgroup 2,3,6,7,8,10,13,15 \rgroup}$$
Solution
The SOP K-map representation of the given Boolean function is shown in Figure 2.
Explanation
The simplification of the function is done as per the following steps −
There are no isolated 1s in the K-Map.
The minterm m2 can form a 4-square with m3, m6, and m7. Make it and read it as −
$$\mathrm{\bar{A}C}()$$
The minterm m8 can form a 2-square with m10. Make it and read it as −
$$\mathrm{AB\bar{D}}()$$
The minterm m13 can form a 2-square with m15. Make it and read it as −
$$\mathrm{(A\bar{B}D)}$$
Write all the product in SOP form.
So the simplified SOP expression is,
$$\mathrm{f(A,B,C,D) \: = \: \bar{A}C \: + \: A\bar{B}D \: + \: AB\bar{D}}$$
Example 2
Minimize the following Boolean expression using the 4-variable K-map.
$$\mathrm{f(A,B,C,D) \: = \: \prod \: M(4,6,11,14,15)}$$
Solution
The POS K-map representation of the given Boolean function is shown in Figure 3.
Explanation
In minimization of the given function is done as per the following step −
There are no isolated zeros in the K-map.
The maxterm M4 can form a 2-squate with M6. Make it and read it as −
$$\mathrm{(A \: + \: \bar{B} \: + \: D)}$$
The maxterm M11 can form a 2-square with M15. Make it and read it as −
$$\mathrm{(\bar{A} \: + \: \bar{C} \: + \: \bar{D})}$$
Now, only maxterm M14 is left. M14 can form 2-square with M6 or M15. If we make it with M15, then read it as −
$$\mathrm{(\bar{A} \: + \: \bar{B} \: + \: \bar{C})}$$
Finally, write all the sum terms in POS form.
So, the reduced POS expression of the given Boolean function is,
$$\mathrm{f(A,B,C,D) \: = \: (A \: + \: \bar{B} \: + \: D)(\bar{A} \: + \: \bar{C} \: + \: \bar{D})(\bar{A} \: + \: \bar{B} \: + \: \bar{C})}$$
Numerical Problems on K-Map
Q1. Reduce the following Boolean function using 4-variable K-map
$$\mathrm{f \lgroup A,B,C,D \rgroup \: = \: \sum m \lgroup 0,1,2,5,8,10,11,13,14,15 \rgroup }$$
Q2. Minimize the following Boolean expression using 4-variable K-Map.
$$\mathrm{f \lgroup A,B,C,D \rgroup \: = \: \prod \: M \lgroup 0,2,8,10,11,13,15 \rgroup}$$
Conclusion
This is all about the 4 variable K-map and its application to minimize a Boolean expression into its minimal form. From the above discussion, we can conclude that the 4-variable K-map is a graphical representation of a Boolean expression involving 4 variables and is represented in standard SOP or POS form. This is used to convert a standard SOP or POS form, or minterm form or maxterm form of a 4-variable Boolean expression into its minimal SOP or POS form.
Print Page
Advertisements