Karnaugh map and combined and compared with K W H meter
karnaugh map is a method for solving problem problems in digital combination circuits and sequential circuits in digital, when digital concepts are applied in a series of electronics it is necessary to simplify the simplification of the concept of the whole circuit especially in consideration:
1. efficient use of components
2. ease in soldering component
3. the fewer components are used but the output of the circuit is the same
4. Performance tool more flexible
5. make it easy in trouble shooting circuit
6. More easily damped oscillation system
7. Comparison of output and input more can be defined
XXX . XXX Karnaugh Maps, Truth Tables, and Boolean Expressions
Maurice Karnaugh, a telecommunications engineer, developed the Karnaugh map at Bell Labs in 1953 while designing digital logic based telephone switching circuits.
Now that we have developed the Karnaugh map with the aid of Venn diagrams, let’s put it to use. Karnaugh maps reduce logic functions more quickly and easily compared to Boolean algebra. By reduce we mean simplify, reducing the number of gates and inputs. We like to simplify logic to a lowest cost form to save costs by elimination of components. We define lowest cost as being the lowest number of gates with the lowest number of inputs per gate.
Given a choice, most students do logic simplification with Karnaugh maps rather than Boolean algebra once they learn this tool.
We show five individual items above, which are just different ways of representing the same thing: an arbitrary 2-input digital logic function. First is relay ladder logic, then logic gates, a truth table, a Karnaugh map, and a Boolean equation. The point is that any of these are equivalent. Two inputs A and B can take on values of either 0 or 1, high or low, open or closed, True or False, as the case may be. There are 22 = 4 combinations of inputs producing an output. This is applicable to all five examples.
These four outputs may be observed on a lamp in the relay ladder logic, on a logic probe on the gate diagram. These outputs may be recorded in the truth table, or in the Karnaugh map. Look at the Karnaugh map as being a rearranged truth table. The Output of the Boolean equation may be computed by the laws of Boolean algebra and transfered to the truth table or Karnaugh map. Which of the five equivalent logic descriptions should we use? The one which is most useful for the task to be accomplished.
The outputs of a truth table correspond on a one-to-one basis to Karnaugh map entries. Starting at the top of the truth table, the A=0, B=0 inputs produce an output α. Note that this same output α is found in the Karnaugh map at the A=0, B=0 cell address, upper left corner of K-map where the A=0 row and B=0 column intersect. The other truth table outputs β, χ, δ from inputs AB=01, 10, 11 are found at corresponding K-map locations.
Below, we show the adjacent 2-cell regions in the 2-variable K-map with the aid of previous rectangular Venn diagram like Boolean regions.
Cells α and χ are adjacent in the K-map as ellipses in the left most K-map below. Referring to the previous truth table, this is not the case. There is another truth table entry (β) between them. Which brings us to the whole point of the organizing the K-map into a square array, cells with any Boolean variables in common need to be close to one another so as to present a pattern that jumps out at us. For cells α and χ they have the Boolean variable B’ in common. We know this because B=0 (same as B’) for the column above cells α and χ. Compare this to the square Venn diagram above the K-map.
A similar line of reasoning shows that β and δ have Boolean B (B=1) in common. Then, α and β have Boolean A’ (A=0) in common. Finally, χ and δ have Boolean A (A=1) in common. Compare the last two maps to the middle square Venn diagram.
To summarize, we are looking for commonality of Boolean variables among cells. The Karnaugh map is organized so that we may see that commonality. Let’s try some examples.
Example:
Transfer the contents of the truth table to the Karnaugh map above.
Solution:
The truth table contains two 1s. the K- map must have both of them. locate the first 1 in the 2nd row of the truth table above.
- note the truth table AB address
- locate the cell in the K-map having the same address
- place a 1 in that cell
Repeat the process for the 1 in the last line of the truth table.
Example:
For the Karnaugh map in the above problem, write the Boolean expression. Solution is below.
Solution:
Look for adjacent cells, that is, above or to the side of a cell. Diagonal cells are not adjacent. Adjacent cells will have one or more Boolean variables in common.
- Group (circle) the two 1s in the column
- Find the variable(s) top and/or side which are the same for the group, Write this as the Boolean result. It is B in our case.
- Ignore variable(s) which are not the same for a cell group. In our case A varies, is both 1 and 0, ignore Boolean A.
- Ignore any variable not associated with cells containing 1s. B’ has no ones under it. Ignore B’
- Result Out = B
This might be easier to see by comparing to the Venn diagrams to the right, specifically the B column.
Example:
Write the Boolean expression for the Karnaugh map below.
Solution: (above)
- Group (circle) the two 1’s in the row
- Find the variable(s) which are the same for the group, Out = A’
Example:
For the Truth table below, transfer the outputs to the Karnaugh, then write the Boolean expression for the result.
Solution:
Transfer the 1s from the locations in the Truth table to the corresponding locations in the K-map.
- Group (circle) the two 1’s in the column under B=1
- Group (circle) the two 1’s in the row right of A=1
- Write product term for first group = B
- Write product term for second group = A
- Write Sum-Of-Products of above two terms Output = A+B
The solution of the K-map in the middle is the simplest or lowest cost solution. A less desirable solution is at far right. After grouping the two 1s, we make the mistake of forming a group of 1-cell. The reason that this is not desirable is that:
- The single cell has a product term of AB’
- The corresponding solution is Output = AB’ + B
- This is not the simplest solution
The way to pick up this single 1 is to form a group of two with the 1 to the right of it as shown in the lower line of the middle K-map, even though this 1 has already been included in the column group (B). We are allowed to re-use cells in order to form larger groups. In fact, it is desirable because it leads to a simpler result.
We need to point out that either of the above solutions, Output or Wrong Output, are logically correct. Both circuits yield the same output. It is a matter of the former circuit being the lowest cost solution.
Example:
Fill in the Karnaugh map for the Boolean expression below, then write the Boolean expression for the result.
Solution: (above)
The Boolean expression has three product terms. There will be a 1 entered for each product term. Though, in general, the number of 1s per product term varies with the number of variables in the product term compared to the size of the K-map. The product term is the address of the cell where the 1 is entered. The first product term, A’B, corresponds to the 01 cell in the map. A 1 is entered in this cell. The other two P-terms are entered for a total of three 1s
Next, proceed with grouping and extracting the simplified result as in the previous truth table problem.
Example:
Simplify the logic diagram below.
Solution: (Figure below)
- Write the Boolean expression for the original logic diagram as shown below
- Transfer the product terms to the Karnaugh map
- Form groups of cells as in previous examples
- Write Boolean expression for groups as in previous examples
- Draw simplified logic diagram
Example:
Simplify the logic diagram below.
Solution:
- Write the Boolean expression for the original logic diagram shown above
- Transfer the product terms to the Karnaugh map.
- It is not possible to form groups.
- No simplification is possible; leave it as it is.
No logic simplification is possible for the above diagram. This sometimes happens. Neither the methods of Karnaugh maps nor Boolean algebra can simplify this logic further. We show an Exclusive-OR schematic symbol above; however, this is not a logical simplification. It just makes a schematic diagram look nicer. Since it is not possible to simplify the Exclusive-OR logic and it is widely used, it is provided by manufacturers as a basic integrated circuit (7486).
Logic Simplification With Karnaugh Maps
The logic simplification examples that we have done so could have been performed with Boolean algebra about as quickly. Real world logic simplification problems call for larger Karnaugh maps so that we may do serious work. We will work some contrived examples in this section, leaving most of the real world applications for the Combinatorial Logic chapter. By contrived, we mean examples which illustrate techniques. This approach will develop the tools we need to transition to the more complex applications in the Combinatorial Logic chapter.
We show our previously developed Karnaugh map. We will use the form on the right.
Note the sequence of numbers across the top of the map. It is not in binary sequence which would be 00, 01, 10, 11. It is 00, 01, 11 10, which is Gray code sequence. Gray code sequence only changes one binary bit as we go from one number to the next in the sequence, unlike binary. That means that adjacent cells will only vary by one bit, or Boolean variable. This is what we need to organize the outputs of a logic function so that we may view commonality. Moreover, the column and row headings must be in Gray code order, or the map will not work as a Karnaugh map. Cells sharing common Boolean variables would no longer be adjacent, nor show visual patterns. Adjacent cells vary by only one bit because a Gray code sequence varies by only one bit.
If we sketch our own Karnaugh maps, we need to generate Gray code for any size map that we may use. This is how we generate Gray code of any size.
Note that the Gray code sequence, above right, only varies by one bit as we go down the list, or bottom to top up the list. This property of Gray code is often useful in digital electronics in general. In particular, it is applicable to Karnaugh maps.
Let us move on to some examples of simplification with 3-variable Karnaugh maps. We show how to map the product terms of the unsimplified logic to the K-map. We illustrate how to identify groups of adjacent cells which leads to a Sum-of-Products simplification of the digital logic.
Above we, place the 1’s in the K-map for each of the product terms, identify a group of two, then write a p-term (product term) for the sole group as our simplified result.
Mapping the four product terms above yields a group of four covered by Boolean A’
Mapping the four p-terms yields a group of four, which is covered by one variable C.
After mapping the six p-terms above, identify the upper group of four, pick up the lower two cells as a group of four by sharing the two with two more from the other group. Covering these two with a group of four gives a simpler result. Since there are two groups, there will be two p-terms in the Sum-of-Products result A’+B
The two product terms above form one group of two and simplifies to BC
Mapping the four p-terms yields a single group of four, which is B
Mapping the four p-terms above yields a group of four. Visualize the group of four by rolling up the ends of the map to form a cylinder, then the cells are adjacent. We normally mark the group of four as above left. Out of the variables A, B, C, there is a common variable: C’. C’ is a 0 over all four cells. Final result is C’.
The six cells above from the unsimplified equation can be organized into two groups of four. These two groups should give us two p-terms in our simplified result of A’ + C’.
Below, we revisit the Toxic Waste Incinerator from the Boolean algebra chapter. See Boolean algebra chapter for details on this example. We will simplify the logic using a Karnaugh map.
The Boolean equation for the output has four product terms. Map four 1’s corresponding to the p-terms. Forming groups of cells, we have three groups of two. There will be three p-terms in the simplified result, one for each group. See “Toxic Waste Incinerator”, Boolean algebra chapter for a gate diagram of the result, which is reproduced below.
Below we repeat the Boolean algebra simplification of Toxic waste incinerator for comparison.
Below we repeat the Toxic waste incinerator Karnaugh map solution for comparison to the above Boolean algebra simplification. This case illustrates why the Karnaugh map is widely used for logic simplification.
The Karnaugh map method looks easier than the previous page of boolean algebra.
Below we repeat the Toxic waste incinerator Karnaugh map solution for comparison to the above Boolean algebra simplification. This case illustrates why the Karnaugh map is widely used for logic simplification.
The Karnaugh map method looks easier than the previous page of boolean algebra.
variable Karnaugh Maps
Knowing how to generate Gray code should allow us to build larger maps. Actually, all we need to do is look at the left to right sequence across the top of the 3-variable map, and copy it down the left side of the 4-variable map. See below.
The following four variable Karnaugh maps illustrate reduction of Boolean expressions too tedious for Boolean algebra. Reductions could be done with Boolean algebra. However, the Karnaugh map is faster and easier, especially if there are many logic reductions to do.
The above Boolean expression has seven product terms. They are mapped top to bottom and left to right on the K-map above. For example, the first P-term A’B’CD is first row 3rd cell, corresponding to map location A=0, B=0, C=1, D=1. The other product terms are placed in a similar manner. Encircling the largest groups possible, two groups of four are shown above. The dashed horizontal group corresponds the the simplified product term AB. The vertical group corresponds to Boolean CD. Since there are two groups, there will be two product terms in the Sum-Of-Products result of Out=AB+CD.
Fold up the corners of the map below like it is a napkin to make the four cells physically adjacent.
The four cells above are a group of four because they all have the Boolean variables B’ and D’ in common. In other words, B=0 for the four cells, and D=0 for the four cells. The other variables (A, C) are 0 in some cases, 1 in other cases with respect to the four corner cells. Thus, these variables (A, C) are not involved with this group of four. This single group comes out of the map as one product term for the simplified result: Out=B’D’
For the K-map below, roll the top and bottom edges into a cylinder forming eight adjacent cells.
The above group of eight has one Boolean variable in common: B=0. Therefore, the one group of eight is covered by one p-term: B’. The original eight term Boolean expression simplifies to Out=B’
The Boolean expression below has nine p-terms, three of which have three Booleans instead of four. The difference is that while four Boolean variable product terms cover one cell, the three Boolean p-terms cover a pair of cells each
The six product terms of four Boolean variables map in the usual manner above as single cells. The three Boolean variable terms (three each) map as cell pairs, which is shown above. Note that we are mapping p-terms into the K-map, not pulling them out at this point.
For the simplification, we form two groups of eight. Cells in the corners are shared with both groups. This is fine. In fact, this leads to a better solution than forming a group of eight and a group of four without sharing any cells. Final Solution is Out=B’+D’
Below we map the unsimplified Boolean expression to the Karnaugh map.
Above, three of the cells form into a groups of two cells. A fourth cell cannot be combined with anything, which often happens in “real world” problems. In this case, the Boolean p-term ABCD is unchanged in the simplification process. Result: Out= B’C’D’+A’B’D’+ABCD
Often times there is more than one minimum cost solution to a simplification problem. Such is the case illustrated below.
Both results above have four product terms of three Boolean variable each. Both are equally valid minimal cost solutions. The difference in the final solution is due to how the cells are grouped as shown above. A minimal cost solution is a valid logic design with the minimum number of gates with the minimum number of inputs.
Below we map the unsimplified Boolean equation as usual and form a group of four as a first simplification step. It may not be obvious how to pick up the remaining cells.
Pick up three more cells in a group of four, center above. There are still two cells remaining. the minimal cost method to pick up those is to group them with neighboring cells as groups of four as at above right.
On a cautionary note, do not attempt to form groups of three. Groupings must be powers of 2, that is, 1, 2, 4, 8 ...
Below we have another example of two possible minimal cost solutions. Start by forming a couple of groups of four after mapping the cells.
The two solutions depend on whether the single remaining cell is grouped with the first or the second group of four as a group of two cells. That cell either comes out as either ABC’ or ABD, your choice. Either way, this cell is covered by either Boolean product term. Final results are shown above.
Below we have an example of a simplification using the Karnaugh map at left or Boolean algebra at right. Plot C’ on the map as the area of all cells covered by address C=0, the 8-cells on the left of the map. Then, plot the single ABCD cell. That single cell forms a group of 2-cell as shown, which simplifies to P-term ABD, for an end result of Out = C’ + ABD.
This (above) is a rare example of a four variable problem that can be reduced with Boolean algebra without a lot of work, assuming that you remember the theorems.
