Wednesday, January 2, 2013

The Karnaugh map

The Karnaugh map is a graphical representation of all the combinations of the input variables that can exist in a logical circuit. The map consists of a number of squares, each of which represents a unique combination of the input variables. The number of squares in a map must be equal to 2n, where n is the number of input variables.

This means that a Boolean expression with two variables must be represented by a 4-square map, and an expression with three variables by an 8-square map, as shown.

The Karnaugh map7_19

To map an equation the equation should first be put into the sum-of-products form, e.g. The Karnaugh map 2 . Each term in the equation is mapped by a 1 in the appropriate square. Each term that is not present in the equation is mapped by a 0 in the appropriate square. Thus for the expression quoted previously the mapping is :

The Karnaugh map7_23

A term like AB is mapped by putting a 1 into two squares. The term tan be rewritten as  Untitled-8_03  and so the mapping is:

Untitled-8_07

A single variable, such as B for example, is mapped by putting 1 into four squares; B can be rewritten as Untitled-8_11 Karnaugh and so the mapping is:

A karnaugh mapping

A Karnaugh mapping of a Boolean expression can be used to minimize the expression by looping together 'adjacent1 squares in groups of two, four or eight. Two squares are considered to be adjacenl if they are (a) side-by-side, either horizontally or vertically, but not diagonally, (b) at each end of the map and in the same row. Thus, squares 0 and 2, 0 and 4, and 0 and 1 are adjacent but 1 and 7 are not. When squares are looped together all terms of the form The Karnaugh map become equal to 1 and are redundant.

The Karnaugh map 8_17

Example 9

Use a karnaugh map to simplify the equation  The Karnaugh map6

The Karnaugh map7 

solution

( a) the mapping is :

the mapping

the looped squares give F = AC + BC (Ans.)

(b ) The mapping is :

The Karnaugh map26_03 

From the map, F = AB + C (Ans.)

(C ) The mapping is :

The mapping 26_06

From the map, A karnaugh mapping26_08

Example 10

use a Karnaugh map simplify the equation A karnaugh mapping6A karnaugh mapping26_14  Confirm the result with a truth table.

First apply De Morgan's rules.

A karnaugh mapping26_19

 

the mapping is :

The Karnaugh map26_22

From the map, F = I (Ana.)

The truth table is shown by Table 17.

A karnaugh mapping26_26

Table 18 gives the truth table of a combinational logic circuit that is to be designed.

A karnaugh mapping27_03

The Boolean expression describing the logical operation of the circuit is A karnaugh mapping27_06 , This expression should be mapped to see whether any simplification is possible. The mapping is:

A karnaugh mapping27_10

From the map,  the map. Once the minimal Boolean expression has been obtained it must be implemented using the appropriate gates. Three possibilities exist. The wanted circuit can be implemented

(a) using AND, OR and NOT gates

(b) using NAND gates only, or

(c) using NOR gates only.

In both the TTL and the CMOS logic families NAND and NOR gates are cheaper, faster to operate and dissipate less power than AND or OR gates. It is also advantageous from both the manufacturing and maintenance points of view if a circuit uses just one type of gate troughout. It is therefore common practice to construct a circuit using either NAND or NOR gates alone.

The next step in deriving the wanted circuit should be to draw the logic diagram using AND, OR and NOT gates. The diagram can then be converted to a circuit that uses either NAND or NOR gates only by simply replacing each AND/OR/NOT gate by its NAND/NOR equivalent.

The final step is then to decide which integrated circuits will be used to construct the final circuit.

Suppose the Boolean expression to be implemented is the map.

(a) The logic diagram using AND/OR/NOT gates is shown in Fig. 24. One AND, one OR and one NOT gate are needed, necessitating the use of three integrated circuits.

(b) The NAND equivalent of Fig. 24 is obtained by replacing each gate by its NAND gate equivalent. The circuit obtained is shown in Fig. 25(a). It might seem, at first sight, that six gates are now needed but two of these gates give successive inversions and are therefore redundant. Removing the redundant gates gives the final circuit of Fig. 25(b). This circuit contains four NAND gates and will need only one integrated circuit. Fig. 26 shows the circuit constructed with a 7400 quad 2-inpui NAND gate.

the map27_14

the map28_03

(c) The NOR gate version of Fig. 24 can be obtained similarly. Fig. 27(a) shows the first logic circuit diagram and Fig. 27(b) shows the final circuit after redundant gates have been removed. Again, four gates are needed and the circuit could be fabricated using the 7402 quad 2-input NOR gate.