Skip to main content
P
ptc-27846521-Visitor
1-Visitor
August 2, 2010
Question

Are there any Boolean simplification resources for Mathcad?

  • August 2, 2010
  • 1 reply
  • 3781 views

Are there any Mathcad resources for symbolic Boolean simplification?

I am thinking truth table methods using karnaugh mapping with automated simplification, or reed-muller simplification. There are many programs that handle 8 variables, I have a need for more than 8 variables.

Many available methods give results in sum of products or product of sums, that were often used for circuit deign, but can often improved upon for computer programs. For example, xor reduces "(~a & b ) or (a & ~b)" to "a xor b" and factoring by the distribution law can reduce the number operations form the number of distributed terms to one operation on the factored term.

For this reason I would also like to find xor reduction and factoring for Mathcad.

Thanks, JS

1 reply

J
jeanGiraud1-Visitor
1-Visitor
August 3, 2010

You can probably start here: http://communities.ptc.com/message/148962#148962

P
ptc-27846521-VisitorAuthor
1-Visitor
August 3, 2010

I'm not really dealing with inequalities as much as Boolean expressions. This is the sort of thing I am simplifying (in this case, sum of products form.)

To demystify what I am doing here, the first formulations are a permutative state space description of the survival of a cell in the "Game of Life"cellular automata. The second is modeling a simple, specialized counter for the same purpose. I was surprised that the first formulation did not lead to the simplest possible formulation, but on reflection that what we have here is a distant relative to the collapse of the probability function in quantum mechanics. Wild possibilities disappear into nothingness if we sequentially approach a solution...chuckle. It also shows the optimization routines I was using are either suboptimal or can't weed out some kinds of redundant cases.

L = C' a' b' c' d' e' f g j + C' a' b' c' d' e f' g j + C' a' b' c' d' e f g' j + C' a' b' c' d' e f g j' + C' a' b' c' d e' f' g j + C' a' b' c' d e' f g' j + C' a' b' c' d e' f g j' + C' a' b' c' d e f' g' j + C' a' b' c' d e f' g j' + C' a' b' c' d e f g' j' + C' a' b' c d' e' f' g j + C' a' b' c d' e' f g' j + C' a' b' c d' e' f g j' + C' a' b' c d' e f' g' j + C' a' b' c d' e f' g j' + C' a' b' c d' e f g' j' + C' a' b' c d e' f' g' j + C' a' b' c d e' f' g j' + C' a' b' c d e' f g' j' + C' a' b' c d e f' g' j' + C' a' b c' d' e' f' g j + C' a' b c' d' e' f g' j + C' a' b c' d' e' f g j' + C' a' b c' d' e f' g' j + C' a' b c' d' e f' g j' + C' a' b c' d' e f g' j' + C' a' b c' d e' f' g' j + C' a' b c' d e' f' g j' + C' a' b c' d e' f g' j' + C' a' b c' d e f' g' j' + C' a' b c d' e' f' g' j + C' a' b c d' e' f' g j' + C' a' b c d' e' f g' j' + C' a' b c d' e f' g' j' + C' a' b c d e' f' g' j' + C' a b' c' d' e' f' g j + C' a b' c' d' e' f g' j + C' a b' c' d' e' f g j' + C' a b' c' d' e f' g' j + C' a b' c' d' e f' g j' + C' a b' c' d' e f g' j' + C' a b' c' d e' f' g' j + C' a b' c' d e' f' g j' + C' a b' c' d e' f g' j' + C' a b' c' d e f' g' j' + C' a b' c d' e' f' g' j + C' a b' c d' e' f' g j' + C' a b' c d' e' f g' j' + C' a b' c d' e f' g' j' + C' a b' c d e' f' g' j' + C' a b c' d' e' f' g' j + C' a b c' d' e' f' g j' + C' a b c' d' e' f g' j' + C' a b c' d' e f' g' j' + C' a b c' d e' f' g' j' + C' a b c d' e' f' g' j' + C a' b' c' d' e' f' g j + C a' b' c' d' e' f g' j + C a' b' c' d' e' f g j' + C a' b' c' d' e' f g j + C a' b' c' d' e f' g' j + C a' b' c' d' e f' g j' + C a' b' c' d' e f' g j + C a' b' c' d' e f g' j' + C a' b' c' d' e f g' j + C a' b' c' d' e f g j' + C a' b' c' d e' f' g' j + C a' b' c' d e' f' g j' + C a' b' c' d e' f' g j + C a' b' c' d e' f g' j' + C a' b' c' d e' f g' j + C a' b' c' d e' f g j' + C a' b' c' d e f' g' j' + C a' b' c' d e f' g' j + C a' b' c' d e f' g j' + C a' b' c' d e f g' j' + C a' b' c d' e' f' g' j + C a' b' c d' e' f' g j' + C a' b' c d' e' f' g j + C a' b' c d' e' f g' j' + C a' b' c d' e' f g' j + C a' b' c d' e' f g j' + C a' b' c d' e f' g' j' + C a' b' c d' e f' g' j + C a' b' c d' e f' g j' + C a' b' c d' e f g' j' + C a' b' c d e' f' g' j' + C a' b' c d e' f' g' j + C a' b' c d e' f' g j' + C a' b' c d e' f g' j' + C a' b' c d e f' g' j' + C a' b c' d' e' f' g' j + C a' b c' d' e' f' g j' + C a' b c' d' e' f' g j + C a' b c' d' e' f g' j' + C a' b c' d' e' f g' j + C a' b c' d' e' f g j' + C a' b c' d' e f' g' j' + C a' b c' d' e f' g' j + C a' b c' d' e f' g j' + C a' b c' d' e f g' j' + C a' b c' d e' f' g' j' + C a' b c' d e' f' g' j + C a' b c' d e' f' g j' + C a' b c' d e' f g' j' + C a' b c' d e f' g' j' + C a' b c d' e' f' g' j' + C a' b c d' e' f' g' j + C a' b c d' e' f' g j' + C a' b c d' e' f g' j' + C a' b c d' e f' g' j' + C a' b c d e' f' g' j' + C a b' c' d' e' f' g' j + C a b' c' d' e' f' g j' + C a b' c' d' e' f' g j + C a b' c' d' e' f g' j' + C a b' c' d' e' f g' j + C a b' c' d' e' f g j' + C a b' c' d' e f' g' j' + C a b' c' d' e f' g' j + C a b' c' d' e f' g j' + C a b' c' d' e f g' j' + C a b' c' d e' f' g' j' + C a b' c' d e' f' g' j + C a b' c' d e' f' g j' + C a b' c' d e' f g' j' + C a b' c' d e f' g' j' + C a b' c d' e' f' g' j' + C a b' c d' e' f' g' j + C a b' c d' e' f' g j' + C a b' c d' e' f g' j' + C a b' c d' e f' g' j' + C a b' c d e' f' g' j' + C a b c' d' e' f' g' j' + C a b c' d' e' f' g' j + C a b c' d' e' f' g j' + C a b c' d' e' f g' j' + C a b c' d' e f' g' j' + C a b c' d e' f' g' j' + C a b c d' e' f' g' j';
I managed a couple of levels of simplification. Here is my an intermediate result that has been optimized and factored.

L = d' e' (f (a' b' c' g j + g' j' (C a c' + a' b c)) + f' (a' b c (g j' + g' j) + C a (c' g j' + g' (j' (c + b) + c' j)))) + a' (b' c' d e (f' g' j + j' (f g' + f' g)) + (d e f' g' j' + d' e' (f g j' + j (f g' + f' g)) + (f' g' j + j' (f g' + f' g)) (d e' + d' e)) (b c' + b' c)) + (C a c' f' g' j' + a' (b c f' g' j' + b' c' (f g j' + j (f g' + f' g)))) (d e' + d' e) + (b c d' e' f' g' j' + b' c' (d e f' g' j' + d' e' (f g j' + j (f g' + f' g)) + (f' g' j + j' (f g' + f' g)) (d e' + d' e)) + (d' e' f g' j' + f' (d' e' g j' + g' (d' e' j + j' (d e' + d' e)))) (b c' + b' c)) (a + C);

But I know that theory tells me that I have at least 8 or 9 more xor operations that can be applied to this expression and that each almost certain to reduce the number of boolean operations.
I was not able to easily go further so I explored another method and was able to reformulate the expression with different variables to find a simple iterative pattern that would give me L. But this too is not the final answer.
(Of course the following will not actually work in Mathcad because of limitations in Mathcad's symbolic handling, but it makes logical sense...if anyone knows any resource to work on these sort of problems symbolically, please let me know. I can't use hashing as these calculations are going to be inseparable from the underlying monolithic structure.)
itercalc.PNG
All the S variables can, in principle, be eliminated leaving only the dependencies on N and C. THAT, optimized as POS, then xor reduced and then factored is as good as I can probably expect.
So again, if anyone knows of some Mathcad resources that would help with these kind problem, thanks ahead of time.
-jks
P
ptc-27846521-VisitorAuthor
1-Visitor
August 8, 2010

I have a correction to my last response. The final equation is not correct, because I assumed a "don't care" state in the truth table that must have the value of true in order to work.

This changes the last S4 assignment. I found this error when I actually wrote a quick and dirty program in Squeak Smalltalk. It works fine once I got the truth table debugged. I intend to look into writing it again for Mathcad using image processing just for fun.

Here is the actual code from Smalltalk. It shows the power of a real Object Oriented language as I implemented Boolean operations which operate on 1000x1000x1 bit map images using BitBlt operations. Here is the actual logic code which works correctly. It is not optimized so I am looking to minimize the number of Boolean operations, each of which operates on a million pixels in parallel. The speed is not great. I get about 8 generations per second on my lap top. But that is with no optimization, and I know I can make it much faster just by cashing object instances and working with profiling. I have demonstrated speeds 10 times as great in a Bitblt loop test. Also,there are lots of opportunities to optimize it. Not only that, if I get access to the 70+ Graphic Processing Units on my high end graphics card through Open GL or some such the I can get some real speed.

At present I do 50+ BitBlts per generation. That is more than 50 million brute force bit Boolean operations per Life generation whether any state changes or not, like in empty space. Golly using HashLife, sometimes can get 10^7 generations per second using a very sophisticated hashing scheme.

Below is the code for the main execution loop which carries out the complete of the Game of Life logic as Boolean operations. It is quite impressive once you understand each variable actually holds a million bits, each of which is operated on in parallel in the Boolean operations. Clearly there is more optimization to be had. For example the first time through the loop all the boolean operations are unnecessary as they are operating on zero value 2D space meshes.

Capture.PNG

You could use infix operations in Mathcad in a way to do this kind of thing to some extent.

Terms & ConditionsAccessibility statement