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\$

2 Answers 2

Reset to default
6
\$\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\$
2
  • \$\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\$ Commented Feb 6, 2013 at 13:29
  • \$\begingroup\$ How should we approach these not-so-obvious "find minimum nand/nor gates" implementation questions? Does it come only through experience or are there rules/clues that we need to note/remember? TIA. \$\endgroup\$ Commented Mar 3, 2024 at 16:36
5
\$\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\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.