Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Karnaugh Maps

  1. Nov 19, 2005 #1
    In the next few insertions, I shall attempt to explain the concept and operation of Karnaugh Maps. I hope this will be of interest to someone. I would welcome your questions and opinions.

    Initial Concept

    M. Karnaugh published a paper in October 1953, in which he described the basic principles of what has since become known as the ‘Karnaugh Mapping’ technique. In this re-examination of that technique, attempt will be made to explain, as thoroughly as possible, the ideas behind this technology, and to show some ways in which it can be used to simplify the digital logic design function, and to demonstrate some of the exceptional power and flexibility that can be exercised in this graphical mapping method. Hopefully, when finished, this tutorial will provide a basis for facilitating much of the process of designing many of the essential components that are used in digital assemblies.

    As a start, three attachments are included with this insertion in the string; a set of four-variable K-Maps, a set of six-variable K-Maps, and a 'Truth Table' framework that can be used with maps of up to eight-variables. These can be printed and used whenever needed. In this tutorial, we will show how these are used together. An eight-variable map, and possibly a ten-variable map will be included later.

    First, we shall explain the reasoning behind the map, then we shall illustrate its use.

    Concept Refinement

    The Karnaugh map, as it was initially envisioned, was considered to be directly capable of minimizing Boolean equations of up to only four variables. To handle a greater number of variables, two or more maps had to be used together, a somewhat cumbersome process - - - and this still entailed a practical working limit of up to approximately six variables. (The process essentially extends the map into three dimensions.)

    Then, about a decade after Karnaugh's paper, an individual named Matthew Mahoney observed a symmetrical reflecting approach behind the process of map construction which showed that maps could be extended in design beyond four variables, and from that approach he came up with a slightly different design which, was termed the 'Mahoney Map'. That approach will be shown (in passing) in a future insertion.

    KM
     

    Attached Files:

  2. jcsd
  3. Nov 19, 2005 #2
    The basic Map Structure

    1.) The basic Map Structure

    The Karnaugh Map is made up essentially of an array of adjacent rectangular "cells", each of which represents a predefined logical state (off or on; "0" or "1") of the total set of possible variable value combinations represent-able, thus if the map is designed for three variables (for example), then it would have 2^3 (or 8) cells. We will demonstrate how the cells are arranged within the map.

    First, however let it be stated that the K-Map is simply a vehicle for graphically performing and demonstrating the application of the various Boolean axioms (which are given in table 1). As an example, figure 1 shows a couple of simple two-cell maps (the smallest possible size K-Map). A map of this size can represent only one variable (not very useful in a practical application, but useful for demonstration). In the first of these two maps, we state that the value "A" exists in its asserted state. As such, there is nothing more that we can say about it. What we get out is exactly what we put in - - - in exactly the same form. It cannot be refined any further

    In the second map of figure 2 however, we state that both "A" and "A' " are present, and we put both into the map. In this case, we know from the axioms of table 1 (Boolean Postulates and Theorems) that A + A' = 1, the Postulate 5 case, so that the need for the "A" variable disappears (it is absorbed into the "1"). As result, no logic devices or enabling signals would be needed for this case, because the 'output' is always present. ("1" means all the time.)

    The solution of the K-Map generally works out in this way (mostly via application of Postulate 5). This is the most prevalent postulate operable in K-Maps, but not the only one. With it, for each two terms of the map that have all variables alike except for one, that pair of terms has an N + N' grouping, and thus the "N" variable drops out of that term. The task then is to arrange the cells within our map so that each symmetrical cell-group pair - - - can have one and only one variable that changes (this we will explain more completely later)

    An even more useful pair of examples are given in figure 2. In 2a) we mark in the values to represent (A'B + AB' ) (represented by ones in the map). Examination of that map shows that there is no symmetry across the axis between the B' and B Rows - - - - or, across the axis between the A' and A Columns. Because of this, neither a variable in "A", nor a variable in "B" will drop out (be reduced).

    On the other hand, (in figure 2b), where we initially defined the values (AB' + AB), there is a symmetry across the axis between the B' and the B rows, so that in this case, the B-variable will drop out (Postulate 5), leaving "A" as the minimized value.

    The important factor in the design of the Karnaugh map is the fact that the map is laid out so that, across any "axis" one and only one bit in the binary value of the term(s) represented within, may change. This means that one and only variable can change (from N to N' or vice versa) across that axis.

    KM
     

    Attached Files:

  4. Nov 19, 2005 #3
    2) Map Layout Choice

    2) Map Layout Choice

    Before discussing the actual operation of the Karnaugh Map, a few words are in order concerning the choice of directions for laying the map out. The first of these possible choices would be the use of a column-ordered map such as that shown in figure 3. In this arrangement, the lower-ordered variables (A, B, etc.) are arranged into the columns, with their characters placed vertically along the left (and maybe the right) of the map. The higher-ordered variables (such as D, E, etc.) are arranged into the rows, and are depicted horizontally across the top (and maybe the bottom) of the map.

    The second arrangement is into a row-ordered map like that of figure 4. In this arrangement, the lower-ordered variables (A, B, etc) are arranged into the rows, with their defining characters represented horizontally across the top (and maybe the bottom) of the map. The higher ordered variables (such as D, E, etc.) are arranged into the columns and their defining characters represented vertically along the left (and maybe the right) of the map.

    Many people use the column-ordered representation, possibly because that is the way Karnaugh laid his out. I prefer the row-ordered map, because that is the orientation I find most familiar in everyday life. This is the way we were taught from elementary school to orient almost everything. In reality, it probably makes little difference. The maps will usually be filled in, by-the-numbers, directly from truth tables, with little concern for orientation (we will demonstrate that later). Only when reading the maps will the layout usually come into play to any noticeable degree, and then the variables will be clearly delineated if the accompanying map forms are used.

    KM
     

    Attached Files:

  5. Nov 20, 2005 #4
    K-Map Numbering Method - Part 1

    K-Map Numbering Method - Part 1

    The position at which each possible minterm* is located within the K-Map corresponds directly to the number which is assigned to that cell in the map, thus the location of each cell of the map must be selected so as to assure that the following is true: - - - From any cell within the map, to its adjacent (vertically or horizontally) neighbor cell - - -one and only one bit in the cell numbering may change. This numbering sequence is accomplished as follows.

    Referring to figures 5 and 6, we build a Karnaugh Map in the following manner: First we start with a base, or root, cell. To this cell we assign the number "0". From here on, we add cells and assign their cell numbers by what may be likened to an 'unfolding' process. This process we can liken to that of continually producing a new group of cells exactly like the ones we already have, but positioned exactly on top of the one(s) we already have. Each cell of this new layer, then has the same value as the one directly beneath it, plus 2^M (where M is the number of the 'unfolding' operation, starting at "0"). Each 'unfolding' step, is then done from the boundary (axis) following the last presently existing cell in the map (horizontally or vertically).

    For a row-ordered K-Map, we first generate the cells of the first row as is illustrated in figure 5. The number of 'unfolding' operations will depend upon how wide to make the map. (In the illustration, we perform three 'unfolding' operations, in order to produce an eight-cell-wide map.) Starting with the "zero" cell, we generate a new cell on top of it, and give it the value "1" (0 + 2^0 = 1). Then we unfold this out - - around the 'axis' (figure 5.b) following the "0" value cell, and now have a two-cell-wide map. Next, we repeat the process, generating two new cells atop the ones we have, and give these new cells the values (0 + 2^1 = 2) and (1 + 2^1 = 3). Then when we unfold these out (figure 5.c), we have the map cells "0", "1", "3" and "2". Finally, when we perform the process again (this time adding 2^2), we end up with the cells "0", "1", "3", "2", "6", "7", "5" and "4" (figure 5.d).

    We then produce the remaining rows of our K-Map in the same manner, but by unfolding each new row around an axis beneath the row from which it is derived (figure 6). For example, row 2 is formed by generating it above row one, with each cell in row 2 having the same value as as the cell beneath it, plus 2^3 (figure 6.b). The same process is then repeated to generate the next pair of rows (figure 6.c)

    What we now have, is a map like that of figure 7. If we trace adjacent cells through the map, we now get a number arrangement which looks essentially like that of the standard 'Reflecting Gray Code" numbering sequence. In this sequence, every sequential number has one and only one bit different from its sequential neighbor (predecessor or following number). To be sure, our map doesn't necessarily come from the standard reflecting gray-code sequence, but is simply dirived in much the same way, thus we end up with the same pattern.

    What's more, all the cells of the map are arranged so that each has only a one-bit difference from its neighbor, vertically or horizontally (the vertical relationship, other than at the dnds of rows, would be of no concern with gray-codes). The way the map was generated assures this two-way relationship.


    KM

    [* If there are N binary variables, then there will be a total of 2^N possible Simple-Sum-of-Products (SSOP)combinations of these N-variables, where each of these 'terms' contains each variable, represented in either its normal or its complemented (not) form. Each or these 2^N possible terms is called a minterm. For example, if there are two variables A and B, then there are four possible minterms; A'B', AB', AB and A'B.]
     

    Attached Files:

  6. Nov 20, 2005 #5
    4. Karnaugh Map Numbering Method - - Part 2

    4. Karnaugh Map Numbering Method - - Part 2

    In figure 8, we have a binary representation of the cell numbering of the K-Map, A straight examination shows us that every cell within the map has a binary number value in it which is identical to that of each of its adjacent cells (above, below and to both sides), except for one bit (a different bit in each direction). One bit, when going from any cell to a neighbor is all that changes. Furthermore, going from any cell to one neighbor, the bit that changes is different from the bit that changes if going to another neighbor from that cell. Finally, we can see a pattern that occurrs along any row or column of cells, when going to the next adjacent row or column. The bit that changes, is the same for all cells along that row or column. In other words, across every "axis" between rows or columns, there is a particular bit that changes. The significance of this is the fact that, along any axis, there is a N-N' variable pair combination, which is the only variable that changes when crossing that axis - - - thus every cell pair across that axis allows the elimination of that particular variable.

    The reason for this can be seen from the way that the cells and groups of cells were "unfolded", to create our numbered cell groups, both horizontally and then vertically. This created the distinct axes, each of which is identified by - - - the bit that changes as that axis is crossed when going to adjacent cells. [What is not yet readily apparent, is the fact that (for maps of more than four variables) a one-bit change occurs not only for adjacent cell rows/columns, but also for all that are symmetrically located across each of these axes. This we shall discuss later.]

    If we thus examine figure 9, we see (in the example of a four-variable case) which bit changes as each axis is crossed. For numerical convenience, "A" represents the rightmost bit, "B" the next to rightmost bit, and so on. Finally, figure 10 depicts several possible configurations of K-Maps, set up and numbered according to the rules which we have established. By substituting the binary values for each of the cell number values (shown in decimal) we can readily verify the bit-changes across each axis.

    There is more to come - - - KM
     

    Attached Files:

  7. Nov 21, 2005 #6
    5. The Mahoney Map

    5. The Mahoney Map​


    In the early 1960s, Matthew Mahoney more precisely defined the basic mechanism through which the logic-map operates. Using this principle (which we have already laid out) he defined and laid out what came to be called the "Mahoney-Map". Essentially, the Mahoney Map is a variation of the Karnaugh Map, and the principles will apply equally in both cases.

    Two examples explaining the workings of the Mahoney Map are shown in figures 11 and 12. The basic difference of the Mahoney Map from the Karnaugh Map is the fact that, where the K-Map can be laid out in either a "column-ordered" or a "row-ordered" manner (as we described in insertion number 2), the M-Map is laid-out in an alternating Row-Column manner - - - and can be numbered using a series of repeatingly reversing "Z" patterns. Explanation of the Mahoney Map is as follows:

    The same reason that underlies Karnaugh Maps also applies to Mahoney Maps. This is illustrated in figure 11. There (in figure 11-a) we start out with one cell ("0") and expand from there by symbolically rotating that cell about the axis to the right, and adding "1" (2^0) to the original value (0), and putting the sum (0 + 1 = 1) into the new cell. Next we rotate two cells we now have downward, and add "2" (2^1) to each of the newly created cell values (0 + 2 = 2) and (1 + 2) = 3. Next (in figure 11-b), we rotate what we now have, to the right, and add "4" to each cell value to get (0 + 4 = 4), (1 + 4 = 5), (2 + 4 = 6) and (3 + 4 = 7). Then we rotate our new 8-cell group downward (again), and this time add "8" to each and get, values 8 through 15 (also in figure 11-b). Next (in figure 11-c), we rotate our cells right again, and add 16 to each. Finally here, (in figure 11-d), we rotate our cells downward again, and add 32 to each. This process, we can see, accomplishes the same thing as with the Karnaugh Map, except with alternating rotations to the right and then down.

    There was also a method defined for drawing the M-Map, which is easy to remember. This consists of drawing in consecutive numbers starting at "0", and going through continually repeating and reversing "Z" patterns (as shown in figure 12). Observing figure 12-a, we see how the numbering of M-Map cells means putting in the consecutive numbers in reversing "Z" patterns. Cells "0" through "3" form a standard "Z", numbers 4 through 7 go in with a reverse "Z" pattern, numbers 8 through 11 go in with an inverted "Z" pattern, and numbers 12 through 15 go in with a reverse-inverted "Z" pattern. Also, as shown in figure 12-b, Those four, four bit entries also form a (larger) "Z" pattern. There are four of these larger "Z" patterns, which each also derive from four of the smaller patterns. The second of these larger patterns is also reversed, the third is inverted, and the fourth is reversed and inverted. Then finally, the four larger Z-patterns are themselves put in in a Z-pattern. Basically the K-Map and the M-Map configurations offer the same capabilities, and are used in the same manner. Comparative advantages of the two types are as follows:

    Mahoney Map Advantages:
    A) This map is easier to draw-up, especially in the larger sizes. It is necessary only to put in sequential decimal values into a set of continually reversing "Z" patterns. The actual (reflecting gray-code-like) sequence that is being generated is hidden in the mechanics of the construction process.

    B) Maps of different sizes always have the same cell-numbers all located in the same places.

    Karnaugh Map Advantages:
    A) This map is more familiar to more people, and thus more communicatable.

    B) The Variables in this mapping arrangement remain in order, rather than alternating - - making them somewhat easier to follow.

    Discussion from here on, will be limited to the case of the Karnaugh Map.

    KM
     

    Attached Files:

  8. Nov 22, 2005 #7
    7. Karnaugh Map Annotation Choices

    7. Karnaugh Map Annotation Choices​

    In passing, we look at the various methods used for annotating the Karnaugh Map, not attempting to suggest or endorse any, but to indicate some things that have been used, and that might be used at various times in this string (sometimes because of the constraints imposed by the software being used here (MS Word, etc.).

    First, brief mention is made of the ways used to indicate occurrence of a minterm* within the map. Figure 15 shows some of these. The top view, illustrates use of the value "1", indicating "presence" or "yes". This is the most commonly used indicator, though other marks, such as "X"or several other characters have also been used. The last entry, the "slash" was recommended by Mahoney for his map configuration. In this series of string insertions, the "1" shall be used (at least in most cases).

    Figure 16 shows ways of grouping the cells (minterms) for minimization purposes. (The bottom style was recommended and used by Mahoney.) It should be noted that none is absolutely ideal in the case of complex maps of greater than four variables, because of the need which sometimes arises in those cases, to link non-adjacent cells.

    * See insertion number 3.

    Will try to get #6 Tomorrow, after some drawing erors are corrected. - - - KM.
     

    Attached Files:

  9. Nov 23, 2005 #8
    6. Closed Map Structure

    6. Closed Map Structure​

    The one point to be emphasized in this insertion, is the fact that the Karnaugh Map is a closed entity - - - thus it has no outside boundaries. Karnaugh himself described it as being like a torus, such as that shown in figure 14 (in this case, a six-variable map is shown).

    Figure 13 is of a four-variable map showing the relationships across what appear to be the outside boundary axes (but since the map is 'closed' these axes are not outside boundaries). The first assertion we make here, is that the (so called) top axis of the K-Map, and the (so-called) bottom axis are not two separate axes, but are the same axis, coming, in this case, between the C'D row and the C'D' row. Arrows show the transition across this axis, Just as is the case across all other axes, one bit value in the representation changes (in this case, the "D" bit representation). Similarly, there is only one vertical axis between the A'B and the A'B' columns, and it is characterized in the same way, verifying that this is a completely closed structure.

    KM
     

    Attached Files:

  10. Nov 23, 2005 #9
    8. The Karnaugh Map is An SSOP Tool

    8. The Karnaugh Map is An SSOP Tool​


    The Karnaugh Map was designed to take a known sum (OR'ing) of conditions, each of which is given as a minterm of the variable set (for example, A, B, etc.) being evaluated - - - which is a SSOP (Simple Sum of Products) function - - - and to minimize this function, in order to produce another SSOP function which will use the fewest number of gates.

    To illustrate what is meant here, we can refer to the example in figure 17, in which we have the four variables (A, B, C, D). We are initially given the conditions; which in this case, consist of Eight minterms (of a possible sixteen). This can be expressed as the SSOP function:

    f = A'B'C'D' + AB'C'D' + A'BC'D' + A'B'CD' + AB'CD' + A'BCD' + A'B'CD + AB'CD

    This function is solved in the K-Map, by assigning each of the minterms to its respective cell - - - to derive the minimized version of the function:

    f = A'D' + B'C + B'D'

    - - which is also a SSOP form. Finally, shown in figure 17, are two gate combinations that can be employed to generate this function. (a NAND - NAND pairing is equivalent to AND - OR.)

    NOTE: It can also be pointed out here, that whereas the K-Map is designed to readily work with SSOP functions, it can with a little manipulation, also yield SPOS (Simple Product of Sums) results, such as that of figure 18. (P.S: Here instead of AND - OR, we could have used NOR - NOR)

    Next: The dynamics of minimization. - - - KM
     

    Attached Files:

  11. Nov 26, 2005 #10
    9. Dynamics of The Minimization Process

    9. Dynamics of The Minimization Process​


    The example shown here is not a practical application, nor is the method of solving the example the usual approach (there are too many minute steps taken), however it is intended to illustrate what takes place inside the map minimiation process.

    In this case, we select every cell within the map to be 'marked'; in other words, all the minterms are present. This is shown in figure 19-a, in which every cell has a "1". We have additionally illustrated the values of the minterms represented within each cell.

    In figure 19-a, we can see that each cell in the first column has a value identical to its adjacent neighbor in the second column, except for the value of the "A" variable. As an example, the values in cells "0" and "1" are A'B'C'D' and AB'C'D' respectively, thus when we observe these two cells grouped together (OR'ed) we get:
    A'B'C'D' + AB'C'D' = B'C'D'(A' + A)
    = B'C'D' (1)
    = B'C'D' - - - - thus, we have eliminated the "A", and get cells "0" and "1" to contain what is in figure 19-b.
    The same is the case for the remaining cell pairs between columns "1" and "2", and also those between columns "3" and "4". What we get then is that shown in figure 19-b.

    In like manner, in figure 19-b, each cell-pair in combined columns "1" and "2" , has values that are the same as those in combined columns "3" and "4", except for the value of the "B" variable, thus if we combine (for example) the values of cells "0/1" and the values of cells "2/3" (by OR'ing them), we get
    B'C'D' + BC'D' = C'D'(B' + B) = C'D'
    - - - thus we have now eliminated the "B" - - - in the first row - - - and can do likewise for the other three rows.

    What we have left, is the groupings shown in "C". Now we notice that the valus of the term in row "1" is the same as that in row "2", except for "C", and we thus have:
    C'D' + CD' = D'(C' + C) = D'(1) = D'
    The same is the case between rows "3" and "4", and we thus have:
    C'D + CD = D(C' + C) = D

    Finally, in figure 19-d, - - - if we combine (by OR'ing) the two remaining cell groupings, we get:
    D' + D = 1
    This simply implies that the "output signal" is "1" meaning that it is always present - - - and requires no logic to enable it.

    This example, in a practical sense, is basically useless in the "real world", but it is also informative. It shows what takes place during the map minimization process.

    KM
     

    Attached Files:

  12. Nov 26, 2005 #11
    10. A Few Simple Rules

    10. A Few Simple Rules

    Now we are ready to jump into the map minimization process in earnest, but before doing so there are a few rules that should prove helpful. Most of these rules concern the process for gathering the minterms ((marked cells) together into groups, and do not concern the form used to delineate these groups. (In this series, choice is made to "circle" the selected groups of cells.

    Map Cell Entry Rules:
    Rule 1: Each minterm (term containing all variables, in either the asserted or the negated state) going into a map will occupy one (and only one) cell.
    Rule 2: If a term has fewer than the maximum variables, expand it to form minterms, by adding all missing variables. Do this by inserting in place of the original term, two new terms, one with the added variable in its negated state and one with the added variable in its asserted state. If one variable is thus added, two new terms will be formed; if two are added, four new terms are formed; if three are added, eight new terms are formed; etc.

    Map Grouping Rules (Cell Grouping):
    Rule 3: Maps have no "boundaries". They are closed.
    Rule 4: Each cell grouping (circling, etc.) must contain exactly 2^N cells, where N = 1, 2, 3, etc.
    Rule 5: If 2 cells are grouped, one variable will be eliminated.
    Rule 6: If 4 cells are grouped, two variables will be eliminated.
    Rule 7: If 8 cells are grouped, three variables will be eliminated.
    Rule 8: If 16 cells are grouped, four variables will be eliminated.
    Rule 9: Any valid group of cells must be rectangular (and in a map of four or fewer variables, they must be contiguous).
    Rule 10: Any Cell grouping must be symmetrical across each of its dividing axes.
    Rule 11: Make each cell grouping being formed, as large as possible.
    Rule 12: The overlapping of cell groups is perfectly acceptable.
    Rule 13: Leave no marked cell behind(when finishing with groupings).
    Rule 14: Include no unmarked cells within a grouping (except possibly "don't care" cells).
    Rule 15: Avoid including "redundant" groupings.

    Hints:
    Rule 16: There may be multiple solutions that are correct.
    Rule 17: Any correct answer will include the the smallest number of terms, and the lowest variable-per-term count, and will include all of the available minterms.

    Map Solving Rules: Finally, when reading out the term value for grouping that has been constructed (circled, etc.) on the map, there are these additional rules.
    Rule 18: There must be a product term (in the SSOP solution) for each grouping that has been formed.
    Rule 19: If a grouping intersects a variable (N) in both, its negated and its asserted states (N' and N), drop that variable from the term being formed.
    Rule 20: If a grouping intersects a variable (N) in only its negated state (N') include it in the term in its negated state. Likewise, if the grouping intersects that variable in only its asserted state, include it in its asserted state.
    Rule 21: Check to verify that rules 5 through 8 have been complied with.

    We are now ready to start!

    KM

    P.S. Some additional Truth Tables are also included to make it easier to work with eight variable Karnaugh Maps. One of these will be submitted soon.
     

    Attached Files:

  13. Nov 27, 2005 #12
    11. Filling and Grouping - - Examples

    11. Filling and Grouping - - Examples

    In this insertion, we solve a few maps to illustrate the straightforward application of the rules. First, we look at the example listed in insertion #8.

    f = A"B"C"D" + AB'C'D' + A'BC'D' + A'B'CD' + AB'CD' + A'BCD' + A'B'CD + AB'CD

    This has eight terms, all of which are minterms, so these can be entered directly into the map. This is accomplished by putting each minterm into the map cell who's position intersects the corresponding variable states. Thus, the first term in "f" goes into the first cell (# 0), the one which intersects the variables A', B', C' and D' (See rule # 1). The rest are entered in the same way, as shown on figure 20-a.

    We then look for cells to collect into a group, while obeying all pertinent rules concerning grouping. By encircling cells numbered "0", "1", "4" and "5", we create a grouping that complies with all rules that are relevant (rules numbered 3, 4, 9, 10, 11 and 14), as is seen in figure 20-a. We then form three more groupings which also corellate to those rules(also shown in figure 20-a). Taken together these groupings also corellate to rules 12, 13 and 15, indicating that the groupings are valid.

    When we then evaluate the groupings for the purpose of minimization, we see that each grouping contains four cells, meaning that two variables will be eliminated from each of them. Taking that first grouping (cells 0, 1, 4 and 5), we see that it symmetrically straddles the axis between "A " and "A' ", and the axis between "C' " and "C' ", so that by rule 19, these two variables are eliminated. On the other hand, this grouping intersects "D' ", but does not intersect "D", so that according to rule 20, "D' " is included in this term; and for similar reason, "B' " is included, (Rule 6 is verified) - - - yielding term "B'D' ". Then, similar examination of the other two groupings, gets us the terms "A'D' " and "B'C ", so that we end up with:

    f = A'D' + B'C + A'D

    Using the same processes, if we start with the following function:

    f = ABC' + A'BC' + A'B'C + AB'C + ABC

    - - we can put it into a map and group terms as is shown in figure 20-b, using much the same processes as were used in the last example. Note, that this example has only three variables, so that only the top half of a map is used. Solving this map, we get:

    f = AB + BC' + B'C

    Note, then that from figure 20-c, we can solve the same function, and get:

    f = AC + BC' + B'C

    - - - and this verifies rule 16.

    Next, in figure 20-d, we start with a function that has Eight four-variable terms, and end with two two-variable terms:

    f = A'B + AC'

    This function is minimized in the same way as before.

    Finally, if we are given the following function:

    f = AC'D' + B'CD' + BCD' + A'CD + ABD + AB'C'D' + AB'C'D

    We immediately see that this is a four-variable function, and that also five of its six terms must be expanded to get a function containing minterms only. When we do so, we get:

    f = AB'C'D' + ABC'D' + A'B'CD' + AB'CD' + A'BCD' + ABCD' + A'B'CD + A'BCD + ABC'D + ABCD + AB'C'D

    This function is shown entered into each of the maps of figure 21. Comparison of "a", "b", and "c" of figure 21, shows three different, but all correct, groupings for this map, all leading to different but corresponding solutions. These are:

    f = AD' + AC' + AB + A'C (figure 21-a)
    f = AC' + BC + CD' + A'C (figure 21-b)
    f = AD' + BC + AC' + A'C figure 21-c)

    The last (figure 21-d) is incorrect because it does not adhere to rule 13.

    KM
     

    Attached Files:

  14. Nov 28, 2005 #13
    12. What Is Wrong - - - If Anything?

    12. What Is Wrong - - - If Anything?​

    In this insertion, we study the rules given before - - with a few examples. Some, if not all of these in figure 22, are examples of mistakes in the use of the rules.

    The example in figure 22-a, is incorrect, because, as shown, the two top circled areas are taken together, and as such violate rule 10. These two are not symmetrical across either the axis between B'-B, or the axis between A-A', and thus cannot be taken together . (In addition, in standard maps of four variables or fewer, all cells "circled" must be adjacent to each other.) In the future, for maps larger than four variables, we'll use different colors to show different groupings, for sake of clarity. The resultant function would be: f = AB'D' + A'B + A'D.

    The example in figure 22-b, is incorrect. It violates both rule 10, and rule 4. The correct grouping must consist of two groupings, one including the the four leftmost marked cells, - - and the other, an overlapping grouping including the four rightmost cells. The resultant function would be: f = AC + BC.

    The example in figure 22-c, is incorrect. It violates rule 14. A correct grouping would have three groups, one circling the top four cells, one circling the top two and the bottom two and one circling the entire left column. The resultant function would be: f = A'B' + B'C' + B'D'.

    The example in figure 22-d, is incorrect. It ignores rule 3. If that rule had been followed it would be recognized that all four cells form an adjacent and symmetrical grouping. The resultant function would be: f = A'C'.

    The example in figure 22-e, is incorrect. The vertical grouping shown violated rule 10 and rule 4. The correct grouping would have two groups. These would have; one group containing the top two marked cells and one group containing the bottom two marked cells. The resultant function would be: f = ACD' + AB'D.

    The example in figure 22-f, is incorrect. It violates rule 15. There should be only four groupings (and thus four terms). One correct grouping would have; one group containing the two cells in the left (A'B') column, one group containing the two cells in the next-to-left (AB') column, one group containing the two cells in the next-to-right (AB) column and one group containing the two cells in the right (AB') column. The resultant function would be: f = A'B'C' + AB'D' + ABC + A'BD.


    The example in figure 22-g, is correct.

    The example in figure 22-h, is incorrect. It violates rule 11 and ignores rule 12. The circle enclosing the AB'CD' cell should also contain the top two cells of the first column and the top cell of column two. The resultant function would be: f = A'B' + C'D' + B'D'.

    The example in figure 22-j, is correct. This example illustrates the correct observation of rule 3 that was missed in example 22-d.

    KM
     

    Attached Files:

  15. Nov 30, 2005 #14
    13. More Grouping Examples

    13. More Grouping Examples​


    Following are four examples of the minterm entry, grouping for minimization and reading process:

    1) Given the following function:
    f = ACD' + BC'D' + ABC'D + A'BC'D + A'B'CD'
    - - we expand this to get the following minterms:
    f = ABCD' + AB'CD' + ABC'D' + A'BC'D' + ABC'D + A'BC'D + A'B'CD'
    we put these into the map to get what is in figure 23-a, and this is grouped and read out to get:
    f = BC' + B'CD' + ABD'
    Note, that this is not the only possible solution function.

    2) Given the following function:
    f = A'BC'D' + ABCD' + AB'CD + A'B'C'D
    - - we see that, since each of these already has four variables, they are all already in minterm form, so they are entered directly into a map, as shown in figure 23-b. Upon examining this map, we can also say that no grouping can be done, so that this function is already the most reduced form possible.
    f = A'BC'D' + ABCD' + AB'CD + A'B'C'D

    3) Given the following function:
    f = A'B'C'D' + AB'C'D' + ABC'D' + AB'C'D + ABC'D + A'BC'D
    - - we see that, since each of these already has four variables, they are all already in minterm form, so they are entered directly into a map, as shown in figure 23-c, and this is grouped and read out to get:
    f = AC' + B'C'D' + BC'D

    4) Given the following function:
    f = A'B'CD' + A'B'CD + ABCD' + ABCD
    we see that, since each of these already has four variables, they are all already in minterm form, so they are entered directly into a map, as shown in figure 23-d, and this is grouped and read out to get:
    f = A'B'C + ABC

    KM
     

    Attached Files:

  16. Nov 30, 2005 #15
    14. The "Don't Care Condition

    14. The "Don't Care Condition​


    Often, when we are designing new functions, the input signals, are constrained as to what combination of states will be received. As an example, there could be a system with four machines configured so that no more than two could be running at a time, and our logic could produce its output depending upon which of these is operating or off. Right off, there are certain constraints - - - conditions we don't have to deal with. We could show these conditions with a truth table, representing the machine state outputs by "A", "B", "C" and "D", as follows:

    Machine output - - - - D - - C - - B - - A
    - - - - - - - - - - - - - - - -0 - - 0 - - 0 - - - 0
    - - - - - - - - - - - - - - - -0 - - 0 - - 0 - - - 1
    - - - - - - - - - - - - - - - -0 - - 0 - - 1 - - - 0
    - - - - - - - - - - - - - - - -0 - - 0 - - 1 - - - 1
    - - - - - - - - - - - - - - - -0 - - 1 - - 0 - - - 0
    - - - - - - - - - - - - - - - -0 - - 1 - - 0 - - - 1
    - - - - - - - - - - - - - - - -0 - - 1 - - 1 - - - 0
    - - - - - - - - - - - - - - - -0 - - 1 - - 1 - - - 1 - - - - - Not allowed
    - - - - - - - - - - - - - - - -1 - - 0 - - 0 - - - 0
    - - - - - - - - - - - - - - - -1 - - 0 - - 0 - - - 1
    - - - - - - - - - - - - - - - -1 - - 0 - - 1 - - - 0
    - - - - - - - - - - - - - - - -1 - - 0 - - 1 - - - 1 - - - - - Not allowed
    - - - - - - - - - - - - - - - -1 - - 1 - - 0 - - - 0
    - - - - - - - - - - - - - - - -1 - - 1 - - 0 - - - 1 - - - - - Not allowed
    - - - - - - - - - - - - - - - -1 - - 1 - - 1 - - - 0 - - - - - Not allowed
    - - - - - - - - - - - - - - - -1 - - 1 - - 1 - - - 1 - - - - - Not allowed

    As we can see, there are five combinations of states (0n-off) of the four machines that we will not see, because they are already constrained so as to not operate in those combinations. Because of that, we can more-or-less ignore those states, or even better, handle those states to our own advantage, in our designs. In other words, we can treat them in our designs, to contribute to our logic either as an "occurrence" or as a "non-occurrence", because we'll never have to deal with them. In other words, we can treat them as either "ones" or "zeros" on our map.

    These constrained states we call "don't care" states, and as convention, we can represent them as the letter "N" on our maps. Then when grouping our terms, we can choose to either 'include' or to 'not-include' each of them, depending upon which is advantageous to our design - - whichever makes the design simpler.

    One word of caution should be voiced here. Whichever way we choose to configure our design, that is how our logic will behave overall - - - so if the "not allowed" should occur, our logic will then define how our circuit behaves. In the real world we should check for contingencies, and determine what would happen if the 'unthinkable' should occur. Usually this won't be a consideration in our design, simply because, in such a case, things will already have gone wrong, and our curcuit won't generally make it any more wrong - - - but we should still check after designing, to make sure. Some sort of recovery might be in order (like with clocks when the power blinks out), but this is usually included in our 'start-up' circuit.

    The 'don't care' condition is a powerful design tool, which should prove helpful in many occasions.

    KM

    P.S: With this insertion I have included an eight-variable map, for general use.
     

    Attached Files:

  17. Dec 1, 2005 #16
    15. "Don't Care" Examples

    15. "Don't Care" Examples​

    The following examples, shown in figure 24, use the same four functions as were used in insertion 13, however in this case, certain minterm positions are also assumed to represent "don't care" cases.

    1) We were given the following function:
    f = ACD' + BC'D' + ABC'D + A'BC'D + A'B'CD'
    - - and we expand this to get the following minterms:
    f = ABCD' + AB'CD' + ABC'D' + A'BC'D' + ABC'D + A'BC'D + A'B'CD'
    We are also given the following "don't care" cases:
    N = A'BCD' + A'BCD + ABCD
    The expanded function minterms are entered into the map. Also, the "don't care" cases are already in minterm form, so these are entered directly into the map. What we get is shown in figure 24-a. In this case, we choose to treat all the "don't care" minterms as function minterms, because they greatly simplify the solution. What we then get is:
    f(N) = B + CD'

    2) We were given the following function:
    f = A'BC'D' + ABCD' + AB'CD + A'B'C'D
    - - and since as we saw before, each of these already has four variables, they are all already in minterm form, so they are entered directly into a map. No grouping can be done, so that this function is already the most reduced form possible, unless "don't care" terms are available.
    f = A'BC'D' + ABCD' + AB'CD + A'B'C'D
    We are also given the following "don't care" cases:
    N = A'B'C'D' + AB'CD' + ABCD + A'BC'D
    These are also already in minterm form, and so are also entered directly into the map, and what we get is the map shown in figure 24-b. Now, we can group terms and reduce the resultant function, as shown in the figure, and we get:
    f(N) = A'C' + AC

    3) We were given the following function:
    f = A'B'C'D' + AB'C'D' + ABC'D' + AB'C'D + ABC'D + A'BC'D
    - - and since each term here already has four variables, they are all already in minterm form, so they are entered directly into a map. We are also given the following "don't care" conditions:
    N = A'BC'D' + ABCD' + AB'CD + A'B'C'D
    These are entered into the map along with the function terms, and we get what is shown in figure 24-c. Now, we can group terms and reduce the resultant function, as shown in the figure, and we get:
    f(N) = C'
    Note that, in this case, we chose to use some of the "don't care" terms and to not use others. That is totally our discretion.

    4) We were given the following function:
    f = A'B'CD' + A'B'CD + ABCD' + ABCD
    and these were already in minterm form, and so were entered directly into the map, as was previously shown in figure 23-d. We were also given the following "don't care" terms:
    N = AB'
    - - which, when expanded gives us the following minterms:
    N = AB'C'D' + AB'C'D + AB'CD' + AB'CD
    These terms, when entered into the map along with the function terms, gives us the discretion to form the groupings shown in figure 24-d. From this grouping, we get the following:
    f(N) = B'C + AC

    Hopefully, these examples help to illustrate how the "don't care" can be used to help simplify the logic design operation. It must be remembered, however that by taking advantage of these constraints, we are actually designing a circuit that operate as planned only if the constraints are not violated. (This is a generally safe assumption, because whatever will violate the constraints would also cause problems in any case. It is still prudent to check for contingency situations after the circuit is designed.)

    KM
     

    Attached Files:

  18. Dec 2, 2005 #17
    16. Maps Larger Than Four-Variables - - - Part 1

    16. Maps Larger Than Four-Variables - - - Part 1​


    The rules concerning Karnaugh Maps, which we have already discussed, apply to maps larger than four-variables just as they do the smaller ones. The only noticeable difference in handling is the fact that groupings that are combined in the larger maps can now be non-contiguous (as long as they continue to obey the symmetry rule [rule 10]). To make it a bit more methodical, we establish something of a protocol for solving maps of greater than four variables:

    1) Start each grouping at its smallest size at first, and build it up (mentally), via a "coupling" process.
    2) When coupling two cell groups, every cell within one group must couple to a symmetrically situated cell in the other group.
    3) When coupling four or more rows or columns (must be a power of two), start by coupling the two "innermost", then the two "next-to-innermost", etc., until the "two outermost are coupled - - - or at least one pair cannot be coupled.
    4) Remember that, because of the "unfolding" way our maps are built, any two adjacent cells will couple. Also, remember that any two cells that are "symmetrical" will couple. The same holds for "groupings", thus any two adjacent or "symmetrical" groupings of the same size will couple, to form the next larger grouping.
    5) Each time a larger grouping is formed, by coupling, one variable is eliminated.
    6) Remember that, groupings must contain exactly 2^n cells, so that by starting with the smallest size and building the grouping up via coupling, this rule is maintained.

    We can use this protocol for building up a grouping, with the filled-in maps of figure 25-a as an illustration. Starting with cells [9,11,25,27], we see that "9" and "11" can be coupled (and eliminate variable "B",as the arrows below the group indicate). The same is the case for "25" and "27". Next we can take the two groupings we have just formed, couple them, and eliminate variable "E".

    Then we can do the same thing with cells [15,13,31,29] again eliminating "B" and "E". Next, we notice that the two 4-cell groupings that we have formed are themselves symmetrical about the axis from "C' " to "C", so that these two groupings can now be coupled (and eliminate "C").

    Then we can do the same things with cells [57,59,41,43] and cells 63,61,47,45], again eliminating "B" and "E" (two more times), and then couple these two groupings (again, eliminating "C"). Finally we see that the upper grouping and the lower grouping that we have just formed, are themselves symmetrical about the axis from "F' " to "F", so that these can be coupled (eliminating "F"), and we end up with a 16-cell grouping, which has four variables eliminated from it, leaving [f = AD].

    In the second illustration of figure 25 (25-b), we can first form the couplings to eliminate "A", then couple each of these horizontally, to eliminate "C". Next, we can couple each of these 4-cell groupings vertically to its adjacent grouping, to eliminate "D", and get two 8-cell groupings. Finally, we couple these two 8-cell groupings, eliminating "F", and end up with a 16-cell grouping. What we then get is [f = BE].

    In figure 26, we can follow the same procedure to get [f = C'D'] and [f = AB]. We leave it as a practice exercise to do the same for figure 27.

    This is all a straightforward operation, except for one thing - - - how do we determine whether two cells or two cell groups are symmetrical in these larger maps?


    KM
     

    Attached Files:

  19. Dec 3, 2005 #18
    17. Maps Larger Than Four-Variables - - - Part 2

    17. Maps Larger Than Four-Variables - - - Part 2​


    The main problem with larger maps is - - - determining what is symmetrical? With four-variable maps, all we have to know about any two cells is - - - if they are adjacent they are symmetrical, and if they are symmetrical they are adjacent. With larger maps, it's not quite that simple. Obviously, any two adjacent cells are still symmetrical, but now, cells can be non-adjacent and also be symmetrical. On the other hand a lot of non-adjacent cells are not symmetrical to each other.

    To answer this question in the simplest, most straightforward way, figure 28 is included. This figure defines which cells across any horizontal row are "symmetrical" to which other cells along that row. The first illustration (figure 28-a) shows us the obvious, that all cells are symmetrical to their immediate neighbors. Figure 28-b shows us which cell pairs (other than the adjacent ones) are symmetrical within each half - - the left or the right - - of the map. In this case, there are two possible symmetrical couplings (four, if the two adjacent ones in the middle of each half are counted, but these have already been considered as being adjacent). Finally, figure 28-c shows us which cells are symmetrical between the two horizontal halves of the map (again, the adjacent coupling possibilities have been omitted). We can verify these non-adjacent symmetries via either of two methods: 1) study of the "unfolding" process through which the map was formed, or 2) observation of the binary value of the cell numbers, and that only one bit is different between any two symmetrical cells. The same coupling considerations are true vertically.

    In figures 29 and 30, we have four cases, in which we shall determine whether 16-cell groupings can be made . In figure 29-a, there are two groupings of eight cells each, with both arranged vertically in columns. Obviously, each column can itself be grouped, since all cells within each column are symmetrical to that column's other cells (because they are all adjacent). The two columns themselves, however are not symmetrical, and thus cannot be combined to form a 16-cell grouping.

    In figure 29-b, we cannot create full groupings either vertically or horizontally. Taking the top row, the reason for this horizontally can be ascertained in two ways: 1) The first two cell minterms will couple, as will the last two, but then the remaining two terms will not couple, because they have different variable sets. 2) The simplest way to state it, however is - - that where the cells [19,18] will couple because they are symmetrical, the other cell pair [17,22] will not couple with the first pair because the two pairs are not symmetrical. The same problem exists vertically.

    In figure 30-a, there are two 8-cell groupings, but these will not couple because neither the inside columns, nor the outside columns are symmetrical with each other.

    In figure 30-b, the cell groupings will not couple either verticlly nor horizontally. In both of these cases, the reason is the same that it was in the figure 29-c case.

    KM

    P.S: In the maps that have been supplied, the "axes" for any given variable have been 'color matched' to the header block area for that variable. Thus the "axes" between [A'-A] or [D'-D] are black. Likewise, the "axes" between [B'-B] or [E'-E] are blue. Likewise, the "axes" between [C'-C] or [F'-F] are red. This is done to make it a bit easier to determine which variable is being eliminated by a coupling.
     

    Attached Files:

  20. Dec 4, 2005 #19
    18. Maps Larger Than Four Variables - - Part 3

    18. Maps Larger Than Four Variables - - Part 3 - - Recognizing The Patterns​


    In the previous two insertions, we have tried to show where and why symmetries exist. Ths simplest and most atraightforward consideration, however is to simply remember the various patterns of symmetry. To do this, figure 31 is included, which shows the predominant cases.

    Full-column symmetry corresponding to that of figure 28-c is given in figure 31-a. In each of these cases, 32-cell symmetries are shown. Obvious subsets of these would be symmetrical (2^N) partial rows or partial columns.. Thus, for example, from figure 31-a, we could have just the first two rows, or the second and third - along with the sixth and seventh rows, or maybe the middle four rows. (Where there are symmetries, the intersection of these symmetries are also valid.) Similar, full row symmetry is shown in figure 31-b.

    Full-row symmetry corresponding to that of figure 28-b is given in figure 31-c. The same variations hold as in the paragraph above. Similarly, for that shown in figure 31-d.

    A couple of the many adjacent-cell symmetries, as laid out in figure 28-a, are shown in figures 31-e and 31-f. Finally, it is pointed out again that any intersection of these symmetries is valid. Thus, for example we could intersect the symmetries of figure 31-a with those of figure 31-d, and get a pattern of cells [1,3,7,5,17,19,23,21,49,51,55,53,33,35,39,37]. The trick here is to see all of the myriad possibilities.
    (One possibility here is to make a set of transparent overlays.)

    A few example cases are shown in figure 35. Fir each of the four cases, which, if any of these groups can be combined to form a 16-bit cell group?

    KM
     

    Attached Files:

  21. Dec 4, 2005 #20
    19. The Eight-Variable Map

    The number of variables in a symmetrical, reflecting K-Map, is limited only by the size that a person is willing to draw, and the complexity of the patterns that one is willing to delve into. We have included in this series, an eight-variable map, so a few words are given here.

    Figure 32 shows three (of the four) types of symmetry pattern that might exist with the eight-variable map (adjacent cell symmetries are not shown - - these should be obvious). In general for every two variables added to the map, another two levels of symmetries are also included, one for vertical and one for horizontal.

    Figures 33 and 34 show just a few of the symmetry patterns possible from the types revealed in figure 32.

    KM

    Answer to the question of insertion 18: Only "d" is combinable to form a 16-cell group.
     

    Attached Files:

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Karnaugh Maps
  1. Mappings and inverses (Replies: 2)

  2. Linear Mapping (Replies: 4)

  3. Karnaugh maps? (Replies: 1)

  4. Range mapping (Replies: 3)

  5. Conformal mapping (Replies: 2)

Loading...