4

I need an algorithm that, when given any number of boolean expressions, with any number of variables, can do multi-level logic minimization to give a set of boolean functions.

Wikipedia briefly mentions multi-level representations and gives an example, but doesn't explain how to do it, and I can't find it anywhere else either.

Edit: to clarify, it needs to work on systems with multiple outputs, merging parts of the outputs' boolean expressions to minimize the number of required logic gates.

Wikipedia gives the following example:

F1 = AB + AC + AD

F2 = A`B + A`C + A`E

A functionally equivalent multilevel representation can be:

P = B + C

F1 = AP + AD

F2 = A`P + A`E

This reduces the number of logic gates required by reusing B + C.

I'm looking for an algorithm to do this with any number of inputs and outputs and produce the a functionally equivalent multilevel representation with the minimum possible number of logic gates. Apologies if any of my terminology was/is off.

Nathan Comer
  • 41
  • 4
  • Have you seen [this](https://stackoverflow.com/a/14903316/1911064) related post? – Axel Kemper Nov 06 '22 at 01:42
  • do you mean something like [Karnaugh Maps](https://stackoverflow.com/a/24054153/2521214) ? – Spektre Nov 06 '22 at 06:04
  • On an interesting note: Nvidia is now successfully using Reinforcement Learning to create improved 64-bit adders and similar circuits beating the existing approaches and heuristic algorithms: https://developer.nvidia.com/blog/designing-arithmetic-circuits-with-deep-reinforcement-learning http://www.sci.utah.edu/publications/Roy2021a/PrefixRL_Optimization_of_Parallel_Prefix_Circuits_using_Deep_Reinforcement_Learning.pdf One would believe that adder circuits are solved after 92 years of carry-lookahead adders (https://en.wikipedia.org/wiki/Carry-lookahead_adder) – Sebastian Nov 06 '22 at 11:07
  • But especially the middle digits of the result are quite involved. – Sebastian Nov 06 '22 at 11:08
  • (Interestingly, the wikipedia article doesn't expand on the 24 transistor solution, and doesn't state the number of transistors using the shared expression. I am severely out of practice, but I get two transistors *more* - not saying CSE is detrimental at the switch level, but thinking the example too small.) – greybeard Nov 07 '22 at 06:14
  • @greybeard If you want to minimize on transistor/switch level - and not just the boolean expression - you have to specify the process to know, which circuits can be realized with how many transistors, e.g. NOR, NAND, NOT, how many inputs are possible, how many outputs (fanout) due to line capacity (it would also depend on the length of the lines, the used frequency and voltage, the size of the transistors). In practice you would not only want to minimize the transistor count at all costs, but also limit the overall delay and also consider, how to place the transistors in a nice rectangle. – Sebastian Nov 07 '22 at 06:47
  • 1
    (@Sebastian I earned my pay programming IC design tools in the 1980s.) – greybeard Nov 07 '22 at 06:59
  • @greybeard If you find the time, I would love to hear about your experiences and typical methods. Perhaps you could write some sentences. – Sebastian Nov 07 '22 at 07:17
  • 1
    I believe espresso can handle these sorts of problems. See: https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer – alias Nov 08 '22 at 21:10

1 Answers1

0

I believe what you want is Quine-McCluskey algorithm, which has an exponential complexity. The idea is to generate a truth table and combine minterms. The linked wikipedia provides a clear explanation on how the algorithm works.

TYeung
  • 2,579
  • 2
  • 15
  • 30
  • As I understand it, the Quine-McCluskey algorithm takes one boolean function and minimizes it. What I need is something that works on any number of boolean functions (so that the system as a whole has multiple outputs). I've edited the question to clarify. Thanks. – Nathan Comer Nov 06 '22 at 17:19
  • If you have multiple number of boolean functions, then you can run Quine-McCluskey algorithm multiple times. – TYeung Nov 06 '22 at 23:50
  • So the idea is to run all functions through the Quine-McCluskey algorithm and look for shared parts? After simplifying Wikipedia's example, we can see that both functions contain the substring "B + C", which is exactly the logic we need to extract to another function. But would the Quine-McCluskey algorithm ever give results where the reusable parts of the functions aren't identical substrings of the two simplified functions? If so, how would we see that the functions share some logic which we can extract? If not, we should be able to just scan both simplified functions for shared substrings. – Nathan Comer Nov 07 '22 at 03:10
  • @NathanComer Then your question is more difficult than I thought. – TYeung Nov 08 '22 at 03:38