2
\$\begingroup\$

I need to implement the following function en1 = (b4⊕b3⊕b2⊕b1⊕b0)' using the minimum number of NAND gates.

schematic

simulate this circuit – Schematic created using CircuitLab

How can I achieve the optimal implementation using the fewest possible NAND gates? Should I replace the XOR gates in the schematic above with their equivalent using NAND gates, or should I express the function in Sum of Products (SOP) form, then apply De Morgan's Theorem by negating twice? In the second option, I end up with 16 5-input NAND gates, plus an additional 16-input NAND gate since I got 16 minterms and the function has 5 variables.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ You don't count "initial inversion/inverters" ("+5")? Do you have limitations on circuit depth? (You show a solution with four 2-XORs; every XOR can be implemented with four 2-NANDs: 16 (much smaller) NANDs, no need for initial inversion.) \$\endgroup\$ Commented Jan 21 at 12:27
  • \$\begingroup\$ I don't have any limitations since it's just an academic exercise. I want to know which is the best way to implement any Boolean function with the lowest number of NAND/NOR gate \$\endgroup\$ Commented Jan 21 at 13:10
  • \$\begingroup\$ @minghierid I believe that the general problem of applying NAND gates to arbitrary logic is NP-complete. Aka hard. You might also examine this paper . That said, have a look at this minimization for XOR using NAND. It's just slightly non-obvious. But it provides a segue into recognizing the general difficulties for larger problems. \$\endgroup\$ Commented Jan 21 at 13:22
  • \$\begingroup\$ (counting inverters, any solution with less than 16 gates would surprise me - and you gave that circuit yourself, sort of.) You are welcome to answer your own question. \$\endgroup\$ Commented Jan 21 at 13:23
  • 2
    \$\begingroup\$ Just out of curiosity, I looked up the 74xx280 9-bit parity generator/checker. The diagram there basically shows four 3-input XOR gates, with each of those implemented as sum-of-products. Back in the day, those guys were experts at optimizing logic, so I'm guessing that's about as good as it gets. \$\endgroup\$ Commented Jan 21 at 15:51

3 Answers 3

Reset to default
3
\$\begingroup\$

Here is the circuit with minimum number of NAND gates for 1 EXOR gate.

There is no simplification for a multiple EXOR, because you have multiple times the same EXOR function. If there were a simplification, this would violate basic math/logic.

enter image description here

\$\endgroup\$
2
  • \$\begingroup\$ I'm know that a XOR gate can be implemented with 4 NAND gates, but I'm wondering if by combining multiple XOR gates, like I showed, the semplification can be done more efficiently than simply substituting each XOR with its 4-NAND equivalent for example by applying DeMorgan to the SOP or any other methods \$\endgroup\$ Commented Jan 21 at 13:51
  • 1
    \$\begingroup\$ There is no simplification, because you have multiple times the same EXOR function. If there were a simplification, this would violate basic math/logic. \$\endgroup\$ Commented Jan 21 at 13:53
1
\$\begingroup\$

A compromise between the two-(and a half)-level SOP implementation (with a problematic 16 input gate) and the 9-level circuit from four "generic NAND XORs" would be two 2-input XOR gates with three levels and one 3-input XOR from 3 inverters, 4 3-input and 1 4-input NAND gate: 5-and a half levels.
Again 16 gates in total counting the inverters.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ ("At that level" I count inputs more often than not: 32i+16o for the generic version, 32i+16o for the compromise, 101i+22o for SOP.) \$\endgroup\$ Commented Jan 21 at 15:53
1
\$\begingroup\$

You have to make a truth table of the output for every input. Then by using a KMap simplify the boolean as a sum of the minterms.
Then by de Morgan's theorem A'+B'=(AB)'. (AB)' is the Nand gate with inputs A and B.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ (You know the K-map of XORs? For 8 inputs, it looks a checkerboard.) \$\endgroup\$ Commented Jan 22 at 6:54
  • \$\begingroup\$ If it is like a board for checkers you can simplify the boolean expression first then write everything as Nand gates. \$\endgroup\$ Commented Jan 22 at 11:36
  • \$\begingroup\$ I would appreciate a presentation of such a simplification. \$\endgroup\$ Commented Jan 22 at 15:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.