Maker Pro
Maker Pro

Algorithm to generate boolean function by using Karnaugh map

E

Eric K.

Jan 1, 1970
0
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.
 
J

John Duffus

Jan 1, 1970
0
Eric K. said:
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.

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

John Providenza

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

John P
 
E

Eric K.

Jan 1, 1970
0
Thanks JD. But the requirment is to use K-Map using Java.
 
J

Jim Thompson

Jan 1, 1970
0
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.

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

...Jim Thompson
 
E

Eric K.

Jan 1, 1970
0
Thanks, John. But how to do it using KMAP as it is required?
 
C

Carl W.

Jan 1, 1970
0
Eric said:
Thanks, John. But how to do it using KMAP as it is required?

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
gate lead) solution.

Thanks,
Carl W.
 
E

Eric K.

Jan 1, 1970
0
Jim Thompson said:
Simply buy KMAP v4.4.5, 3,4, or 5-variable.

...Jim Thompson

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

Jim Thompson

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

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

...Jim Thompson
 
F

Frithiof Andreas Jensen

Jan 1, 1970
0
Eric K. said:
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.

Quine-McCluskey is the Google word:
http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/ , http://freshmeat.net/projects/qmls/
 
B

Bert Cuzeau

Jan 1, 1970
0
Eric said:
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.

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

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

Bert Cuzeau
 
Top