The Fanout Structure of Switching Functions
John P. Hayes · Journal of the ACM · 1975
The problem of determining the amount of fanout required to reahze a switching function m investigated.The significance of fanout in switching networks is discussed Fanout-free functions are introduced and their propertms examined.Two relations, adjacency and masking, are defined on the variables X of a functlonf(X), and these relations are used to characterize fanoutfree functions A quantity r(f) called the input fanout index of f is defined for arbitrary switching functions; r (f) represents the minimum number of input variables that require fanout in any reahzation of ff It is shown that r(f) can be determined from the pmme lmphcants and prime imphcates of f using two additmnal relations on X, the conjugate property and compatibility An algorithm is presented for finding a reahzatlon of f in whmh only T(f) variables fan out.Some other measures of fanout are briefly considered.