Forums

Boolean Algebra / Karnaugh Maps with N > 2 (Higher Dimensions)

Started by David T. Ashley December 30, 2006
Most who inhabit this list are probably familiar with standard Boolean
algebra and Karnaugh maps, i.e.

http://en.wikipedia.org/wiki/Karnaugh

Karnaugh maps come up very frequently in the design of microcontroller
software, i.e. on a processor that handles bitfields very efficiently, one
might even implement a 3-state state machine as something like:

if (!x.bf1)
   {
   if (!x.bf0)
      {
      /* 0/0 logic, First State */
      }
   else
      {
      /* 0/1 logic, Second State */
      }
   }
else
   {
   /* 1/X logic, Third State */
   }

However, it also occurs frequently that an integer range (x, 0-255, say) is
"paneled" into smaller pieces of significance (0-10, 11-67, and 68-255,
say), and this can lead to truth tables that are a mixture of these
"paneled" ranges and Boolean values.  The simplest example would be a table
with 3 columns (corresponding to the three ranges above), and two rows (y,
one for F, one for T).

i.e.
  | 0-10 | 11-67 | 68-255
F | 1    | 1     |  0
T | 0    | 1     |  0

In "reducing" a 3 x 2 table like this, one could easily end up with a
Boolean-valued function like:

(!y && x<=67) || (x>=11 && x<=67)

Is there an algebra (similar to Boolean algebra) or a way of thinking that
would allow one to freely mix "Boolean" values and "paneled" values and have
some way of reducing functions, similar to a Karnaugh map with more
dimensions?

Thanks.
------------------------------------------------------------
David T. Ashley              (dta@e3ft.com)
http://www.e3ft.com          (Consulting Home Page)
http://www.dtashley.com      (Personal Home Page)
http://gpl.e3ft.com          (GPL Publications and Projects) 


 Its academic , i let the CPU do all this at microsecond speeds .

  How fast are you at Carnaugh ?

  There is no money in teaching computers , because if the
computer is to be useful , it must not require humans to
 write its code .


   I have demonstrated many times , the method of forcing to
 OpSys to create the algorithms .....

David T. Ashley wrote:

> However, it also occurs frequently that an integer range (x, 0-255, say) is > "paneled" into smaller pieces of significance (0-10, 11-67, and 68-255, > say), and this can lead to truth tables that are a mixture of these > "paneled" ranges and Boolean values. The simplest example would be a table > with 3 columns (corresponding to the three ranges above), and two rows (y, > one for F, one for T). > > In "reducing" a 3 x 2 table like this, one could easily end up with a > Boolean-valued function like:
Uhuh (looks up, down, and around to see if a trick question is about to drop on my head or run me over).... maybe I missed something really significant, but you apparently answered your own question implicitly with the little piece of C you gave. What is (V > 10) if not a Boolean result? Instead of thinking about this as a single Boolean input A and a binary variable V that can lie in one of three possible "panels" of interest, you should think about this as a single Boolean input (from your original problem/circuit), and two additional Boolean inputs, which I'll call C and D. C = 1 iff (v is an element of {0..10}) D = 1 iff (v is an element of {11..67}) [Note there is an implicit third state where C=D=0, i.e. v > 67]. You now have a vanilla three-input K-map with inputs V, C and D. Once you reduce this to a Boolean expression, you can substitute the appropriate numeric comparisons: C = (V <= 10) (implies D') C' = (V > 10) (implies D=X) C'D = (V > 10 && V < 68) D' = (V < 11 || V > 67) C'D' = (V >= 68) (CD) = impossible (Hey, I never thought I would use a K-map again, I guess that wasn't time wasted at college after all).
"larwe" <zwsdotcom@gmail.com> wrote in message 
news:1167510464.459609.231260@v33g2000cwv.googlegroups.com...
> > David T. Ashley wrote: > > Instead of thinking about this as a single Boolean input A and a binary > variable V that can lie in one of three possible "panels" of interest, > you should think about this as a single Boolean input (from your > original problem/circuit), and two additional Boolean inputs, which > I'll call C and D. > > C = 1 iff (v is an element of {0..10}) > D = 1 iff (v is an element of {11..67}) > [Note there is an implicit third state where C=D=0, i.e. v > 67]. > > You now have a vanilla three-input K-map with inputs V, C and D. Once > you reduce this to a Boolean expression, you can substitute the > appropriate numeric comparisons: > > C = (V <= 10) (implies D') > C' = (V > 10) (implies D=X) > C'D = (V > 10 && V < 68) > D' = (V < 11 || V > 67) > C'D' = (V >= 68) > (CD) = impossible
The technique you proposed works ... I was hoping for some kind of a very general result or a very general way of thinking ... I have this feeling ... maybe too much caffeine or maybe I misread the expiration date on that chicken in my fridge ... that there are some optimizations that could be performed better with a more general way of thinking. For example, in Boolean algebra, ((x == FALSE) OR (x == TRUE)) == TRUE, or more compactly, (x OR !x) = 1 Similarly, in the "paneled" math, ((x <= 10) OR (x >= 11 AND x <= 67) OR (x >= 68)) = TRUE Also, (! ((x <= 10) OR (x >= 68))) = (x >=11 AND x <= 67) (very similar in spirit to De Morgan's theorem) I was just wondering if there was some more general way of thinking about it all. Something like a higher-dimensional Karnaugh map. Dave.
David T. Ashley wrote:

> I was just wondering if there was some more general way of thinking about it > all. Something like a higher-dimensional Karnaugh map.
It seems to me that any heuristic you could devise for working with these fuzzy logic type expressions (which is what they are, by the way) would ultimately reduce to something very much the same as what I described.
David T. Ashley wrote:
> I was hoping for some kind of a very general result or a very general way of > thinking ... I have this feeling ... maybe too much caffeine or maybe I > misread the expiration date on that chicken in my fridge ... that there are > some optimizations that could be performed better with a more general way of > thinking.
That funny feeling you describe is the one you get right before you make a wonderful new discovery, but I'm afraid you have to figure out what it is yourself. ...or else switch to decaf. ;^) Personally, anything that takes K-maps beyond much beyond 4 inputs seems to be stretching the tool beyond what it does well until I get N-dimensional paper to doodle them on. - Tim.