[Solved]: Karnaugh map with don't care: increasing the number of groups instead of simplifying

Problem Detail: 

              AB         00  01  11  10          00 | x | 1 | 0 | 1 | CD  01 | 0 | 1 | x | 0 |     11 | 1 | x | x | 0 |     10 | x | 0 | 0 | x | 

The answer to the above Karnaugh map is $F(ABCD) = B D + \bar B \bar D + \bar A \bar C \bar D + \bar A C D$ according to my book and the K-map solvers online.

But what I don't get is that I can further reduce the terms in this answer: $F(ABCD) = \bar B \bar D + \bar A CD + \bar A B \bar C$ also covers all the min terms in lesser groups.

The answer in my book just has a bigger group covering additional don't cares. Since they are optional shouldn't my answer be correct?

Asked By : imhobo

Answered By : ZeroUltimax

Your answer is correct. It is also more reduced. The reason your book and the solver give you a bigger equation is because they use a greedy algorithm that attempts to match bigger groups (groups with less variable in them). This will have an optimal behavior if the map has no "don't cares" [reference needed].

To have optimal behavior with "don't care", you have to consider that an X can be either a 1 or a 0. That means that for each X, you have two versions of you map. So, if you have $N$ "don't cares", you will have to reduce the $2^N$ versions of the map and choose the smallest reduced operation from the results.

Extra

If you have lots of those maps to reduce, i suggest you use Logic Friday or a similar equation reducer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29164