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
