3

How to simplify a given boolean expression with many variables (>10) so that the number of occurrences of each variable is minimized?

In my scenario, the value of a variable has to be considered ephemeral, that is, has to recomputed for each access (while still being static of course). I therefor need to minimize the number of times a variable has to be evaluated before trying to solve the function.

Consider the function

f(A,B,C,D,E,F) = (ABC)+(ABCD)+(ABEF)

Recursively using the distributive and absorption law one comes up with

f'(A,B,C,E,F) = AB(C+(EF))

I'm now wondering if there is an algorithm or method to solve this task in minimal runtime.

Using only Quine-McCluskey in the example above gives

f'(A,B,C,E,F) = (ABEF) + (ABC)

which is not optimal for my case. Is it save to assume that simplifying with QM first and then use algebra like above to reduce further is optimal?

user2722968
  • 13,636
  • 2
  • 46
  • 67
  • The Google term is "fanout minimization". There are algorithms to design fanout-free circuits where every literal does not occur more than once. However, this is only possible for special boolean expressions. – Axel Kemper Aug 27 '13 at 20:35

3 Answers3

1

I usually use Wolfram Alpha for this sort of thing.

500 - Internal Server Error
  • 28,327
  • 8
  • 59
  • 66
-1

Try Logic Friday 1

It features multi-level design of boolean circuits.

For your example, input and output look as follows:

enter image description here

Axel Kemper
  • 10,544
  • 2
  • 31
  • 54
  • I'm looking for an algorithm or method since i need to implement it into code. The result Z as shown above is not optimal for my case as A and B are evaluated twice – user2722968 Aug 28 '13 at 18:21
  • Look at the circuit depicted in the image. A general algorithm beyond heuristics is not known to me. You might ask Google for "Reduced Binary Decision Diagrams". http://en.wikipedia.org/wiki/Binary_decision_diagram – Axel Kemper Aug 28 '13 at 20:33
  • Reading papers on fanout and bdds, this seems to be the general answer I was looking for, thanks. – user2722968 Aug 29 '13 at 18:52
  • @user2722968 If you plan to implement this yourself you want to (at the very least) read chapter 8 in *Synthesis and Optimization of Digital Circuits* by Giovanni De Micheli. The theory of multi-level minimization is far less simple than that of two-level minimization. – Fizz Feb 13 '15 at 06:42
  • Also chapter 11 in *Logic Synthesis and Verification Algorithms* by Hachtel and Somenzi. – Fizz Feb 13 '15 at 07:24
  • If you want something more "state of the art" rather than widely used in industry see http://alcom.ee.ntu.edu.tw/publications/iccad07-fd.pdf or http://www.eecs.berkeley.edu/~alanmi/publications/2008/iccad08_lp.pdf Multi-level optimization is still an active research area. – Fizz Feb 13 '15 at 07:39
-1

You can use an online boolean expression calculator like https://www.dcode.fr/boolean-expressions-calculator

You can refer to Any good boolean expression simplifiers out there? it will definitely help.

Hemant Singh
  • 1,487
  • 10
  • 15
  • I'm looking for an implementation, so an algorithm is being looked for – user2722968 Jun 23 '18 at 17:28
  • then you can go through Karnaugh Map Boolean Algebra Simplification Technique https://www.allaboutcircuits.com/textbook/digital/chpt-8/logic-simplification-karnaugh-maps/ Let me know if it helps – Hemant Singh Jun 23 '18 at 17:37