Label unlabeled Karnaugh map according to given truth table

Question

Assuming I have an unlabeled but filled out Karnaugh map and a truth table with variables, what algorithm can I follow to find the correct label (variable) for each row and column of the map?

Example:

Answer 1

It is not always possible to assign the correct labels.

Example:

             cd
       00  01  11  10
      +---+---+---+---+
   00 | 0 | 0 | 0 | 0 |
      +---+---+---+---+
   01 | 0 | 0 | 0 | 0 |
ab    +---+---+---+---+
   11 | 0 | 0 | 1 | 0 |
      +---+---+---+---+
   10 | 0 | 0 | 0 | 0 |
      +---+---+---+---+

Here, one could exchange ab and cd without changing the map. This is the case for all symmetric maps (see below).

Imagine a map with all zero values or all one values. Again, it would not be possible to be certain about the labels.

Assuming a 4-input map with the order of rows and columns fixed to 00 01 11 10, the four variables can be assigned in 4*3*2*1 = 24 ways. To determine a correct labeling, one could try them out starting with the most likely ones: ab|cd, cd|ab, ac|bd, db|ca.

The design principle of Karnaugh maps does enforce an ordering of rows and columns with exactly one bit-change between neighbors. Therefore, 00 10 11 01 or 11 10 00 01 would also be valid orderings. Taking this into account would lengthen the try-and-error search considerably.

In case the Karnaugh map is filled in a symmetric fashion (cell values do not change by swapping rows and columns), the number of label assignments is halved to 2*3*2*1 = 12.

---

Update:

In your example, you could label the Karnaugh map with vw on the left and xy at the top. If you then derive a minimized expression for the Karnaugh map, you get

$$w\bar{y} \lor \bar{w} \bar{x} $$

From the truth table, you get:

$$\bar{c}d \lor \bar{a} \bar{d}$$

A comparison of these two expressions leads to the conclusion that:

• Label $w$ should be $d$
• Label $x$ should be $a$
• Label $y$ should be $c$
• Label $v$ should be $b$