Karnaugh Maps

12 Key excerpts on "Karnaugh Maps"

• 

  eBook - ePub

  Electronic Logic Circuits

  • J. Gibson(Author)
  • 2013(Publication Date)
  • Routledge

    (Publisher)

  Chapter 2 that the reduction of Boolean expressions by inspection, using the rules of Boolean algebra, is not obvious in many cases. Some method is required which will assist with this reduction; when five or fewer variables are involved one of the most useful techniques is that which uses a Karnaugh map.

  3.5 Karnaugh Maps

  Karnaugh Maps are a modification of Venn diagrams, which are a pictorial device that should be familiar to any reader with some elementary knowledge of set theory. It is not essential to understand the origins of Karnaugh Maps in order to use them to simplify logical expressions; some of the more advanced texts listed in the bibliography include details of the basic theory of the technique.

  A Karnaugh map consists of a rectangular area which is divided into squares (or elements) and each square represents one minterm. There is only one square for any minterm and there is a square for every minterm. The squares are not allocated to the minterms at random, they are arranged so that a movement of one square vertically (up or down) or one square horizontally (left or right) results in the minterms associated with the two adjacent squares differing only in a single variable. In other words the two minterms are identical except for one variable which is inverted in one of them but not in the other. Diagonal movements on the Karnaugh map are not of interest. Within these rules many different maps may be drawn. Figure 3.1 shows two different maps for a system with three inputs of A, B and C; both maps are correct.

  A Karnaugh map is best regarded as a three-dimensional device which has to be represented in a two-dimensional form when it is printed. This is one reason why so many maps may be drawn. When movements of one square are repeatedly made in the same direction the edge of the map is eventually reached. A further move of one square is equivalent to moving off the edge of the map and returning onto it at the opposite edge, i.e. the top edge should be joined to the bottom one and the left-hand edge should be joined to the right-hand one. The only way in which the map could be drawn with this form is on a doughnut-shaped surface (the surface of a toroid). The two-dimensional map is an attempt to represent this surface and it is satisfactory provided that it is remembered that a movement off one edge of the map and back on at the opposite edge is identical to a move from one square to an adjacent square.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Foundations of Digital Logic Design

  • Gideon Langholz, Abraham Kandel;Joe L Mott;;(Authors)
  • 1998(Publication Date)
  • WSPC

    (Publisher)

  168 CHAPTER 4 COMBINATIONAL LOGIC CIRCUITS described by binary information. The Karnaugh map and Quine-McCluskey procedures simply follow this clue to its logical conclusion. 4.3 Karnaugh Maps A Karnaugh map (or K-map for short) is a graphical method for representing the truth table of a Boolean function. K-maps may be used to represent functions of any number of variables, but are most often used for functions of at most six variables. If n is the number of variables, then the K-map has 2 n cells, one for each of the 2 n minterms (maxterms) and, therefore, one for each row of the truth table. Moreover, these cells are arranged such that the minterms (maxterms) are displayed in a geometric pattern so that logically adjacent terms are visibly apparent. Minimization, therefore, can be accomplished by recognizing basic patterns on the K-map. Each cell of the K-map is assigned a coordinate that forms an /i-bit binary number corresponding to a minterm (maxterm) of n literals. Two cells are adjacent if their corresponding binary combinations differ by only one bit. If a function F is expressed in canonical sum-of-products (SOP) form, then we complete the K-map of F by placing a 1 in those cells whose coordinates correspond to minterms that occur in the canonical form, and placing a 0 in each of the remaining cells. If F is in canonical product-of-sums (POS) form, we place a 0 in those cells that correspond to maxterms of the canonical form and a 1 in all the others. If the functional value 1 occurs in a cell of the K-map of a function F, then the cell is called a 1-cell of F; if a 0 value occurs, the cell is called a 0-cell. Hence, two adjacent 1-cells (0-cells) immediately identify the presence of a redundant variable in the corresponding minterms (maxterms); four adjacent 1-cells (O-cells) imply the existence of two redundant variables; and so on. We introduce the notion of K-maps assuming that F is in SOP form.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Logic Design

  • Brian Holdsworth, Clive Woods(Authors)
  • 2002(Publication Date)
  • Newnes

    (Publisher)

  Karnaugh map or K-map.

  Figure 3.4 The map for two Boolean variables

  Karnaugh Maps can be labelled and marked in a variety of ways. For example, each cell can be numbered with the decimal subscript of the minterm that occupies the cell. In this case, the bottom right-hand cell would be numbered with 3, as shown in Figure 3.5(a) . The cell numbering shown in Figure 3.5(a) assumes that A is the most significant bit in the binary to decimal conversion, and B the least significant bit. Since A has weighting 2 and B has weighting 1, this is sometimes indicated in abbreviated form as A, B ≡ 2,1 (which is not a conventional equation, but merely indicates the respective weights of A and B ). Alternatively, the cells can be marked with the binary representation of their corresponding subscript, as shown in Figure 3.5(b) . A further possibility for the axis labels is to use instead of 0 and 1, as shown in Figure 3.5(c) .

  Figure 3.5 Alternative methods for marking a Karnaugh map

  For three variables, the map contains eight cells, one for each of the possible minterms as shown in Figure 3.6(a) , drawn for the weighting A, B, C ≡ 4,2,1. The variable A is allocated to the two rows of the map, while the variables B and C are allocated to the four columns. There are four combinations of these two variables, and each combination is allocated to a column of the map.

  Figure 3.6 Karnaugh Maps for three variables

  The columns and rows are allocated in the way shown so that two adjacent columns are always associated with the true value of a variable or, alternatively, its complement. An examination of Figure 3.6(a) shows that the first two columns are associated with the second and third columns are associated with C , and the third and fourth columns are associated with B. The reason for allocating the variables to the columns in this way will be clearer when the procedure for minimisation of a Boolean function is discussed later in this chapter. Note, however, that the column labels along the top of the K-map are the same as the Gray code order for two binary variables (see section 1.21 ). The reason for this is that the underlying principle of the K-map is that in moving from one cell to an adjacent cell either vertically or horizontally, the value of one (and only one ) Boolean variable may change, and of course similarly Gray codes must change by just one digit only at each step. An alternative method of labelling the axes of a 3-variable K-map is shown in Figure 3.6(b)

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Fundamentals of Logic Design, Enhanced Edition

  • Charles Roth, Jr., Larry Kinney, Eugene John, , Charles Roth, Jr., Larry Kinney, Eugene John(Authors)
  • 2020(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Karnaugh Maps 137 Figure 5-1 shows the truth table for a function F and the corresponding Karnaugh map. Note that the value of F for A = B = 0 is plotted in the upper left square, and the other map entries are plotted in a similar way in Figure 5-1(b). Each 1 on the map corresponds to a minterm of F. We can read the minterms from the map just like we can read them from the truth table. A 1 in square 00 of Figure 5-1(c) indi- cates that Auni2032Buni2032 is a minterm of F. Similarly, a 1 in square 01 indicates that Auni2032B is a minterm. Minterms in adjacent squares of the map can be combined since they differ in only one variable. Thus, Auni2032Buni2032 and Auni2032B combine to form Auni2032, and this is indicated by looping the corresponding 1’s on the map in Figure 5-1(d). Figure 5-2 shows a three-variable truth table and the corresponding Karnaugh map (see Figure 5-27 for an alternative way of labeling maps). The value of one vari- able (A) is listed across the top of the map, and the values of the other two variables (B, C) are listed along the side of the map. The rows are labeled in the sequence 00, 01, 11, 10 so that values in adjacent rows differ in only one variable. For each combination of values of the variables, the value of F is read from the truth table and plotted in the appropriate map square. For example, for the input combination ABC = 001, the value F = 0 is plotted in the square for which A = 0 and BC = 01. For the combination ABC = 110, F = 1 is plotted in the A = 1, BC = 10 square.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Design

  Basic Concepts and Principles

  • Mohammad Karim, Xinghao Chen, Mohammad A. Karim(Authors)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  Karnaugh map , or K-map, for short.

  It must be noted though that designers may often use devices other than gates for realizing complex logic functions. For example, read-only-memory as well as programmable logic devices can be used to generate multiple functions of multiple-input variables without regard to much minimization. Consequently, the traditional demand for absolute minimization has been diminished somewhat in recent years by the introduction of such devices. However, there are many occasions when it is absolutely necessary to reduce complex logic functions. The choice between a simpler logic circuit and a faster logic circuit is generally a matter of judgement. Higher speed often means higher cost. The cost, on the other hand, is a composite function of the number of logic gates, the number of logic layers, and the number of inputs per gate in each of these layers. The exact rat10 between the cost of a logic gate and the cost of logic gate input depends on the type of logic gate being used. In most cases, however, the cost of an additional logic gate will be several times that of an additional gate input on an already existing logic gate. When speed, for example, is the central issue, either a sum-of-product (SOP) or a product-of-sum (POS) expression is desirable for the most simplified logic function. For certain circuit technology, one may not assign any cost to inverting the variables. In such cases, both complemented and uncomplemented literals are assumed to be available when needed throughout the logic network.

  Unfortunately, K-map-based scheme is neither suited for solving problems involving more than six input variables nor easily programmable. In this chapter, therefore, we also present a minimization algorithm, known as Quine-McCluskey’s (Q-M) tabular reduction technique, that is reasonably straightforward. It is possible to come up with more than one valid minimization of a function if K-maps are used because of the different ways the maps may be interpreted. The Q-M technique, in comparison, uses a systematic method to conduct an exhaustive search to determine all possible combinations of logically adjacent minterms. Typically, the technique converges to the same optimum solution for the logic function. However, the technique is often time consuming, especially for functions having multiple-input variables. But since it follows a systematic and algorithmic approach, it is possible to write software programs based on the Q-M method to allow computer-aided design of logic circuits. The Q-M technique can also be used to optimize multiple-output logic functions for circuits that have one or more common input variables.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Digital Logic

  With an Introduction to Verilog and FPGA-Based Design

  • M. Rafiquzzaman, Steven A. McNinch(Authors)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  By inspecting the truth table, ƒ = 0 for maxterms M 0 , M 4 , M 5 , and M 7 . Therefore, the function ƒ can be obtained by logically ANDing these maxterms as follows: ƒ = ΠM(0, 4, 5, 7) = (A + B + C)(A + B + C)(A + B + C)(A + B + C) Minterms, Maxterms, And Karnaugh Map 81 4.2 Karnaugh Maps A Karnaugh map, or simply a K-map, is a diagram showing the graphical form of a truth table. Since there is no specific set of rules for minimizing a Boolean function using identities, it is difficult to know whether the minimum expression is obtained. The K-map provides a systematic procedure for simplifying Boolean functions of typically up to five variables. It is difficult to obtain K-maps analytically for more than five variables. However, a computer program using a tabular method such as the Quine- McCluskey algorithm can be used to minimize Boolean functions with more than five variables. Note that the theory behind K-map is based on Gray code and the identity, A + A = 1. The K-map is a diagram containing squares with each square representing one of the minterms of the Boolean function. For example, the K-map of two variables (A, B) contains four squares. The four minterms A B, AB, AB, and AB are represented by each square. Similarly, there are 8 squares for three variables, 16 squares for four variables, and 32 squares for five variables. Since any Boolean function can be expressed in terms of minterms, the K-map can be used to visually represent a Boolean function. The K-map is drawn in such a way that there is only a one-bit change from one square to the next (Gray code). Squares can be combined in groups of 2 n where n = 0, 1, 2, 3, 4, 5, and the Boolean function can be minimized by following certain rules. This minimum expression will reduce the total number of gates for implementation. Thus, the cost of building the logic circuit is reduced. 4.2.1 Two-Variable K-map Figure 4.3 shows the K-map for two variables.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Digital Logic Design

  • B. Holdsworth(Author)
  • 2014(Publication Date)
  • Butterworth-Heinemann

    (Publisher)

  2 Karnaugh Maps and function simplification 2.1 Introduction One of the objectives of the digital designer when using discrete gates is to keep the number of gates to a minimum when implementing a Boolean function. The smaller the number of gates used the lower the cost of the circuit. Simplification can be achieved by a purely algebraic process, but this can be tedious, and the designer is not always sure that the simplest solution has been produced at the end of the process. A much easier method of simplification is to plot the function on a Karnaugh map and with the aid of a number of simple rules to reduce the Boolean function to its minimal form. This particular method is very straightforward up to and including six variables; above six it is better to go to a tabulation method like Quine—McCluskey, or possibly to use an iterative method of reduction which involves the formation of optional products. Function simplification is not so important in these days of MSI (medium-scale integration) and LSI (large-scale integration) as it was when discrete gates were used for implementing Boolean functions, although it gives an insight into the methods used for manipulating the algebra, and as such it is worthy of the reader's attention. 2.2 Product and sum terms A product term of M variables is the logical product of all n variables, where any of the n variables may be represented by the variable itself or 16 Karnaugh Maps and function simplification 17 VA 0 0 1 1 B 0 1 0 1 P-terms P 0 --ÂB P x =AB P z --AB P3--AB 5-terms S 0 *A + ß 5, --A + B 5 2 =/44/9 5 3 =,4 4/9 its complement. In the case of two variables A and B there are four possible combinations of the variables and these are tabulated in figure 2.1. Corresponding to these four combinations of the variables there are four possible Aterms which can be obtained as follows. In the first row of the table A = 0 and Z? = 0, hence A B = 1.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Electricity and Electronics for Renewable Energy Technology

  An Introduction

  • Ahmad Hemami(Author)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  The sum of the expressions Karnaugh map: Special tables by the use of which logic cir-cuits can be simplified and their output can be determined. K-map: Abbreviation for Karnaugh map. 698 Electricity and Electronics for Renewable Energy Technology for those cells with 1 inside defines the logic function for the application. In the present two-input example the expression for the output Z is Z A B A B = ⋅ + ⋅ This is the expression for the complement of a XOR gate. So, for this application the required circuit consists of a XOR gate and a NOT gate. For this problem it was not necessary to use a K-map because it is a trivial case of two inputs. But, for three and four inputs the problem is more involved. One important property of a K-map is that moving from any cell to a neigh-boring cell implies only one change (and never more than one). One change means that only one of the inputs switches to its complement. You can see that for two-input K-map moving horizontally changes B , only, and moving vertically changes A , only. This property helps to select the correct entry for extension of the two-input K-map to three and four inputs, as can be seen next. Also, take note that in K-map notation all cells have two neighbors vertically and two neighbors horizontally. In other words, the cells are assumed to be seamlessly organized in circles and not in rows and col-umns. This matter is more important and clearer for three and four inputs and will be visited again. 23.5.2 K-Map for Three Inputs The K-map for two inputs can be extended to three inputs by combining the third input either in the horizontal or vertical direction with the input already placed there. Here we do that horizontally, and the third variable C is combined with B , as it is shown in Figure 23.26. The K-map for three variables has eight cells, each one of which represents one of the possible eight combinations of three inputs. In Figure 23.26 the cells are numbered from 1 to 8 for referencing.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Electronics 1

  Combinational Logic Circuits

  • Tertulien Ndjountche(Author)
  • 2016(Publication Date)
  • Wiley-ISTE

    (Publisher)

  Figure 4.14 . The cells in the map can be grouped in the following manner:

  The simplified expression of Z is then given by:

  [4.21]

  1. – Minterms of the function Z are assigned to cells in the four-variable Karnaugh map as follows:

  Figure 4.14. Six-variable Karnaugh map

  The products obtained from the grouping carried out in the Karnaugh map shown in Figure 4.15 are written as follows:

  Figure 4.15. Karnaugh map with entered variables

  The elimination of the variables permitted by loops 3, 4 and 5 are explained by the fact that:

  [4.22]

  and

  [4.23]

  As before, we obtain the simplified equation for the function Z that is equal to:

  [4.24]

  4.3.5. Representation based on the XOR and AND operators

  For some logic functions, it may be necessary to use representation based on the XOR and AND gates instead of using sum-of-products representations. This is especially the case if the objective is to minimize the total number of logic gates and the interconnect complexity.

  The Karnaugh map depicted in Figure 4.16 gives a representation for each of the three logic functions used as examples. Three types of loops can be identified on the map, including minterms that are diagonal, one position apart from each other, or adjacent. The logic expressions that can be associated with the different loops can be written as follows:

  • – loop 1:
  • – loop 2:
  • – loop 3:

  Figure 4.16. Karnaugh map with entered variables

  We can see that each expression is made more compact using the XOR logic function.

  4.4. Systematic methods for simplification

  The Karnaugh method is appropriate for the simplification of logic functions with a small number of variables. As the number of variables increases, systematic procedures or algorithms are used for simplification. The implementation of these algorithms takes place in two steps. The first step is the determination of the prime implicants. The second step consists of constituting the set of terms that make up each minimized logic expression.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Logic Design

  • Sajjan G. Shiva(Author)
  • 2018(Publication Date)
  • CRC Press

    (Publisher)

  Chapter 2 to minimize functions is tedious and error prone. Its success depends on our ability to recognize the application of a theorem or a postulate during the minimization process. Such recognition may not be obvious. Further, there is no general set of rules to aid that recognition.

  In this chapter, we will examine two popular minimization techniques. The first is based on a graphical representation of Boolean functions using Karnaugh Maps (K-maps), and the second is a tabular method devised by Quine and McCluskey, called the Quine-McCluskey procedure (QM procedure). Both of these methods are mechanical in nature. K-maps are useful in minimizing functions with up to five or six variables. The QM procedure is useful for functions of any number of variables and can easily be programmed to run on a digital computer.

  Generally, several minimum functions can be obtained for a given function using either method, based on the choices made during the minimization process. All minimum functions with the same number of literals yield circuits of the same complexity; hence, any of them can be selected for implementation.

  3.1    K-maps

  K-maps are modified Venn diagrams. Consider the Venn diagram for two variables, A and B, shown in Figure 3.1(a) . The four areas correspond to minterms m0 , m1 , m2 , and m3 , as shown in (b). Each of these areas is represented by a square (block) in the map (c). Here the union of the two blocks in the second column yields A (i.e., AB′ + AB = A), and hence the area covered by these two blocks corresponds to A. Similarly, the first column corresponds to A′; the first row corresponds to B′, and the second row corresponds to B. The usual forms of the two-variable K-map are shown in (d) and (e). The values 0 and 1 shown at the top of the map—in (e)—correspond to the values of A, and those shown on the left side are the values of B

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Higher Engineering Mathematics

  • John Bird(Author)
  • 2017(Publication Date)
  • Routledge

    (Publisher)

  Table 11.11 (c). To simplify a four-variable Boolean expression, the Boolean expression is depicted on a Karnaugh map as outlined above. Any cells on the map having common edges either vertically or horizontally are grouped together to form couples of eight cells, four cells or two cells. During coupling, the horizontal lines at the top and bottom of the cells may be considered to be common edges, as are the vertical lines on the left and the right of the cells. The simplified Boolean expression for a couple is given by those variables common to all cells in the couple. See Problems 18 and 19.

  Summary of procedure when simplifying a Boolean expression using a Karnaugh map

  1. Draw a four-, eight- or sixteen-cell matrix, depending on whether there are two, three or four variables.
  2. Mark in the Boolean expression by putting 1s in the appropriate cells.
  3. Form couples of 8, 4 or 2 cells having common edges, forming the largest groups of cells possible. (Note that a cell containing a 1 may be used more than once when forming a couple. Also note that each cell containing a 1 must be used at least once.)
  4. The Boolean expression for the couple is given by the variables which are common to all cells in the couple.

  Problem 14.    Use the Karnaugh map techniques to simplify the expression

  P ¯

  ·

  Q ¯

  +

  P ¯

  · Q

  Using the above procedure:

  1. The two-variable matrix is drawn and is shown in Table 11.12 .
  2. The term

     P ¯

     ·

     Q ¯

     is marked with a 1 in the top left-hand cell, corresponding to Ρ = 0 and Q = 0;

     P ¯

     ·

     Q ¯

     is marked with a 1 in the bottom left-hand cell corresponding to P = 0 and Q = 1
  3. The two cells containing 1s have a common horizontal edge and thus a vertical couple can be formed.
     Table 11.11
  4. (d) The variable common to both cells in the couple is

     P = 0 ,   i .e .  

     P ¯

     thus
     P ¯

     ⋅

     Q ¯

     +

     P ¯

     ⋅ Q =

     P ¯

  Table 11.12

  Problem 15.    Simplify the expression

  X ¯

  ⋅ Y ⋅

  Z ¯

  +

  X ¯

  ⋅

  Y ¯

  ⋅ Z + X ⋅ Y ⋅

  Z ¯

  + X ⋅

  Y ¯

  ⋅ Z

  by using Karnaugh map techniques.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Sequential Logic

  Analysis and Synthesis

  • Joseph Cavanagh(Author)
  • 2018(Publication Date)
  • CRC Press

    (Publisher)

  For example, consider the first term of Equation 1.18. If x 2 x 3 = 10, then Equation 1.18 yields z 1 = 1 + ⋅ ⋅ ⋅ + 0 which generates a value of 1 for z 1 . Ap-plying x 2 x 3 = 10 to Equation 1.19 will cause every term to be equal to 1, such that, z 1 = (1) (1) (1) = 1. Figure 1.1 (d) illustrates a 5-variable Karnaugh map. To determine adja-cency, the left map is superimposed on the right map. Any cells that are then physically adjacent are also logically adjacent and can be combined. Since x 5 is the low-order variable, the left map contains only even-numbered minterms; the right map is characterized by odd-numbered minterms. If 1s are entered in minterm locations 28, 29, 30, and 31, the four cells combine to yield the term x 1 x 2 x 3 . Figure 1.1 (e) illustrates an alternative configuration for a Karnaugh map for five variables. The map hinges along the vertical centerline and folds like a book. Any squares that are then physically adjacent are also logically adjacent. For example, if 1s are entered in minterm locations 24, 25, 28, and 29, then the four squares combine to yield the term x 1 x 2 x 4 ′ . Some minterm locations in a Karnaugh map may contain unspecified en-tries which can be used as either 1s or 0s when minimizing the function. These “ don’ t care ” entries are indicated by a dash (–) in the map. A typical situation which includes “don’t care ” entries is a Karnaugh map used to represent the BCD numbers. This requires a 4-variable map in which minterm locations 10 through 15 contain unspecified entries, since digits 10 through 15 are invalid for BCD. Example 1.9 A minimized equation will be derived which is asserted when-ever a BCD digit is even. All even BCD digits are plotted on a Karnaugh map as shown in Figure 1.3 for function z 1 . The unspecified entries in minterm lo-cations 10, 12, and 14 are assigned a value of 1; all remaining unspecified en-tries are assigned a value of 0.

  Sign up to read

  Learn more about book