1. Digital Logic
2. Topic: K-Maps with Entered Variables

Entered Variables

Entered variable maps simplify the process further by visually minimizing a K-map. The compression of the map makes a multi-variable system much easier to visualize and minimize.

Truth tables provide the best mechanism for completely specifying the behavior of a given combinational logic circuit, and K-maps provide the best mechanism for visualizing and minimizing the input-output relationships of digital logic circuits. So far, we have shown input variables across the top left of a truth table and around the periphery of K-maps. This allows every state of an output signal to be defined as a function of the input patterns of 0’s and 1’s on a given row in a truth table, or as the binary coding for a given K-map cell. Without any loss of information, truth tables and K-maps can be translated into a more compact form by moving input variables from the top-left of a truth table to the output column, or from outside the K-map to inside the cells of a K-map. Although it will not be clear until later modules, the use of entered variables and compressed truth tables and K-maps often makes a multi-variable system much easier to visualize and minimize.

The translation mechanics are illustrated in the figures below, where a 16-row truth table is compressed into both 8-row and 4-row truth tables. In the 8-row truth table, the variable D is no longer used to identify an input column. Instead, it appears in the output column, where it encodes the relationship between two rows of output logic values and the D input. In the 4-row truth table, variables C and D are no longer used to identify an input column, but rather in the output column where they encode the relationship between four rows of the output logic values and the C and D inputs.

The 4-cell K-map is reproduced to the right, this time showing the implied sub-maps that illustrate the relationship between C and D for each of the four unique values of the A and B variables. For any entered variable K-map, thinking of (or actually sketching) the sub-maps can help identify the correct encoding for the entered variables. Note that truth table row numbers can be mapped to cells in the sub-maps by reading the K-map index codes, starting with the super-map code, and appending the sub-map code. For example, the shaded box in the sub-map is in box number 1110.

This same map compression is illustrated below, showing the mapping from non-compressed K-maps directly to compressed K-maps. The colors show how cells in the uncompressed map are translated to the cells in the compressed map. Note that two cells in the 16-cell map are compressed into a single cell in the 8-cell map, and that four cells in the 16-cell map are compressed into a single cell in the 4-cell map.

Minterm SOP equations and maxterm POS equations can also be translated directly into entered variable K-maps as shown in the illustration below (the smaller numbers at the bottom of K-map cells show the minterm or maxterm numbers assigned to that cell). The minimum number of input variables is assumed when encoding minterms or maxterms into the K-maps. For example, if the largest minterm present is 14, four input variables are assumed.

Looping entered variable K-maps follows the same general principles as looping ‘1-0’ maps optimal groupings of 1’s and entered variables (EVs) are sought for SOP circuits, and optimal groupings of 0’s and EVs are sought for POS circuits. The rules are similar: all EVs and all 1’s (or 0’s) must be grouped in the largest possible‚ power of 2‚ sized rectangular or square grouping, and the process is complete when all EVs and all 1’s (or 0’s) are included in an optimal loop. The differences are that similar EVs can be included in loops by themselves or with 1’s (or 0’s), and care must be taken when looping cells with 1’s (or 0’s), because a ‘1’ (or ‘0’) indicates that all possible combinations of EVs are present in that map cell, and loops that include 1’s (or 0’s) together with EVs often include only a subset of the possible combinations of the EVs (this is illustrated in Fig. 4 below). Looping an EV K-map is complete when all minterms or maxterms are contained in an adequate group. Perhaps the most challenging aspect is to ensure that all possible combinations of EVs have been accounted for in cells that contain 1’s (or 0’s).

To help understand looping in EV K-maps, it may be helpful to think of the sub-maps implied by every K-map cell. As shown in the figures below, the variables in K-map cells can arise from looping the ‘1-0’ information entered into cells in the implied sub-maps. A looping of information in adjacent cells in the EV K-map can include 1’s (or 0’s) in the sub-maps that appear in the same positions in the sub-maps.

When reading the loop equations, the SOP product terms (or POS sum terms) for each loop must include the variables that define the loop domain and the EVs contained within the loop. For example, in the first example below, the first SOP term $\overline A \cdot \overline B \cdot D$ includes the loop domain $\overline A \cdot \overline B$ and the entered variable D.

Cells in entered variable maps might contain a single entered variable or a logic expression of two or more variables. When looping cells that contain logic expressions, it helps to recognize the differences in SOP and POS looping mechanics. As compared to a single EV in a K-map cell, a product term in a cell represents a smaller SOP domain, because the more AND’ed variables in a product term, the smaller the defined logic domain. A sum term in a cell represents a larger SOP domain, because the more OR’ed variables in a sum term, the larger the defined logic domain. When looping SOP equations from an EV map, cells containing product terms have fewer 1’s in their sub-maps than cells that contain single EVs, and cells with sum terms contain more 1’s. Similarly, when looping POS equations from an EV map, cells containing sum terms have fewer 0’s in their sub-maps than cells that contain single EVs, and cells with product terms contain more 0’s.

Don’t cares in entered variable K-maps serve the same purpose as they did in ‘1-0’ maps; they indicate input conditions that cannot occur or that are irrelevant, and they can be included in groupings of 1’s, 0’s, or entered variables as needed to minimize logic. As shown in Fig. 5 below, a given don’t care can be taken as a ‘1’, ‘0’, or entered variable as needed for any particular loop.

Important Ideas

• Without any loss of information, truth tables and K-maps can be translated into a more compact form by moving input variables from the top-left of a truth table to the output column, or from outside the K-map to inside the cells of a K-map.
• Minterm SOP equations and maxterm POS equations can also be translated directly into entered variable K-maps.
• Looping entered variable K-maps follows the same general principles as looping ‘1-0’ maps.
• Cells in entered variable maps might contain a single entered variable or a logic expression of two or more variables.
• Don’t cares in entered variable K-maps serve the same purpose as they did in ‘1-0’ maps.