Electronic – the minimum number of NOR gates needed to implement a 2-input multiplexer

digital-logicmultiplexer

In the first chapter of The Elements of Computing Systems, the reader is asked to implement basic logic gates like Not, And, Or, Xor, as well as a 2-input multiplexer and de-multiplexer. The authors instruct the reader to build their gates using the universal NAND gate as a basis.

I am able to build all of the requested gates using NAND gates without issue. Using truth tables and DeMorgan's law, I have minimized the gates as much as possible (e.g. Xor can be minimally represented using only 4 NAND gates, as can a 2-input Mux chip).

For the sake of rigor, I decided to build the gates using the other universal gate: NOR. In doing so, I noticed that NAND and NOR representations are pretty much tied in terms of complexity. For example, And gates require 2 NAND gates or 3 NOR gates, but this is countered by Or gates needing 2 NOR gates or 3 NAND gates.

For the 16 boolean functions that exist for 2 inputs, NAND and NOR end up tied. Neither gate is superior in terms of minimizing complexity. However, this doesn't seem to hold when building the Mux chip.

I can build the Mux chip in 4 NAND gates. The de-multiplexer (DMux) chip can be built in either 5 NAND gates or 4 NOR gates. My brain's pattern-recognition wants so very badly to think that the Mux chip must have a NOR representation in only 5 gates, thus making Mux and DMux another set of tied pairs leaving NAND and NOR gates tied once again.

But try as I may, I cannot find a way to implement a Mux chip in any fewer than 7 NOR gates.

Am I missing some minimization trick (as with masks in NAND-Xor or NOR-Xnor)?

Best Answer

You can build the mux with 4 NOR gates, too. It doesn't require extra inverters on the inputs and outputs, if that's what you were doing. Note that the sense of the "select" input is inverted, so you need to swap the "A" and "B" inputs to compensate.