Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 57 ยท Simplification

Variable Entrant Maps (VEM)

Learn variable entrant maps: fold one variable into the cells of a smaller K-map, then simplify with a step-by-step method and a Python checker.

A Karnaugh map is wonderful up to four variables, and awkward beyond. A five-variable map needs two grids stacked in your head, and a six-variable map needs four. The Quine-McCluskey method handles any size but is a table procedure for a computer, not a drawing for a person. A variable entrant map (VEM, also called a map-entered variable map or MEV map) sits in between: it folds one or more variables into the cells of a smaller map, so a 4-variable function fits on an 8-cell map and a 5-variable function on a 16-cell map.

This lesson shows how to build a VEM, how to read its cell entries (0, 1, D and D'), and the step-by-step method that turns it into a sum of products. A Python program carries out the same method and checks the answer against the full truth table.

The idea: let a cell hold a function

In a normal K-map each cell holds 0 or 1: the output for one fixed combination of all variables. Now choose one variable, say D, to be the entered variable, and keep only the others (A, B, C) as the map variables. Each cell now stands for a fixed combination of A, B, C and shows what the output does as D varies. There are only four possibilities for a single entered variable:

F when D = 0 F when D = 1 Cell entry Meaning
0 0 0 output is 0 whatever D is
1 1 1 output is 1 whatever D is
0 1 D output follows D
1 0 D' output is the opposite of D

A normal 4-variable map has two cells (or truth-table rows) for each ABC combination. A VEM merges that pair into one cell, and records the pair as one of the four entries. With two entered variables the entries become expressions in two variables (D, E, D + E, DE', and so on), and the map shrinks further, but one entered variable is plenty to learn the method.

Building the map from a minterm list

Suppose F(A, B, C, D) = ฮฃ m(1, 2, 5, 6, 9, 10, 14, 15), where the minterm number is 8A + 4B + 2C + D. The two minterms that share the same ABC are 2ยทABC and 2ยทABC + 1 (the rows with D = 0 and D = 1). The program below builds the cell entries.

Python From minterms to cell entries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Arrange the eight cells in a 2 by 4 grid with the columns in Gray code order (BC = 00, 01, 11, 10), exactly like an ordinary K-map, so that neighbours differ in one map variable:

BC = 00 01 11 10
A = 0 D D' D' D
A = 1 D D' 1 0

Everything you know about K-map adjacency still applies, including wrap-around, so the left and right columns are neighbours.

The simplification method

You cannot just circle "ones", because the cells now contain more than ones. The method splits the work by entry type. Each pass produces product terms of the map variables, and the terms from the entered-variable passes get that variable ANDed on.

  1. Constant 1 terms. Look only at the cells that contain 1. Treat every other cell (0, D, D') as 0, then group the 1s exactly as in a normal K-map. These groups give ordinary product terms with no D in them. (A cell containing D must not be used here: a group that covers it would be 1 when D = 0, which is wrong for that cell.)
  2. Terms for D. Now look at the cells that contain D. Treat them as the 1s of a new map. The cells containing a constant 1 are don't cares (they already get their 1 from step 1, so covering them again does no harm), and everything else (0, D') is 0. Find the minimal groups, and AND each resulting term with D.
  3. Terms for D'. The same again, with the D' cells as the 1s, the constant 1 cells as don't cares, and the final terms ANDed with D'.
  4. Add all the terms together. This is the sum of products for the function.

Apply it to the map above. The only constant 1 is the cell A=1, BC=11, and nothing else can join it, so step 1 gives ABC. The D cells are 000, 010 and 100. Grouping A=0, C=0 (cells 000 and 010, with B free) gives A'C', and grouping B=0, C=0 (cells 000 and 100) gives B'C'. So step 2 contributes A'C'D + B'C'D. The D' cells are 001, 011 and 101; together with the constant cell 111 as a don't care they form one group of four where C = 1, giving CD'. The answer is

F = ABC + A'C'D + B'C'D + CD'

which has 4 terms and 11 literals, the same cost as the minimal answer you would find with a full 4-variable K-map.

A checker you can run

The program implements all four steps. It finds every group on the 8-cell map, keeps only the prime groups that stay inside the allowed cells, and picks the cheapest set that covers the required cells. At the end it evaluates the result for all 16 input rows and compares it with the original function. It runs on two different functions.

Python The VEM method and an exhaustive check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second function ends up as F = BC' + BD + A'CD + A'C'D'. Notice how the groups with D and D' pick up different map-variable terms, and how each answer is verified for all 16 combinations. Treat that last line as part of the method: a hand-made VEM is easy to get wrong in the don't-care step, and a brute-force check takes seconds.

When to use it

Method Best for Weak spot
Algebra and laws tiny expressions needs insight, no guarantee of minimality
K-map 2 to 4 variables gets hard beyond 4
VEM 5 to 6 variables by hand; 4 variables with a clear entered variable the entry-by-entry procedure takes care, and sharing between the passes can be missed
Quine-McCluskey any size, by computer a table method, not visual

VEMs also help with design. When one input (a data bit, say) goes straight through some cells and is inverted in others, the entries D and D' show you the structure of the circuit, like a multiplexer with D and D' on its data inputs and A, B, C on the selects. You will meet that view in the multiplexers lesson. Don't cares from don't cares and hazards work in a VEM too: a don't-care cell can be treated as whichever of 0, 1, D or D' helps the grouping.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a VEM with entered variable D, what does the cell entry D' mean?

    The entry D' means F = 1 when D = 0 and F = 0 when D = 1 for that cell's combination of map variables.
  2. 2. How many cells does a VEM need for a 5-variable function with one entered variable?

    Four map variables give 2^4 = 16 cells. The fifth variable is folded into the cell entries.
  3. 3. When grouping the constant 1 cells (step 1), how are the cells containing D treated?

    A cell holding D is 0 when D = 0. A product term without D that covers it would wrongly output 1 there.
  4. 4. When finding the terms for D, what happens to the cells that contain a constant 1?

    A D-term covers a constant-1 cell correctly only when D = 1, which is harmless since the cell is already 1 from another term, so those cells can be used to make groups larger.
  5. 5. What is the last step of the method?

    Each pass yields product terms, and the final function is their sum.

Summary

  • A variable entrant map folds one (or more) variables into the cells of a smaller K-map; each cell holds 0, 1, D or D' when one variable D is entered.
  • Build the entry for each combination of the map variables from the pair of truth-table rows that differ only in D.
  • Simplify in passes: ones-only for constant 1 terms, then the D cells (constant-1 cells as don't cares) with D ANDed on, then the same for D', and add the results.
  • Always verify the result against the full truth table; the pass structure makes slips easy.
  • VEMs let you handle 5 and 6 variables by hand and show the multiplexer structure of a function.

Next: Half Adders and Full Adders