CODEWITHSUNDEEP
algorithmboolean-logicminimization
Hexaneat
Hexaneat

Reputation: 41

Is there an algorithm for multi-level logic minimization?

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.

Upvotes: 4

Views: 654

Answers (1)

Y.T.
Y.T.

Reputation: 2739

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.

Upvotes: 0

Related Questions