MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a circuit enumeration question related to my research. My combinatorics knowledge is lacking, so any help would be appreciated.

Given N 2-input, 1-output NOR gates (x1, x2, ..., xn) and M circuit inputs (y1, y2, ..., ym), how many possible circuit wirings can be generated using some or all of the inputs and some or all of the gates (including feedback)? Each of the NOR gates' inputs may be connected to one of the M circuit inputs or alternatively connected to a NOR gate's output (including its own).

Functionally and structurally redundant circuits are allowed. I'm just interested in an upper-bound figure for the number of possible circuits. Much thanks!

share|cite|improve this question
A weak bound is ((m+n+1) choose 2)^n, as each of the gates has at most (m+n+1) choose 2 possibilities for each of the inputs. If you do a brute force enumeration for small n, you may be able to determine the dependence on the number of inputs pretty easily. Certainly it will be easy once you have found the values for m at most 2n. Gerhard "Ask Me About Gate Arrays" Paseman, 2013.01.30 – Gerhard Paseman Jan 31 '13 at 6:11
Also, by looking at permuting the n outputs, you might be able to remove a factor of close to n factorial from the bound to remove some redundancy. Gerhard "Ask Me About System Design" Paseman, 2013.01.30 – Gerhard Paseman Jan 31 '13 at 6:32
Unfortunately, the entries to Boolean Functions don't quite cut it, as some of the designs produce oscillators. Gerhard "Circuits Is A Better Term" Paseman, 2013.01.31 – Gerhard Paseman Jan 31 '13 at 21:09

Although weak upper bounds can be readily had, I would like to consider an arrangement that provides a better upper bound when more of the architecture is known. Since it helps cut down on the numbers, I will assume that the n-many gates are identical, have two inputs each, and are symmetric, so that x GATE y and y GATE x give the same results. This analysis can easily extend to gates with more inputs that are not symmetric. Knowing something of the feedback portion will be crucial to refining the estimate.

Let us start with the purely combinatorial portion. All the gates in this portion take their inputs from the m provided inputs. As an input can be repeated, there can be up to m^2 different possible basic functions represented by a 2 input gate on the m inputs. Because of symmetry and the fact that the same input line can be repeated, there are M = (m+1) choose 2 different possible outputs.

If order is important, then C such gates can be painted with the M colors in M^C different ways. However, we can get a tighter bound on the number of functionally distinct circuits by ordering the M colors and arranging the gates in color order. If I got it right, this results in CC= (M+C+1) choose (M+1) distinct circuits.

Now of the remaining number (N-C) of gates, let us assume F of them have their outputs involved in feedback mechanisms. Thus there are I=(m+C+F) many possibilities for inputs to these F many gates. Order is important here, as the F gates are interwired, so I will settle for a weak bound of FF= ((I+1) choose 2)^F possibly distinct subcircuits. There may be a way to show that enough redundancy exists that the actual number of distinct subcircuits is more like FF/(F!), but a professional graph theorist should be consulted for this part.

Finally the rest of the N gates, say R, draw from the J = (m +C +F) signals available, but since these are not combinatorial circuits, one has something like K= (J+1) choose 2 - (m+1) choose 2 possibilities, and this is just like the combinatorial case before, as we can eliminate redundancy and orient the outputs as we please, so we actually have RR= (R+K+1) choose (K+1) possibilities.

So, for a given triple (C,F,R) of nonnegative integers summing to N, there is an upper bound of CC*FF*RR circuits for that triple, with a final upper bound being a sum over all such triples of that number of circuits.

Gerhard "Ask Me About Programmable Logic" Paseman, 2013.01.31

share|cite|improve this answer
The above is still rough, but (as in a MathOverflow comment about Graham's number that has disappeared from me) it is larger than the actual bound, so still is an upper bound. One thing to note is that R is not N, since I disinguish combinatorial (early) gates from result (final) gates whose inputs depend on outputs of gates that are not result gates. An interesting problem is on limiting FF, which should be feasible since all F outputs are used, which limits the arrangements of 2F inputs to the feedback gates substantially. Gerhard "Always Looking For Smaller Numbers" Paseman, 2013.02.01 – Gerhard Paseman Feb 1 '13 at 19:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.