Universal Base Functions and Modules for Realizing Arbitrary Switching Functions

Universal base functions (UBF´s) which are generalizations of universal logic functions are defined. An (n, m, r)-UBF can be implemented as a single module (UBM) with n+m inputs and 1 output. An arbitrary n-variable switching function fn (X) is then realized on the fixed UBM by realizing a suitable set of m r-variable functions with which to drive m inputs of the UBM, the remaining n inputs being driven by X. The fan-in of a UBM for r ¿2 is shown to be considerably less than that of a universal logic module (a special case corresponding to r = 1). Specific UBF´s are proposed for r = 2 in which m is on the order of 60 percent of the value obtained by using the UBF defined by the familiar Shannon decomposition formula. This is close to the theoretical lower bound on m. The use of UBM´s provides a new way to realize an arbitrary function or set of functions, completely specified or otherwise, by assembling a small number of circuits selected from a small set of standard logic modules of limited fan-in. For the case r = 2, the number of two-input devices required to drive the m inputs of the UBM is often considerably less than m. DON´T CARES can be used to advantage to reduce this number still further.