Abstract—The starting points of this paper are two size-optimal solutions: (i) one for implementing arbitrary Boolean functions (Horne, 1994); and (ii) another one for implementing a particular sub-class of Boolean functions (Red’kin, 1970). Because VLSI implementations do not cope well with highly interconnected nets—the area of a chip grows with the cube of the fan-in (Hammerstrom, 1988)—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 (1994) valid for fan-in Δ = 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 that 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 AT, 2) solutions (Beiu, 1997c), and with the small constants (5…9) relating to our capacity of processing information (Miller, 1956).
|Title of host publication||International Workshop on Neural Networks|
|Publisher||VU University Press|
|Publication status||Published - Dec 31 1997|
|Event||HELNET'97 - Montreux, Switzerland|
Duration: Oct 4 1997 → …
|Period||10/4/97 → …|