3
\$\begingroup\$

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)?

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'd been staring at the problem so long I'd lost sight of how simple the solution could be. Now that I know, the answer seems so obvious that I wonder how I could have missed it. Thanks so much for your help. \$\endgroup\$ – Ben D. Feb 6 '13 at 13:29
4
\$\begingroup\$

As Dave Tweed notes, the same 4-gate circuit may be used for NAND and NOR gates; it's worth noting, however, that the 4-gate multiplexer will not have a glitch-free output if the select input changes and both inputs are the same style (NAND vs NOR). A glitch-free mux design would use an extra gate tied to the two data inputs, and the final gate would take the input from that extra gate and from the other two gates that use the data inputs.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.