Deeper Sparsely Nets can be Optimal

摘要

The starting points of this paper are two size-optimal solutions: (i) one for implementing arbitrary Boolean functions [1]; and (ii) another one for implementing certain sub-classes of Boolean functions [2]. Because VLSI implementations do not cope well with highly interconnected nets – the area of a chip grows with the cube of the fan-in [3] – this paper will analyse the influence of limited fan-in on the size optimality for the two solutions mentioned. First, we will extend a result from Horne & Hush [1] valid for fan-ins Δ = 2 to arbitrary fan-in. Second, we will prove that size-optimal solutions are obtained for small constant fan-in for both constructions, while relative minimum size solutions can be obtained for fan-ins strictly lower than linear. These results are in agreement with similar ones proving that for small constant fan-ins (Δ = 6 ... 9), there exist VLSI-optimal (i.e., minimising AT2) solutions [4], while there are similar small constants relating to our capacity of processing information [5].