FAN-IN CONSTRAINED LOGIC NETWORKS.
Final scientific rept. 1 Jun 67-24 Nov 68,
SPERRY RAND CORP PHILADELPHIA PA UNIVAC DIV
Pagination or Media Count:
Three topics are considered in this paper, switching-time minimization, the relationship of category theory to switching circuits, and the algebra of cellular arrays. Switching-time is related to the number of levels a logic net has, that is, the number of logic gates a signal must traverse in passing through the net. The object is to establish upper and lower bounds on the number of levels required to implement certain classes of Boolean functions, given that no more than r inputs can be handled by any element of the net. It is shown that minimal level-requirements for n-variable Boolean functions range from approximately log of n to the base r to at least log of 2 to the n-r power to the base r, never requiring more than approximately n - rk levels, where k is the largest integer such that k 2 to the kth power or r. Similar bounds are also found for universal functions for n variables these are functions which can perform to an arbitrary Boolean function in n variables depending on the constants biasing a fixed subset of the inputs. All upper bounds are obtained by explicit construction of nets realizing them. It is shown that the ratio of upper bounds to lower bounds approaches one as r increases to infinity. In succeeding sections, categories and functors are defined which place switching theory in the framework of this increasingly important field, and it is shown that universal functions are the universal elements of a suitably defined functor. Finally, an algebra is defined which could provide a context for the investigation of cellular arrays. Author
- Electrical and Electronic Equipment