# Algorithm to generate boolean function by using Karnaugh map

Discussion in 'Electronic Design' started by Eric K., Sep 30, 2004.

1. ### Eric K.Guest

I am developing a program in Java to generate a boolean function by
using k-map with 4 variables. So from the 4-variable map with 16
cells, user can input 1 or 0 in each cell. Then the program will
generate the simplied boolean function according to the map.

Basically I don't know the algorithm on how to group the "1"s and then
how to simplify it. Please advise. Or let me know if you have/know any
such code that I can learn from.

2. ### John DuffusGuest

Have you checked out the Quine-McCluskey tabulation method? It is very
suitable for programming.
JD

3. ### John ProvidenzaGuest

I believe 'Embedded System Journal' had a goo article on the
Quine--McCluskey method. It was a month or two ago.

John P

4. ### Eric K.Guest

Thanks JD. But the requirment is to use K-Map using Java.

5. ### Jim ThompsonGuest

Simply buy KMAP v4.4.5, 3,4, or 5-variable.

...Jim Thompson

6. ### Eric K.Guest

Thanks, John. But how to do it using KMAP as it is required?

7. ### Carl W.Guest

As I remember (it's been years), the Q-M algorithm finds
all the 1-cubes, which is equivalent to circling every 1 in
the graph (it does something with don't-cares, too). Then,
it circles every 2-cube, which is every pair (as you would
circle them) on the Karnaugh map. It doesn't matter if
the '1' or 'X' is covered by another 2-cube already, it
circles it. I think then it does the 3-cubes (4-way squares
on the K-map) and 4-cubes, on up until it can't circle anything
bigger.

Then it chooses the minimal set of 1,2,3,4,etc.-cubes
which covers the graph. To cover the graph, you have to
have circles which cover all 1's, don't cover any 0's and
we don't care if they cover X's.

So, my guess is that you'd want to use the circling part
of Q-M hidden from the user , then figure out the minimal
set of cubes (hmm, I guess Q-M prefers the top cubes first),
then circle the graphical K-map in such a way that you can
lie to the user when your program prints "It's intuitively
obvious that this is the least cost function" .

A simple example of a K-map which shows the need to
use the Q-M "minimum set of cubes which cover the graph"
is this:

1 1 0 0
0 1 1 0
0 0 1 1
0 0 0 0

If you circle the pairs horizontally, you get 3 2-cubes.
If you circle them vertically first, then circle the
horizontal pairs, you get 4 2-cubes required to cover
the map. 3 2-cubes is typically the better (minimal

Thanks,
Carl W.

8. ### Eric K.Guest

I want to code it by myself but the program package doesn't include
any source code I think. Only executible files...

9. ### Jim ThompsonGuest

Then you need to get a grip on the Quine-McCluskey method or
effectively decode Karnaugh maps with a software scheme.

...Jim Thompson

10. ### Frithiof Andreas JensenGuest

http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/ , http://freshmeat.net/projects/qmls/

12. ### Bert CuzeauGuest

Berkeley's espresso maybe ? (afaik, the name came well before Java

Google on "espresso logic reduction" seems to bring interesting pointers.

Bert Cuzeau