Abstract
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 language | English |
---|---|
Pages | 1321-1326 |
Number of pages | 6 |
Publication status | Published - 1998 |
Externally published | Yes |
Event | Proceedings of the 1998 IEEE International Joint Conference on Neural Networks. Part 1 (of 3) - Anchorage, AK, USA Duration: May 4 1998 → May 9 1998 |
Other
Other | Proceedings of the 1998 IEEE International Joint Conference on Neural Networks. Part 1 (of 3) |
---|---|
City | Anchorage, AK, USA |
Period | 5/4/98 → 5/9/98 |
ASJC Scopus subject areas
- Software