HABARI LIST Articles THE KARNAUGH MAP - ICT CLASSROOM

THE KARNAUGH MAP - ICT CLASSROOM

Article by Benson Mmari

The Karnaugh map, also known as the K-map, is a method of simplify Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward Veitch's 1952 Veitch diagram.

Karnaugh maps are used to simplify real-world logic requirements so that they can be implemented using a minimum number of physical logic gates. A sum-of-products expression can always be implemented using AND gates feeding into an OR gate, and a product-of-sums expression leads to OR gates feeding an AND gate.

Karnaugh maps can also be used to simplify logic expressions in software design. Boolean conditions, as used for example in conditional statements, can get very complicated, which makes the code difficult to read and to maintain. Once minimized, canonical sum-of-products and product-of-sums expressions can be implemented directly using AND and OR logic operators.

Karnaugh maps are used to facilitate the simplification of Boolean algebra functions. Take the Boolean function described by the following truth table.

Minterms and maxterms

Each row of a truth table can be associated with a minterm, which is a product (AND) of all variables in the function, in direct or complemented form. A minterm has the property that it is equal to 1 on exactly one row of the truth table.

Figure 1shows the miniterm as shown below:

			minterm
0	0	0	$\overline{A}\, \cdot \overline{B}\, \cdot \overline{C}\, =m_0$
0	0	1	$\overline{A}\, \cdot \overline{B}\, \cdot C =m_1$
0	1	0	$\overline{A}\, \cdot B \cdot \overline{C}\, =m_2$
0	1	1	$\overline{A}\, \cdot B \cdot C =m_3$
1	0	0	$A \cdot \overline{B}\, \cdot \overline{C}\, =m_4$
1	0	1	$A \cdot \overline{B}\, \cdot C =m_5$
1	1	0	$A \cdot B \cdot \overline{C}\, =m_6$
1	1	1	$A \cdot B \cdot C =m_7$

The subscript on the minterm is the number of the row on which it equals 1. (The row numbers are obtained by reading the values of the variables on that row as a binary number.)

Minterms provide a way to represent any boolean function algebraically, once its truth table is specified. The function is given by the sum (OR) of those minterms corresponding to rows where the function is 1. By the minterm property, the OR will contain a term equal to 1 (making the function 1) on exactly those rows where the function is supposed to be 1.

Example: suppose a function F is defined by the following truth table:

Figure 2


0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Since F=1 on rows 1, 2, 4, and 7.

$\begin{eqnarray*} F &=& m_1 + m_2 + m_4 + m_7 \\ &=& \overline{A}\, \cdot \ove... ... A \cdot \overline{B}\, \cdot \overline{C}\, + A \cdot B \cdot C \end{eqnarray*}$

$\begin{displaymath}\textstyle F = \sum ( 1,2,4,7)\end{displaymath}$ .

Each row of a truth table is also associated with a maxterm, which is a sum (OR) of all the variables in the function, in direct or complemented form. A maxterm has the property that it is equal to 0 on exactly one row of the truth table.

Belowis the three-variable truth table and the corresponding maxterms:

Figure 3

			maxterm
0	0	0
0	0	1	$A + B + \overline{C}\, =M_1$
0	1	0	$A + \overline{B}\, + C =M_2$
0	1	1	$A + \overline{B}\, + \overline{C}\, =M_3$
1	0	0	$\overline{A}\, + B + C =M_4$
1	0	1	$\overline{A}\, + B + \overline{C}\, =M_5$
1	1	0	$\overline{A}\, + \overline{B}\, + C =M_6$
1	1	1	$\overline{A}\, + \overline{B}\, + \overline{C}\, =M_7$

The function is given by the product (AND) of those maxterms corresponding to rows where the function is 0. By the maxterm property, the AND will contain a term equal to 0 (making the function 0) on exactly those rows where the function is supposed to be 0.

$\begin{eqnarray*} F &=& M_0 \cdot M_3 \cdot M_5 \cdot M_6 \\ &=& (A + B + C) \... ...+ B + \overline{C}\,) \cdot(\overline{A}\, + \overline{B}\, + C) \end{eqnarray*}$

$\begin{displaymath}\textstyle F = \prod(0,3,5,6)\end{displaymath}$

Two-Variable Karnaugh Map

Another approach to simplification is called the Karnaugh map, or K-map.

• A K-map is a truth table graph, which aids in visually simplifying logic.

• It is useful for up to 5 or 6 variables, and is a good tool to help understand the process of logic simplification

Figure 4

Three-Variable Karnaugh Map

A useful K-map is one of three variables.

• Each square represents a 3-variable minterm or maxterm.

• All of the 8 possible 3-variable terms are represented on the K-map.

Figure 5

A 4-variable K-map can simplify problems of four Boolean variables.

• The K-map has one square for each possible minterm (16 in this case).

Figure 6

K-map rules

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.

Summary

No zeros allowed.
No diagonals.
Only power of 2 numbers of cells in each group.
Groups should be as large as possible.
Everyone must be in at least one group.
Overlapping allowed.
Wrap around allowed.
Fewest numbers of groups possible.

REFERENCES

· The University of Texas at Dallas- Erik Jonson School of Engineering and Computer Science (https://goo.gl/drgZyR) Visited on 19^th July 2016 at 15:03 hrs.

· WIKIPEDIA | Karnaugh Maps (https://en.wikipedia.org/wiki/Karnaugh_map) Site visited on 6^th June, 2016 15:46 hrs

· Karnaugh Maps | Introduction, and Rules of simplification (http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karnaugh.html) Site visited on 6^th June, 2016 at 16:58 hrs.

· What is Web – The introduction to Karnaugh Map (http://goo.gl/tfvitL) visited on 19^th July 2016 at 13:39 hrs.

· All about Circuits – Karnaugh Map and its Procedures (http://goo.gl/p88MCy) visited on 19^th July 2016 at 11:56 hrs.

· Surrey UK – Minimization and K-Map Rules (http://goo.gl/12cmRa) visited on 12^th July 2016 at 23:32 hrs.

Author : FOR MAPENE

Subscribe to: Post Comments (Atom)

» Articles » THE KARNAUGH MAP - ICT CLASSROOM

THE KARNAUGH MAP - ICT CLASSROOM

0 Articles 12:30

Article by Benson Mmari

The Karnaugh map, also known as the K-map, is a method of simplify Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward Veitch's 1952 Veitch diagram.

Karnaugh maps are used to facilitate the simplification of Boolean algebra functions. Take the Boolean function described by the following truth table.

Minterms and maxterms

Figure 1shows the miniterm as shown below:

			minterm
0	0	0	$\overline{A}\, \cdot \overline{B}\, \cdot \overline{C}\, =m_0$
0	0	1	$\overline{A}\, \cdot \overline{B}\, \cdot C =m_1$
0	1	0	$\overline{A}\, \cdot B \cdot \overline{C}\, =m_2$
0	1	1	$\overline{A}\, \cdot B \cdot C =m_3$
1	0	0	$A \cdot \overline{B}\, \cdot \overline{C}\, =m_4$
1	0	1	$A \cdot \overline{B}\, \cdot C =m_5$
1	1	0	$A \cdot B \cdot \overline{C}\, =m_6$
1	1	1	$A \cdot B \cdot C =m_7$

The subscript on the minterm is the number of the row on which it equals 1. (The row numbers are obtained by reading the values of the variables on that row as a binary number.)

Example: suppose a function F is defined by the following truth table:

Figure 2


0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Since F=1 on rows 1, 2, 4, and 7.

$\begin{eqnarray*} F &=& m_1 + m_2 + m_4 + m_7 \\ &=& \overline{A}\, \cdot \ove... ... A \cdot \overline{B}\, \cdot \overline{C}\, + A \cdot B \cdot C \end{eqnarray*}$

$\begin{displaymath}\textstyle F = \sum ( 1,2,4,7)\end{displaymath}$ .

Belowis the three-variable truth table and the corresponding maxterms:

Figure 3

			maxterm
0	0	0
0	0	1	$A + B + \overline{C}\, =M_1$
0	1	0	$A + \overline{B}\, + C =M_2$
0	1	1	$A + \overline{B}\, + \overline{C}\, =M_3$
1	0	0	$\overline{A}\, + B + C =M_4$
1	0	1	$\overline{A}\, + B + \overline{C}\, =M_5$
1	1	0	$\overline{A}\, + \overline{B}\, + C =M_6$
1	1	1	$\overline{A}\, + \overline{B}\, + \overline{C}\, =M_7$

$\begin{eqnarray*} F &=& M_0 \cdot M_3 \cdot M_5 \cdot M_6 \\ &=& (A + B + C) \... ...+ B + \overline{C}\,) \cdot(\overline{A}\, + \overline{B}\, + C) \end{eqnarray*}$

$\begin{displaymath}\textstyle F = \prod(0,3,5,6)\end{displaymath}$

Two-Variable Karnaugh Map

Another approach to simplification is called the Karnaugh map, or K-map.

• A K-map is a truth table graph, which aids in visually simplifying logic.

• It is useful for up to 5 or 6 variables, and is a good tool to help understand the process of logic simplification

Figure 4

Three-Variable Karnaugh Map

A useful K-map is one of three variables.

• Each square represents a 3-variable minterm or maxterm.

• All of the 8 possible 3-variable terms are represented on the K-map.

Figure 5

A 4-variable K-map can simplify problems of four Boolean variables.

• The K-map has one square for each possible minterm (16 in this case).

Figure 6

K-map rules

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.

Summary

No zeros allowed.
No diagonals.
Only power of 2 numbers of cells in each group.
Groups should be as large as possible.
Everyone must be in at least one group.
Overlapping allowed.
Wrap around allowed.
Fewest numbers of groups possible.

REFERENCES

· The University of Texas at Dallas- Erik Jonson School of Engineering and Computer Science (https://goo.gl/drgZyR) Visited on 19^th July 2016 at 15:03 hrs.

· WIKIPEDIA | Karnaugh Maps (https://en.wikipedia.org/wiki/Karnaugh_map) Site visited on 6^th June, 2016 15:46 hrs

· Karnaugh Maps | Introduction, and Rules of simplification (http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karnaugh.html) Site visited on 6^th June, 2016 at 16:58 hrs.

· What is Web – The introduction to Karnaugh Map (http://goo.gl/tfvitL) visited on 19^th July 2016 at 13:39 hrs.

· All about Circuits – Karnaugh Map and its Procedures (http://goo.gl/p88MCy) visited on 19^th July 2016 at 11:56 hrs.

· Surrey UK – Minimization and K-Map Rules (http://goo.gl/12cmRa) visited on 12^th July 2016 at 23:32 hrs.

Posted by FOR MAPENE

0 comments

Dear readers, after reading the Content please ask for advice and to provide constructive feedback Please Write Relevant Comment with Polite Language.Your comments inspired me to continue blogging. Your opinion much more valuable to me. Thank you.

HABARI LIST

Featured Posts

THE KARNAUGH MAP - ICT CLASSROOM

Minterms and maxterms

Two-Variable Karnaugh Map

Three-Variable Karnaugh Map

K-map rules

Summary

Author : FOR MAPENE

Share this

Label

THE KARNAUGH MAP - ICT CLASSROOM

Minterms and maxterms

Two-Variable Karnaugh Map

Three-Variable Karnaugh Map

K-map rules

Summary

Post a Comment

0 comments

Featured Posts

THE KARNAUGH MAP - ICT CLASSROOM

Minterms and maxterms

Two-Variable Karnaugh Map

Share this

Related Posts

Label

Minterms and maxterms

Two-Variable Karnaugh Map

Next

Newer Post

Previous

Older Post

Post a Comment