Algorithm to generate boolean function by using Karnaugh map

Eric K. · Apr 27, 2005

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.

Frithiof Andreas Jensen · Apr 27, 2005

"Eric K." <usgog@yahoo.com> wrote in message
news:80d6ba74.0409292157.5edd2bbb@posting.google.com...

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/

Fred Bloggs · Apr 27, 2005

Frithiof Andreas Jensen wrote:

Quine-McCluskey is the Google word:

Nah- it is better to go with algorithm karnaugh map simplification. Then
you get something more basic like :
http://www.cs.unco.edu/KARNAUGH/Algorithm.html

Bert Cuzeau · Apr 27, 2005

Eric K. wrote:

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

John Providenza · Apr 27, 2005

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

John P

"John Duffus" <john_duffus@hotmail.com> wrote in message news:<0qO6d.143597$%S.44508@pd7tw2no>...

"Eric K." <usgog@yahoo.com> wrote in message
news:80d6ba74.0409292157.5edd2bbb@posting.google.com...
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

Eric K. · Apr 27, 2005

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

"John Duffus" <john_duffus@hotmail.com> wrote in message news:<0qO6d.143597$%S.44508@pd7tw2no>...

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

Jim Thompson · Apr 27, 2005

On 29 Sep 2004 22:57:21 -0700, usgog@yahoo.com (Eric K.) wrote:

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.

480)460-2350 | |
| E-mail Address at Website Fax

Eric K. · Apr 27, 2005

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

johnp3+nospam@probo.com (John Providenza) wrote in message news:<349ef8f4.0409300629.3d11561c@posting.google.com>...

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

John P

"John Duffus" <john_duffus@hotmail.com> wrote in message news:<0qO6d.143597$%S.44508@pd7tw2no>...
"Eric K." <usgog@yahoo.com> wrote in message
news:80d6ba74.0409292157.5edd2bbb@posting.google.com...
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

Carl W. · Apr 27, 2005

Eric K. wrote:

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.

Eric K. · Apr 27, 2005

Jim Thompson <thegreatone@example.com> wrote in message news:<af8ol0hj40gbqb1rolsncjrvh35oc5mcra@4ax.com>...

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...

Jim Thompson · Apr 27, 2005

On 30 Sep 2004 17:25:24 -0700, usgog@yahoo.com (Eric K.) wrote:

Jim Thompson <thegreatone@example.com> wrote in message news:<af8ol0hj40gbqb1rolsncjrvh35oc5mcra@4ax.com>...

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...

480)460-2350 | |
| E-mail Address at Website Fax

Algorithm to generate boolean function by using Karnaugh map

Eric K.

Guest

Frithiof Andreas Jensen

Guest

Fred Bloggs

Guest

Bert Cuzeau

Guest

John Providenza

Guest

Eric K.

Guest

Jim Thompson

Guest

Eric K.

Guest

Carl W.

Guest

Eric K.

Guest

Jim Thompson

Guest

Welcome to EDABoard.com

Sponsor

Online statistics

Forum statistics

Algorithm to generate boolean function by using Karnaugh map

Eric K.

Guest

Frithiof Andreas Jensen

Guest

Fred Bloggs

Guest

Bert Cuzeau

Guest

John Providenza

Guest

Eric K.

Guest

Jim Thompson

Guest

Eric K.

Guest

Carl W.

Guest

Eric K.

Guest

Jim Thompson

Guest

Log in

Welcome to EDABoard.com

Sponsor