How to use de morgan and other laws to reduce expression - Mux

[ouverson]

Greetings!

I used the Mux Truth Table to derive the Canonical Representation:

(NOT(sel) AND a AND NOT(b)) OR (NOT(sel) AND a AND b) OR (sel AND NOT(a) AND b) OR (sel AND a AND b)

I was able to use this expression to generate the gate diagram and subsequent HDL; and got a "Comparison ended successfully" message - yeah!

However, I'm sure there's an implementation using fewer than 3 NOT, 8 AND and 3 OR gates!

It would be nice to reduce this as far as possible using algebraic laws such as Commutative, Associative, Distributive, De Morgans, Idempotence, Double Negation, etc.

I would appreciate if someone could help me understand how to go about this task.

[WBahn]

The normal way to reduce expressions like this is with Karnaugh maps, which are just a visual way to identify certain Boolean algebraic simplification.

The primary one is

X·Y + X·Y' = X·(Y+Y') = X·1 = X

Using that identity, you should be able to reduce your logic to 1 NOT, 2 AND, and 1 OR.

For Nand2Tetris, this is perfectly fine.

But if you are trying to really understand logic minimization, then the following might be of interest to you.

While this NOT/AND/OR implementation might appear to be very simple, in fact it isn't as simple as it could be. The reason is that AND and OR gates (in CMOS) have more transistors and longer propagation delays than NAND and NOR gates. The "simplified" circuit has 20 transistors and 5 gate delays. It can be converted to 1 NOT and 3 NAND gates which only needs 14 transistors and 3 gate delays. A "gate delay" is the propagation delay through a NOT gate.

Even this can be improved upon with a direct transistor-level CMOS implementation that can get it down to either 14 transistors with 2 gate delays or 12 transistors with 3 gate delays. A transmission-gate implementation can do it with only 6 transistors and two gate delays, but introduces signal coupling between input and output, which is often not desirable and at the very least complicates circuit verification.

[ouverson]

With the help of the "Boolean algebraic simplification" I was able to reduce my canonical representation to 1 Not, 2 And and 1 Or.

Thank you so much for your help and for sharing additional gate design and construction details.

[WBahn]

Glad you found it useful.

To use Boolean algebra to get to a simpler NAND-based solution, we can use the fact that

A NAND B = (A·B)'

and then DeMorgan to recognize that

A OR B = A+B = ((A')(B'))'

With this, you can quickly determine that

Y = (A·B) + (C·D)

is equivalent to

Y = ( (A·B)' · (C·D)' )'

which is

Y = (A NAND B) NAND (C NAND D)

Adding a NOT gate then finished the implementation of the MUX.

[ouverson]

You said:

A OR B = A+B = ((A')(B'))'

Is that correct?