Re: Algorithm to generate boolean function by using Karnaugh map

From: Carl W. (NoEmail_at_hp.com)
Date: 09/30/04 

Date: Thu, 30 Sep 2004 19:11:44 GMT

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.

Relevant Pages

  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (comp.games.development.programming.algorithms)
  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (sci.math)
  • Re: a circumference is a function?
    ... no; it is a circle. ... "graph" of a function. ... The key word here is "valid". ... A real function of real variable is one in which every valid input is ...
    (sci.math)
  • Re: need help with homework
    ... Good intuition as a starter. ... base is a circle then we have a circular cylinder. ... If you have a graph of a function, you make a rule as follows: ...
    (sci.math)
  • Re: Data points for line graph.
    ... > I'm working on a graph with 7 lines. ... > in square, filled in circle, etc.) for each line. ... Charts with Picture Markers ...
    (microsoft.public.powerpoint)
Quantcast