Connect with us

Algorithm to generate boolean function by using Karnaugh map

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

Scroll to continue with content
  1. Eric K.

    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 Duffus

    John Duffus Guest

    Have you checked out the Quine-McCluskey tabulation method? It is very
    suitable for programming.
    JD
     
  3. 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.

    Eric K. Guest

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

    Jim Thompson Guest

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

    ...Jim Thompson
     
  6. Eric K.

    Eric K. Guest

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

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

    Thanks,
    Carl W.
     
  8. Eric K.

    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 Thompson

    Jim Thompson Guest

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

    ...Jim Thompson
     
  10. Quine-McCluskey is the Google word:
    http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/ , http://freshmeat.net/projects/qmls/
     
  11. Fred Bloggs

    Fred Bloggs Guest

  12. Bert Cuzeau

    Bert Cuzeau Guest

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

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

    Bert Cuzeau
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-