FAN-IN CONSTRAINED LOGIC NETWORKS.
Abstract
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 - r)/k 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1969
- Accession Number
- AD0683752
Entities
People
- James T. Ellison
Organizations
- Sperry Corporation