Networks Computing Boolean Functions for Multiple Input Values
Dietmar Uhlig · Cambridge University Press eBooks · 1992
Let f be an arbitrary Boolean function depending on n variables and let A be a network computing them, i.e., A has n inputs and one output and for an arbitrary Boolean vector a of length n outputs f ( a ). Assume we have to compute simultaneously the values f ( a 1 ), …, f ( a r ) of f on r arbitrary Boolean vectors a 1 , …, a r . Then we can do it by r copies of A . But in most cases it can be done more efficiently (with a smaller complexity) by one network with nr inputs and r outputs (as already shown in Uhlig (1974)). In this paper we present a new and simple proof of this fact based on a new construction method. Furthermore, we show that the depth of our network is “almost” minimal. Introduction Let us consider (combinatorial) networks. Precise definitions are given in [Lu58, Lu65, Sa76, We87]. We assume that a complete set G of gates is given, i.e., every Boolean function can be computed (realized) by a network consisting of gates of G . For example, the set consisting of 2-input AND, 2-input OR and the NOT function is complete. A cost C ( G i ) (a positive number) is associated with each of the gates G i ∈ G . The complexity C ( A ) of a network A is the sum of the costs of its gates. The complexity C ( f ) of a Boolean function f is defined by C ( f ) = min C ( A ) where A ranges over all networks computing f . By B n we denote the set of Boolean functions {0, l} n → {0, 1}.