0
$\begingroup$

To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I am calling these N-input-gates.

I want to know if there exists a general algorithm which can always describe an optimal way to implement an N-input-gate using only a collection of N-input-gates with smaller N.

Such as: emulate such-and-such specific 7-input-gate (perhaps uniquely identified by a 128-bit string of outputs) using only a lot of 3-input-gates.

This might most commonly be approached in the real world by breaking N-input-gates into small messes of 2-input-gates (such as AND/OR/XNOR), for example.

But it would also be interesting if the algorithm could be general enough that a person could specify the size of the smaller gates to use.. or perhaps even an exact breakdown of which gates to use (say, "find optimal solution using only NAND or only NOR gates or only AND+NOT gates or only copies of the 3-input (01011101) gate").

Algorithm would obviously need to be able to express when no solution is possible (eg: cannot emulate AND gate using only NOT gates) and structure of algorithm might be dependent on what types of input mutations are allowed (can one output be duplicated into multiple new gates? Can a constant one or zero be fed into a gate somewhere? etc)

I'm asking because I'm curious in principle whether this angle of research has already been done, and it's hard to search for unless one already knows many clever and unique search terms to cut through the noise of ambiguous and overloaded terms. Trust me, "and", "gate", and "function" mean a zillion different things in various contexts. 😋

Also for my own sake I am creating a small logic simulation game based upon cellular automata and I'm curious about possible ways to automate some of the digital signal processing logic I can do within the system. EG if I know I want a specific (arbitrary) set of 16 output bits (EG: 1011011111101011) to come from a nibble of input bits and only have certain N-input-gate building blocks available to implement that, how can that most efficiently be done? Or can it be?

Improve this question
$\endgroup$
3
  • $\begingroup$ What kind of gates do your circuits use? Note that without restrictions some (actually almost all) gates would require exponentially sized boolean formulas. $\endgroup$ Commented Jan 15, 2024 at 7:23
  • $\begingroup$ @rus9384 Ultimately my automata uses a subset of so called "N-ary" (eg, however many inputs you'd like) gates though for practical purposes they are rarely going to be more than 3-ary. I'm still primarily interested in the general solution though as maybe tomorrow I'll make or work within some different system with different limitations or lack thereof, and rather than formulate a solution that would only suit the problem in front of me it would be better to find a general solution that solves this and virtually any other problem all at once. I've started finding an inefficient solution.. $\endgroup$ Commented Jan 15, 2024 at 17:08
  • $\begingroup$ It should not be hard to find a (locally) optimal 2-fanin (i.e. NC circuit) replacement for a 7-fanin gate, though finding a global optimum would be hard. $\endgroup$ Commented Jan 15, 2024 at 18:22

3 Answers 3

Reset to default
0
$\begingroup$

There is most likely no polynomial-time algorithm, i.e., no approach that will be efficient on all inputs. The problem is $\Sigma_2^P$-complete, i.e., at least as hard or even harder than NP-hard, even when limiting to a basis of standard two-input gates. However there are heuristic methods.

See also https://en.wikipedia.org/wiki/Logic_optimization, https://en.wikipedia.org/wiki/Logic_synthesis.

Improve this answer
$\endgroup$
1
$\begingroup$

You can always check whether two circuits have identical behaviour, there are only a finite number of circuits of size k for every k, so you can just systematically try out all circuits ordered by size and produce the first one matching the original, all in finite time. So there is an algorithm.

In practice the number of possible circuits is finite but HUGE. For example, finding an optimal (in some metric) circuit made of NAND gates for five inputs is about at the limit unless you are more clever than I am. Four inputs is no big deal because there are only 65,536 functions with four inputs, but there are over 4 billion with five and 16 billion billion with six inputs.

Improve this answer
$\endgroup$
4
  • $\begingroup$ > there are only a finite number of circuits of size k for every k I assume you mean something like "up to isomorphism", as one can just chain an infinite number of NAND gates if one were so inclined. In that case I'm curious how one would iterate over unique examples in a general sense. $\endgroup$ Commented Jan 17, 2024 at 20:46
  • $\begingroup$ @HappMacDonald Up to different truth tables. $\endgroup$ Commented Jan 19, 2024 at 13:51
  • $\begingroup$ @HappMacDonald An infinite number of NANDs doesn’t fit into size k. $\endgroup$ Commented Jan 21, 2024 at 11:51
  • $\begingroup$ @gnasher729 "a circuit of size K" just means having K inputs though. While I get that there is an upper bound to how many NAND gates one can use to produce unique outputs, I can't find a formula for that via searching nor would said formula matter if my building blocks aren't NAND. Nonetheless, since asking the question I have finally built a script that (inefficiently) performs the computation asked about by the original question. I'm just perfecting its output formatting now. github.com/HappMacDonald/circuit-simulator/blob/main/… $\endgroup$ Commented Jan 22, 2024 at 19:12
-2
$\begingroup$

I can provide a solution to your problem by discussing a general approach to implementing N-input-gates using smaller N-input-gates.

To start, let's consider the case where we want to implement an N-input-gate using only 2-input-gates. One approach is to break down the N-input-gate into smaller sub-gates, such as AND, OR, XOR gates, which are typically implemented using 2-input-gates. This approach is commonly known as gate-level synthesis.

For example, to implement an N-input AND gate using only 2-input-gates, we can break it down as follows:

  1. If N == 2, use a single 2-input AND gate.
  2. If N > 2, divide the N inputs into two groups, each having approximately equal number of inputs.
  3. Implement an N/2-input AND gate for each group using recursion (step 1 and 2).
  4. Finally, implement a 2-input AND gate with the outputs of the two N/2-input AND gates.

Similarly, other N-input-gates like OR or XOR can be implemented using 2-input-gates following similar recursive approaches.

Now, if you want to specify the size of the smaller gates to use, or even the exact breakdown of which gates to use, the problem becomes more complex. In this case, the problem can be formulated as a constraint satisfaction problem (CSP) and can be solved using various algorithms like backtracking or constraint propagation.

In this formulation, you would define constraints based on the available building blocks and the desired gate to be implemented. The algorithm then tries to find a valid combination of building blocks that satisfies the given constraints.

However, for large N or complex constraint sets, finding an optimal solution may not be computationally feasible. In such cases, heuristic search algorithms or approximation techniques can be employed to find good solutions.

It is worth noting that the specific constraints, available building blocks, and desired gate configurations will heavily influence the structure and implementation of the algorithm. Therefore, you may need to tailor the algorithm to your specific requirements and constraints.

To conclude, the research on optimizing the implementation of N-input-gates using smaller N-input-gates has been extensively studied in the field of digital circuit design. Various techniques and algorithms have been developed, but the actual implementation of an optimal solution will heavily depend on the specific constraints and requirements of your problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For $n = 4$ there are $2^{16}$ different functions, for $n = 10$ there are $2^{1024}$ different functions, for $n = 30$ there are $2^{1073741824}$ different functions. You can't just divide and conquer this. Could you cite where you receive the following the research on optimizing the implementation of N-input-gates using smaller N-input-gates has been extensively studied in the field of digital circuit design? $\endgroup$ Commented Jan 19, 2024 at 14:45
  • $\begingroup$ This answer has a distinct AI smell and does not improve on the existing ones. $\endgroup$ Commented Jan 24, 2024 at 23:29

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.