Abstract

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(a1), …,f(ar) of f on r arbitrary Boolean vectors a1, …,ar. 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(Gi) (a positive number) is associated with each of the gates Gi ∈ 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 Bn we denote the set of Boolean functions {0, l}n → {0, 1}.