Algorithm to simplify kv map with more than 4 variables

Question

does someone know an algorithm to simplify a kv map with more than 4 variables. With 4 variables you just creat groups of field that are near each other. And than you can write down the logic expression that discribes this group. By doing this for all groups you get a simplified version of you logix expression that you used to creat the kv map.

According to this:

Die Bedingung dafür, dass mehrere Felder eine Gruppe bilden können, ist daher nicht, dass es sich um zusammenhängende rechteckige Blöcke handelt, sondern ob es möglich ist, eine entsprechende Gruppe durch Spiegelung und Beibehalten zu erzeugen.

Wikipedia KV Diagramm

Translated version (Google translator)

I though maybe you can do this backwords: You fold the map and see which "1" are aboth each other. With folding I mean: Alternating taking the x and y middle axis and folding the map. If there are two "1" aboth each other they create a group.

But what are you doing after the second folding? For example:

becomes

0000
0110

after the first folding. Correct, no groups. But if I fold it a second time I get a wrong group. So how can I differentiate this case from for example this one:

-> fold x

1001
1001

-> fold y

20
20

Now there two "1" aboth each other (i wrote it as a 2). This creates a correct group after folding it 2 times.

Taking contextual cues into consideration, what you've presented as an example looks like a Karnaugh map, but it's far from clear what you're trying to do with it in terms of "simplification." It's not clear what you mean by fold, either, but it doesn't look like a sensible operation, as far as Karnaugh maps go. — shinobi, Jun 18 '17 at 08:51
I edited the question. I hope now its easier to understand. I am sorry that the Link links to the german wikipedia site but at the english one i was not able to find this information. — leet, Jun 18 '17 at 09:58
I see. Perhaps you could average the cell sums after each fold -- this way, you have a group only if the average is 1. In your spurious case, for instance, non-zero averages would be 0.5 from the first fold on. — shinobi, Jun 18 '17 at 12:00
...on a second thought, you may also pull out the 1-s that don't double after a fold, and add their corresponding expressions to the result -- e.g. in your first case, upon the first fold you will be forced to pull the two 1-s out of the map, and add them to the result as something like (~A)B(~C)D + ABCD. — shinobi, Jun 18 '17 at 12:09
But I cant pull out the 1-s if they do not form a group, because maby after the second fold they form a group. Like in the second example. — leet, Jun 18 '17 at 22:18
True. As I'm thinking of it, the Wikipedia page proposes "folding" as an alternative to grid adjacency -- i.e. you "fold" the grid in order to observe that a certain group of 1-s "holds together". In the simple case with up to 4 vars, this would roughly correspond to the observation of an "island" of 1-s. This looks like a simple aid to *manual* processing in the case with 5+ vars -- in automated processing, you can work on the "true" grid with one dimension per var and detect common patterns like rows/planes/blocks of 1-s. — shinobi, Jun 19 '17 at 08:47
There is a nice [online application](http://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/karnaughmap/) available to experiment with functions and diagrams with more than four variables. An extended explanation of such `Mahoney` diagrams can be found [here](http://davidbonal.com/karnaugh-and-mahoney-map-methods-for-minimizing-boolean-expressions/). — Axel Kemper, Jun 19 '17 at 22:59

Algorithm to simplify kv map with more than 4 variables

0 Answers0