1
\$\begingroup\$

Question

There exists tons of software that can minimize a logic circuit by providing a solution using the least amount of logic gates.

What I am interested in, however, is not the total number of gates but the total sum of the weights of each gate. For instance, I want to assign a weight to each logic gate type (ex. AND = 3, NAND = 2, XOR = 6, etc.) and then minimize a given logic circuit with respect to the sum of the weights of all the logic gates.

Example

Suppose we have the following logic gate weights: XOR = 6 ,AND = 3, OR = 3, NAND = 2, NOR = 2, NOT = 1.
We want to minimize the following full adder in terms of total weight. Adding those weights, we have:

$$ 2 \cdot XOR + 2 \cdot AND + 1 \cdot OR \\ = 2 \cdot 6 + 2 \cdot 3 + 1 \cdot 3 \\ = 21 $$

schematic

simulate this circuit – Schematic created using CircuitLab

However, a full adder can also be implemented using 9 NAND gates, resulting in a weight of 18, which is preferable regarding the weights above.

Is there any way to conduct such a minimization?

Why do I need this?

I want to create logic circuits using individual BJT transistors. However, each logic gate requires a different number of transistors to function and also results in a vastly different implementation size. This leads me to the conclusion that for my purposes, not all logic gates are the same. Therefore, just the total number of gates is not a good indication of the total size or number of transistors needed for the circuit.

Any other ideas regarding how to tackle this issue?

\$\endgroup\$
5
  • \$\begingroup\$ Your discrete NAND is not 2 transistors, unless you magically find multiple emitter BJTs. \$\endgroup\$ Commented Jun 22 at 3:46
  • 1
    \$\begingroup\$ Can't I just put 2 NPN transistors in series? I know it is not the most optimal way and has certain limitations, but this is not the thing in question to begin with, it was just for the sake of an example \$\endgroup\$ Commented Jun 22 at 8:25
  • \$\begingroup\$ In parallel. Your goal is to minimize components. If you start off with a flawed premise you are setting yourself up for failure from the start. Your NAND number of 2 would be 3 BJTs making your full adder of 18 actially 27. 2 input NAND requires 2 BJTs in parallel for input and 1 BJT for output. Wouldn't a 50% increase in discrete BJTs have to be factored in before minimization. \$\endgroup\$ Commented Jun 22 at 11:35
  • \$\begingroup\$ This mathcenter.oxford.emory.edu/site/cs170/nandFromTransistors/… is the NAND gate I have in mind, which uses 2 BJT transistors in series. However, even then, specifically setting the weight of the NAND to 2 is not a premise, but a parameter to the problem (thus the example). It could be anything, even 659 (from the top of my head :D). The question is how to minimize the total weight of a circuit given a set of gate weights. \$\endgroup\$ Commented Jun 22 at 11:46
  • \$\begingroup\$ Pana - about NAND implementation, you are correct. \$\endgroup\$ Commented Jun 22 at 15:01

2 Answers 2

Reset to default
1
\$\begingroup\$

Any other ideas regarding how to tackle this issue?

Forget about logic gate level representation and take the optimization one level down (BJT + resistors).

Logic gates with 3 or more inputs will eventually be necessary for simpler implementations. Assuming, from the mentioned "costs", that the constructions are based on BJTs (NPN for NOR and PNP for NAND) and resistors, and adding the NOT operation for the canonical solutions (SOP and POS), the simpler metric is: 1 BJT for each gate input.

Since assembly with discrete components is mentioned, the complexity would not be a problem for and exhaustive automated search:

  1. Use some method like Quine–McCluskey to find the best SOP and POS canonical solutions

  2. Find common terms in the solutions for different outputs in the same circuits (and reuse them)

  3. Counting the costs in "number of inputs", search for further simplifications that break the canonical SOP and POS forms

\$\endgroup\$
2
  • \$\begingroup\$ How do you adapt the cost function? \$\endgroup\$ Commented Jun 22 at 14:11
  • \$\begingroup\$ @greybeard It seems, from the weights provided in the question, that only BJTs are relevant for the cost. If only steps 1 and 2 are used in the search, just count the inputs of NOR and NAND gates (depending if SOP or POS was used) and the NOTs. Each input means 1 BJT. If step 3 is included, AND and OR could also be needed, so, more construction details should be added. \$\endgroup\$ Commented Jun 22 at 15:04
-1
\$\begingroup\$

With pure transistors logic the NAND needs less transistors comparing to AND.

With diode-transistors logic the NAND needs a transistor (AND doesn’t) because you cannot do the inversion with just diodes:enter image description here

\$\endgroup\$
1
  • 3
    \$\begingroup\$ I appreciate the effort but I can't see how this is relevant to my question. Am I missing something? \$\endgroup\$ Commented Jun 22 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.