Karnaugh Maps

The Karnaugh map provides a simple and straight-forward method of minimising boolean expressions. With the Karnaugh map Boolean expressions having up to four and even six variables can be simplified.

what is a Karnaugh map?

A Karnaugh map provides a pictorial method of grouping together expressions with common factors and therefore eliminating unwanted variables. The Karnaugh map can also be described as a special arrangement of a truth table.

The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem.

The values inside the squares are copied from the output column of the truth table, therefore there is one square in the map for every row in the truth table. Around the edge of the Karnaugh map are the values of the two input variable. A is along the top and B is down the left hand side. The diagram below explains this:

Karnaugh Maps - Rules of Simplification

---

The Karnaugh map uses the following rules for the simplification of expressions by grouping together adjacent cells containing ones

• Groups may not include any cell containing a zero
  
• Groups may be horizontal or vertical, but not diagonal.
  
• Groups must contain 1, 2, 4, 8, or in general 2ⁿ cells.
  That is if n = 1, a group will contain two 1's since 2¹ = 2.
  If n = 2, a group will contain four 1's since 2² = 4.
  
• Each group should be as large as possible.
  
• Each cell containing a one must be in at least one group.
  
• Groups may overlap.
  
• Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell.
  
• There should be as few groups as possible, as long as this does not contradict any of the previous rules.
  

2 variable K– map

2 variable K– map plot below : - Each element (0-3) from above table is plotted in k-map below. Var x or A is horizontal row and y or B is vertical column.  There intersection denotes output function element.

A solved example of 2 variable k-map below.

F(x,y)=sum(0,2,3)

Tutorials @fullchipdesign.com

Verilog Tutorial.

LTE Tutorial.

Memory Tutorial.

Minimization solution to above function.

=xy'+x'y'+xy+xy' 

= y’(x + x’) + xy + xy’ 

= y’ + x (y+y’) 

= y’ + x

so the answer is = y’ + x

Problem 1:Consider the following map. The function plotted is: Z = f(A,B) = A + AB

The minimised answer therefore is Z = A.


Problem 2:
Consider the expression Z = f(A,B) =  + A  + B plotted on the Karnaugh map:

The simplified answer is Z =  + 

3 variable Karnaugh map

The K-map for 3 variables is plotted next, you will notice the columns for 11 and 10 are inter-changed. This is done to allow only one variable to change across adjacent cells. This placement in columns allows the minimization of logic. Now any adjacent 1, 2, 4 or 8 cells can be grouped to find a minimized logic.

Example: Minimize following 3 var function.

Above is a common format of representing the K-map problems. The numbers 0,1,6,7 are the location of cells in the 3-var k-map table is discussed next 

Three variable K– map with 1 and 0 values assigned to cells is shown in next table. 

Tutorials @fullchipdesign.com

Verilog Tutorial.

LTE Tutorial.

Memory Tutorial.

F = x’y’(z+z’) + xy(z+z’)

 = x’y’ + xy (Answer.)

Problem  1:    Z = f(A,B,C) =   + B + AB + AC

The minimised result obtained is B + AC+ 
 

Problem  2: Z = f(A,B,C) = B + B + BC + A
The minimized result obtained is B + A

More practice examples on 3 var kmap completely solved at following links.

1. F(x,y,z) = (0,1,6,7) - Answer.
2. F(x,y,z) = (0,1,4,5,6,7) - Answer.
3. F(x,y,z) = (3,4,6,7) - Answer.
4. F(x,y,z) = (0,1,2,3,4,5,6,7) -Answer.

4 - variable Karnaugh map (K-map)

K-map for 4 variables x,y,z,w is discussed below with truth table and k-map plot. 

LTE - 4G Wireless Technology

Digital fundamentals.

Interview Questions.

Note: The columns and rows which are interchanged (not is sequence) are correct and part of kmap plots.

MINIMIZATION USING FOUR VARIABLE KARNAUGH MAP

f1=(x'y'z'w'+x'yz'w')+(x'y'zw'+x'yzw')

    =x'z'w'+x'zw'

    =x'w'

f2=(x'yz'w'+xyz'w')+(x'yzw'+xyzw')

    =yz'w'+yzw'

    =yw'

F=f1+f2

The Minimized Value of  F = x’w’ + yw’

 Four variables K-map (truth table and K-map plot).

1. F(x,y,w, z) = (0,1,2,3,4,6,11,14)
2. F(x,y,w, z) = (0,2,4,6,12,14)
3. F(x,y,w, z) = (0,2,5,7,8,11,13,15)

Don’t Care (X) Conditions in K-Maps

The “Don’t Care” conditions allow us to replace the empty cell of a K-Map to form a grouping of the variables. 

 we can consider a “Don’t Care” cell as either 1 or 0 or we can simply ignore that cell. Therefore, “Don’t Care” condition can help us to form a larger group of cells.

A Don’t Care cell can be represented by a cross(X) in K-Maps representing a invalid combination. 

For example, in Excess-3 code system, the states 0000, 0001, 0010, 1101, 1110 and 1111 are invalid or unspecified. These are called don’t cares. 

A standard SOP function having don’t cares can be converted into a POS expression by keeping don’t cares as they are, and writing the missing minterms of the SOP form as the maxterm of POS form. 

Similarly, a POS function having don’t cares can be converted to SOP form keeping the don’t cares as they are and write the missing maxterms of the POS expression as the minterms of SOP expression.

Example-1:
Minimise the following function in SOP minimal form using K-Maps:

f = m(1, 5, 6, 12, 13, 14) + d(4) 

Explanation:
The SOP K-map for the given expression is:

Therefore, SOP minimal is,

f = BC' + BD' + A'C'D 

Example-2:

Writing the given expression in POS form:

F(A, B, C, D) = M(6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15) 

F = A'(B' + C') 

K-maps for Sum-of-Product Design

Sum Of Product (SOP)

• Sum of Product is the abbreviated form of SOP. Sum of product form is a form of expression in Boolean algebra in which different product terms of inputs are being summed together. This product is not arithmetical multiply but it is Boolean logical AND and the Sum is Boolean logical OR.
  To understand better about SOP, we need to know about min term.

Min Term

• Minterm means the term that is true for a minimum number of combination of inputs. That is true for only one combination of inputs.
  Since AND gate also gives True only when all of its inputs are true so we can say min terms are AND of input combinations like in the table given below.
  3 inputs have 8 different combinations. Each combination has a min terms denoted by small m and its decimal combination number written in subscript. Each of these minterms will be only true for the specific input combination.

Examples:

K-maps for Product-of-Sum Design

Product of Sum

Product of Sum abbreviated for POS.

The product of Sum form is a form in which products of different sum terms of inputs are taken. These are not arithmetic product and sum but they are logical Boolean AND and OR respectively.

To better understand about Product of Sum, we need to know about Max term.

Max Term

Maxterm means the term or expression that is true for a maximum number of input combinations or that is false for only one combination of inputs.

Since OR gate also gives false for only one input combination. So Maxterm is OR of either complemented or non-complemented inputs.

Max terms for 3 input variables are given below.

3 inputs have 8 different combinations so it will have 8 maxterms. Maxterms are denoted by capital M and decimal combination number In the subscript as shown in the table given above.

In maxterm, each input is complemented because Maxterm gives ‘0’ only when the mentioned combination is applied and Maxterm is complement of minterm.

Product-of-sums design uses the same principles, but applied to the zeros of the function.Example:

Designing with Don't-Care Values

In some situations, we don't care about the value of a logic function.
For example, if we use wxyz to represent a number from 0 to 9, we need not worry about the function value produced for wxyz = 10...15.
For these situations, the function can be assigned an output in order to make the resulting circuit as simple as possible.
Suppose we wish to implement the function
f(wxyz)=Sum(3,5,6,7)
and we have the don't-care condition of
d=Sum(10,11,12,13,14,15).The sum-of-products implementation:
The product-of-sums implementation:



---