The Fanout Structure of Switching Functions

作     者：Hayes, John P. 

作者机构：Department of Electrical Engineering and Computer Science Program University of Southern California Los Angeles CA 90007 United States 

出 版 物：《Journal of the ACM (JACM)》 (J. ACM)

年 卷 期：1975年第22卷第4期

页      面：551-571页

学科分类：0810[工学-信息与通信工程] 1205[管理学-图书情报与档案管理] 0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：fanout fanout-free functions fanout-free networks Input fanout index mimmlzatlon of fanout partially fanout-free functtons switching functions 

摘      要：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 functlon f(X), and these relations are used to characterize fanoutfree functions A quantity τ(f) called the input fanout index of f is defined for arbitrary switching functions;τ(f) represents the minimum number of input variables that require fanout in any reahzation of ff It is shown that τ(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 τ(f) variables fan out. Some other measures of fanout are briefly considered. © 1975, ACM. All rights reserved.