Or-and-Or Three-Level Networks

This chapter considers the number of gates to realize logic functions by OR-AND-OR three-level networks under the condition that both true and complemented variables are available, and each gate has no fan-in and fan-out constraints. We show that an arbitrary n-variable function can be realized by an OR-AND-OR three-level network with at most 2r+1 + 1 gates, where n = 2r and r is an integer. We also prove that for sufficiently large r, regardless of the number of levels, we need at least 2r+1 (1 - ξ) gates to realize almost all functions of n variables by an AND-OR multi-level network, where ξ is an arbitrarily small positive real number (0 < ξ < 1). We developed a heuristic algorithm to design OR-AND-OR three-level networks, realized various functions, and compared the number of gates for OR-AND-OR three-level networks with AND-OR two-level ones. For arithmetic functions of 8 variables, three-level networks require, on the average, 40% fewer gates than AND-OR two-level ones. For other benchmark functions of 9 to 128 variables, three-level networks required up to 91% fewer gates. For randomly generated functions of 10 variables, three-level networks required 50% fewer gates.