Abstract
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).
| Original language | English |
|---|---|
| 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 → … |
Conference
| Conference | HELNET'97 |
|---|---|
| Period | 10/4/97 → … |