9
\$\begingroup\$

Is there any algorithm to determine the minimum number of NAND or NOR gates with

  1. given number of inputs
  2. availability / unavailability of complemented input

required for realizing a Boolean expression? We can get an AND-OR form as prime implicants via Karnaugh maps that is minimal (as far as I know, the Quine-McCluskey algorithm obtains them deterministically). Does a similar technique exist for NAND or NOR implementations, too? At least, such technique should determine the required minimum number of NAND/NOR gates even without finding the actual diagram?

Applying De Morgan's law on the prime implicants doesn't seem deterministic,

A ⊕ B = A'B + AB' = ((A'B)'(AB')')' [5 NAND gates]
A ⊕ B = (AB + A'B')' = ((ABAB+ABB') + (A'AB+A'B'))' = (AB(AB+B') + A'(AB+B'))' = ((AB+A')(AB+B'))' = (((AB)'A)'((AB)'B)')' [4 NAND gates by reusing (AB)']
\$\endgroup\$
  • \$\begingroup\$ Is this for a two-stage or multi-stage implementation? \$\endgroup\$ – Fizz Dec 5 '15 at 9:48
  • \$\begingroup\$ @RespawnedFluff The goal of multi-level implementation is to minimize the number of gates, so the minimal NAND/NOR implementation should also be multi-level. \$\endgroup\$ – Samik Dec 5 '15 at 10:46
  • \$\begingroup\$ K-map doesn't give you minimal result for multi-level optimization. \$\endgroup\$ – Fizz Dec 5 '15 at 12:13
10
+50
\$\begingroup\$

You can only find the minimum number of gates in a multi-level network by solving an integer programming problem [or equivalents, see below]. This problem is NP-complete, so only practical to solve up to a dozen gates or so.

There exist approximation methods that won't give you the minimum number but are more tractable in terms of time required... These are a vast topic in themselves, basically the whole field of multi-level optimization. You can read a [free] overview here.

For small networks of NAND (up to 4 variables), the problem has been completely solved by exhaustive enumeration [or equivalent methods]. There's a fairly recent [2009] PhD thesis by Elizabeth Ann Ernst that summarizes the ancient results and extends them. Ernst uses branch-and-bound, which improves upon the exhaustive method in practice, but not asymptotically. She also notes that other implicit enumeration methods like integer programming or CSP (constraint satisfaction, solved via SAT) perform worse in practice.

She obviously wrote some software for her method (called BESS), but I'm not sure if it's publicly available somewhere. Full text of her thesis is freely available at umich. And indeed you found the minimal expression for 2-input xor (your 2nd one obviously), the one highlighted below:

enter image description here

She also compared the exact results (for NANDs) with those produced by the heuristic optimizer from ABC.

ABC was able to produce an optimal network for 340 out of 4,043 functions where the optimal network is known. For those functions where ABC did not produce an optimal network it was an average of 36% larger than the optimal network[.]

There (obviously) some [larger] networks for which BESS didn't finish, but allowed an upper bound to be found (at the point where the search was abandoned). For those ABC did quite well [well with respect to the bounds found], as you can see from the 2nd graph below.

enter image description here

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If you're curious I've tried ABC on the xor problem... and it gives 5 nand gates, at least with the resyn2 script. So it's no better than Logic Friday (which uses misII). \$\endgroup\$ – Fizz Dec 5 '15 at 19:48
  • \$\begingroup\$ There exist scripts and databases for ABC that basically look up a large amount of functions for pre-computed optimal implementations e.g. arxiv.org/pdf/1108.3675.pdf I haven't tried that one, but even if it works, the hard work was done elsewhere. \$\endgroup\$ – Fizz Dec 5 '15 at 19:59
  • \$\begingroup\$ I'm going through the materials you have provided and they look very interesting, I'm struggling to understand them though. Once I properly understand them I'll probably award the bounty. In the meantime, have an upvote. \$\endgroup\$ – Samik Dec 7 '15 at 6:16
1
\$\begingroup\$

There are probably better techniques out there, but way back when in the dark ages, I found Karnaugh Maps to work just fine

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Would you mind to shed some light on those "dark ages" about how to proceed to minimal NAND/NOR implementation from AND-OR implementation obtained from Karnaugh maps? \$\endgroup\$ – Samik Dec 3 '15 at 8:48
1
\$\begingroup\$

NAND followed by NAND is equivilent to AND followed by OR.

NOR followed by NOR is equivilent to OR followed by AND.

NAND followed by NOR would be equivilent to AND followed by AND which doesn't really make much sense. NOR followed by NAND would similarly be equivilent to OR followed by OR.

I don't belive there is in the general case any feasible way to find a minimal soloution for a problem with large numbers of inputs (obviously for small input counts you can brute force). Quine-McClusky only looks at two-level soloutions (the minimal two-level soloution is often not the overall minimal soloution) and can become computationally infeasible with complex truth tables and large number of inputs.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ So there is no better way than bubble shifting? \$\endgroup\$ – Samik Dec 3 '15 at 8:48
1
\$\begingroup\$

The best algorithm is the Espresso algorithm. To some degree this is implemented in FPGA synthesis

Logic friday is a piece of software you can use. NOTE: this reduces an XOR to 5 NAND gates.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ But Espresso also gives the AND-OR implementation, doesn't it? \$\endgroup\$ – Samik Dec 3 '15 at 8:51
  • 1
    \$\begingroup\$ Espresso is "best" only in the sense that it is feasible for large inputs (formulas) [unlike k-maps], but it doesn't give the best/minimal formula in all cases. \$\endgroup\$ – Fizz Dec 5 '15 at 9:53

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.