Karnaugh Maps
Karnaugh Maps, also known as K-maps, are a graphical method used to simplify Boolean algebra expressions. They provide a systematic way to minimize logical functions and are commonly used in digital circuit design and optimization. By grouping and combining adjacent 1s in the map, Karnaugh Maps help in reducing the number of terms in a Boolean expression, leading to more efficient circuit designs.
6 Key excerpts on "Karnaugh Maps"
eBook - ePub- J. Gibson(Author)
- 2013(Publication Date)
- Routledge(Publisher)
...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...
eBook - ePub- Brian Holdsworth, Clive Woods(Authors)
- 2002(Publication Date)
- Newnes(Publisher)
...3 Karnaugh Maps and function simplification 3.2 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 could 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 (or ‘K-map’) and with the help 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 variables it is better to use a tabulation method such as that due to Quine and McCluskey which, after programming, can be run on a computer. 3.2 Minterms and maxterms As explained in section 2.5, a minterm (sometimes called a ‘product term’ or ‘P-term’) of n variables is the logical AND of all n variables where any of the n variables may be represented by the variable itself or 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 3.1. Corresponding to these four combinations of the variables there are four possible minterms which can be obtained as follows. In the first row of the table A = 0 and B = 0, hence = 1. The minterm is formed using the values of the variables which make the value of the minterm equal to 1, hence m 0 =Ā. The other three minterms are obtained in the same way. Figure 3.1 The minterms and maxterms of two variables As also explained in section 2.5, a maxterm (sometimes called a ‘sum term’ or ‘S-term’) of n variables is the logical OR of all n variables where any one of the variables may be represented by its true or complemented form...
eBook - ePubDigital Design
Basic Concepts and Principles
- Mohammad A. Karim, Xinghao Chen(Authors)
- 2017(Publication Date)
- CRC Press(Publisher)
...The graphical technique, which was proposed by Veich and later modified by Karnaugh, allows minimized 2-level functions to be obtained with very little effort. This particular map is referred to as 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 rat 10 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...
eBook - ePub- Raymond F. Gardner(Author)
- 2020(Publication Date)
- CRC Press(Publisher)
...The chip has two additional pins for power (+5Vdc) and return (ground). From the truth table at the right, a 0V input at either pin A, B, or both produces a NAND output of 1, indicating TRUE, which is seen as +5V at the Y pin. If both A and B switches are closed (TRUE), then the output at Y goes FALSE, and 0V shows at the Y pin. (Courtesy of Texas Instruments.) INTRODUCTION TO Karnaugh Maps A Karnaugh map is an alternative method to graphically simplify logic-gate functions without using Boolean algebra. A Karnaugh map is an “expanded-table” representation of the truth tables. Karnaugh Maps are practical for simplifying relatively small Boolean functions of up to six variables, but for larger logic gates, more complex computer algorithms are available. Karnaugh Maps can reduce the number of gates, and they can provide some insight into how digital logic circuits work. In electronic circuits, simplified Boolean functions require fewer components, making them faster and less expensive, while generating less heat. In the Karnaugh map, each combination of input and output logic state is mapped into a table, however the table must be organized so that moving from one cell to the next in either the vertical or horizontal direction changes only one digit. For that reason, the columns in Figure 4.7 do not follow binary numbering between cells (Binary: 00, 01, 10, and 11). Instead, the numbering sequence follows Gray code numbering (Gray: 00, 01, 11, 10), which permits only one digit to be modified for each increment. In the Gray-code sequence used in the Karnaugh table, the middle columns vary by only one bit of change, but likewise the first and last columns are also limited to the one-bit change as decimal 3 (10) shifts only one digit to revert to decimal 0 (00)...
eBook - ePub- J. Crowe, Barrie Hayes-Gill(Authors)
- 1998(Publication Date)
- Butterworth-Heinemann(Publisher)
...In practice Karnaugh Maps become unmanageable for more than five variables (i.e. 32 cells). A three-variable map will have eight cells and its layout is shown in Table 3.9. We will now look at some examples of using three-variable Karnaugh Maps for minimisation. Table 3.9 Layout and labelling of a three-variable truth table and Karnaugh map illustrating the fundamental product terms occupying each cell Example 3.16 Draw the truth table and Karnaugh map for the function Solution This expression has three variables and so the Karnaugh map must contain eight cells. The variables A and B are used to label the four columns in the map (with the four possible combinations of these two variables), with the third variable, C, used to label the two rows (for C = 0 and C = 1) as shown in Table 3.9. The outputs, Y, for the various inputs to the circuit represented by the truth table are entered into the corresponding cells in the Karnaugh map as shown in Table 3.10. To minimise we note that there are two logically adjacent fundamental product terms in column AB (and ABC), and a further two in row C (and) which can be combined to give (as). Therefore Table 3.10 Karnaugh map for discussed in Example 3.16 The grouping of logically adjacent product terms for minimisation is indicated by looping them on the Karnaugh map, as illustrated in the above example. Obviously all fundamental product terms (i.e. 1’s on the Karnaugh map) must be looped and so contribute to the final minimised sum of products expression. Two grouped and looped fundamental product terms are referred to as a dual. To obtain the minimised product terms any variable existing in both uncomplemented and complemented forms within the looped product term is omitted...
eBook - ePub- John Stonham(Author)
- 2017(Publication Date)
- CRC Press(Publisher)
...--]B + C). (A ¯ + B ¯ + C) Remember. In the 2nd canonical form A→0 and A → → 1. Minimal canonical forms The canonical forms obtained from the truth table can, in most cases, be simplified or minimized while the AND/OR structure of the 1st form or the OR/AND of the 2nd form are still maintained. The minimization theorems from Boolean algebra could be used directly on the logic equations, but this is a somewhat open-ended exercise, and it is quite often difficult to tell when the simplest version has been obtained. A graphical method of minimizing logic functions was devised by Karnaugh in 1953. It is based on the minimization theorems and Venn diagrams but also guarantees that the circuit is in its simplest form. The Karnaugh map Also known as a K-map. Consider a Venn diagram containing the binary variable A, occupying half the universe. The areas must overlap as A and B are not disjoint. Now, if a second variable B is introduced, which partitions the universe horizontally, we get Replacing the shaded areas with labels on the axes, we obtain a four-celled K-map, and each cell can contain the output of a logic function when its inputs have the values of the cell co-ordinates. A four-celled K-map can represent any two-variabled logic function. In the K-map of an AND function, a one is placed in the cell corresponding to the intersection of areas A and B on the Venn diagram, whereas the OR function is the union of these areas (see Fig. 3.3). Fig. 3.3 Karnaugh Maps for the AND and OR functions. This is not pure binary. Karnaugh Maps for three- and four-variabled functions can be drawn in two dimensions. Three-dimensional maps can represent functions of up to six variables. As the areas representing the individual variables must overlap, each axis must be labelled in Gray code and cannot be extended to more than two variables. The Gray code labelling is 00, 01, 11, 10 for adjacent rows or columns. Maps for three- and four-variabled functions are shown in Fig. 3.4...
