Small fan-in is beautiful

Valeriu Beiu, Hanna E. Makaruk

Research output: Contribution to conferencePaperpeer-review

1 Citation (Scopus)


The starting points of this paper are two size-optimal solutions: (i) one for implementing arbitrary Boolean functions and (ii) another one for implementing certain sub-classes of Boolean functions. Because VLSI implementations do not cope well with highly interconnected nets - the area of a chip grows with the cube of the fan - in this paper will analyze the influence of limited fan-in on the size optimality for the two solutions mentioned. First, we will extend one result from Horne & Hush valid for fan-in Δ = 2 to arbitrary fan-in. Second, we will prove that size-optimal solutions are obtained for small constant fan-ins 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 (A = 6...9) there exist VLSI-optimal (i.e., minimizing AT2) solutions, while there are similar small constants relating to our capacity of processing information.

Original languageEnglish
Number of pages6
Publication statusPublished - 1998
Externally publishedYes
EventProceedings of the 1998 IEEE International Joint Conference on Neural Networks. Part 1 (of 3) - Anchorage, AK, USA
Duration: May 4 1998May 9 1998


OtherProceedings of the 1998 IEEE International Joint Conference on Neural Networks. Part 1 (of 3)
CityAnchorage, AK, USA

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Small fan-in is beautiful'. Together they form a unique fingerprint.

Cite this