Version 3 of Mahoney Map

Updated 2009-01-28 16:16:55 by andy

AMG: A Mahoney map is like a Karnaugh map [L1 ] with a more straightforward generation process. Either can be used for simplifying logical expressions, particularly for making a simplified logical expression given a truth table.

Someday I will put code here, but for now I will just demonstrate the process of constructing a Mahoney map.

Let's start with the simple single-variable case. I will call this variable A. Make a table like this:

0 1

The numbers 0 and 1 represent /A and A, respectively, where /A is pronounced "not-A". (Man, I wish I could type an overbar!)

Now let's add a second variable B. Mirror the table vertically and add a new digit to the left-hand side, which will represent /B and B. Put 0 on the bottom row and 1 on the top row. 00: /A/B, 01: /AB, 10: A/B, 11: AB.

10 11
00 01

A third variable C can be added by mirroring horizontally and adding a third digit to the left-hand side. Put 0 on the left two columns and 1 on the right two columns.

010 011 111 110
000 001 101 100

Now a fourth variable D! Mirror vertically and add a fourth digit on the left-hand side. Put 0 on the bottom two rows and 1 on the top two rows.

1000 1001 1101 1100
1010 1011 1111 1110
0010 0011 0111 0110
0000 0001 0101 0100

Now that things are out of the realm of the trivial, let's just grab a cell at random and explain its meaning. Take 1011. What that really means is "D and (not C) and B and A", which can also be written "D/CBA". To actually use this to convert a truth table to a logical expression, circle every cell that corresponds to a "true" entry in the truth table. If the function of variables A, B, C, and D is true when "(D and (not C) and B and A)" is true, circle 1011. Depending on the truth table, there will hopefully be several adjacent circled entries, forming rows, columns, or rectangles of width and/or height 2 or 4 (but not 3; it's not a power of two). Circle these. The table wraps around the edges, so the grouping circles can wrap too. Just like how each individual cell corresponds to a single expression (such as D/CBA = 1011), the larger grouping circles correspond to expressions, also known as minterms. For example, if 1000, 1001, 1010, and 1011 are circled, that corresponds to D/C = 10xx, where "x" means "I don't care". Let's say there are large circles: 1000+1001+1010+1011 and 0111+0101. This corresponds to the expression "((D and (not C)) or ((not D) and C and A))", also written "D/C+/DCA". In order of decreasing precedence, a prefixed "/" is "not", juxtaposition is "and", and "+" is "or".

We can keep going. Just alternate between mirroring horizontally and vertically. However, after four variables things start to get tricky. Why is that? First let me explain why the above stuff isn't tricky. :^) Since the tables wrap*, each cell is adjacent to N other cells, where N is the number of variables. Adjacent cells differ in only one variable, which in my notation is one digit (or bit). But since this Wiki only allows me to create two-dimensional tables (lousy stupid wiki!), I can't actually draw a table where a cell visibly has five neighbors. So you will have to use your imagination. Pretend that the right four columns in this next table are stacked on top of the left four columns. Pretend that you have this page printed out and folded with a vertical crease down the middle, so that the rightmost column is touching the leftmost column.

* Actually they don't wrap, but the effect is same. Cells on opposite edges are adjacent because the table is "folded" so that they touch. The problem with thinking in terms of wrapping is that it may cause you to fail to notice some adjacencies when working with five or more variables.

01000 01001 01101 01100 11100 11101 11001 11000
01010 01011 01111 01110 11110 11111 11011 11010
00010 00011 00111 00110 10110 10111 10011 10010
00000 00001 00101 00100 10100 10101 10001 10000

And again!

100000 100001 100101 100100 110100 110101 110001 110000
100010 100011 100111 100110 110110 110111 110011 110010
101010 101011 101111 101110 111110 111111 111011 111010
101000 101001 101101 101100 111100 111101 111001 111000
001000 001001 001101 001100 011100 011101 011001 011000
001010 001011 001111 001110 011110 011111 011011 011010
000010 000011 000111 000110 010110 010111 010011 010010
000000 000001 000101 000100 010100 010101 010001 010000

Now not only are the right four columns adjacent to the left four columns, but the top four rows are adjacent to the bottom four rows. The consequence of this is that not only are you grouping adjacent cells into rows and columns, but also into stacks. For example, the second and seventh cells on the top row are adjacent; they differ only in the second bit (E). They can be grouped. But it's not visually obvious, and now that there are six variables, it's getting hard to imagine in terms of folding. This is where the notation stops being usable, and it makes sense to pick a different approach to simplifying your expression.

But! With a nifty Tk program I could make the table highlight adjacent cells to help overcome the limitations of the notation. Maybe someday I will write one!

Lars H: The natural domain for an n-variable function is an n-dimensional hypercube, but working directly with that is difficult already for n=3. Karnaugh maps compresses two dimensions of the hypercube into one dimension of the table by using the observation that a 2-dimensional hypercube — a square — is also a cycle of length 4, so by changing

  | |      to    -1-2-3-4-

in the drawing, one can depict an n-dimensional hypercube in n/2 dimensions. That way, things work well all the way up to 4 variables. In order to get further, one needs to employ an additional trick.

AMG: In a Mahoney map, this kind of compression happens with every other pair of variables. Take the third table:

010 011 111 110
000 001 101 100

Replace the second variable (B) with don't-care:

0x0 0x1 1x1 1x0
0x0 0x1 1x1 1x0

The two rows are now the same, so drop one. Also drop the don't-care term and understand that the bit assignment is now CA:

00 01 11 10

Now compare with the second table, mentally substituting C for B as the first bit and flipping vertically to match your top-to-bottom convention:

00 01
10 11

See the resemblance? In the above two tables, replace 00 with 1, 01 with 2, 11 with 3, and 10 with 4 to get your two tables.

Why the vertical flip? I used bottom-to-top so that all-bits-zero would be in the lower-left corner, similar to the origin in the first quadrant of the Cartesian plane. But you used top-to-bottom, presumably to match conventional reading order. It doesn't matter which is used.