Physical Sciences and Mathematics Commons^™

On Combinational Networks With Restricted Fan-Out, K. L. Kodandapani, Sharad C. Seth

School of Computing: Faculty Publications

Fan-out-free networks of AND, OR, NOT, EXOR, and MAJORITY gates are considered. Boolean functions for which such networks exist are defined to be fan-out free. The paper solves the following problems regarding the fan-out-free networks and functions.
1) Characterization of the class of fan-out-free functions: The characterization given is constructive in the sense that if a given function is fan-out free one obtains a fan-out-free network to realize it.
2) Counting the class of fan-out-free functions: After establishing a correspondence between a fan-out-free function and a normalized network realizing it, a series of formulas are developed to count distinct normal …