Title: On the Node Complexity of Threshold Gate Circuits with Sub-linear Fan-ins
Abstract: This paper discusses size-optimal solutions for implementing arbitrary Boolean functions using threshold gates. After presenting the state-of-the-art, we start from the result of Horne and Hush [12], which shows that threshold gate circuits restricted to fan-in 2 can implement arbitrary Boolean functions, but require O(2 n /n) gates in 2n layers. This result will be generalized to arbitrary fan-ins (Δ), lowering the depth to n/logΔ + n/Δ, and proving that all the (relative) minimums of size are obtained for sub-linear fan-ins (Δ < n − logn). The fact that size-optimal solutions have sub-linear fan-ins is encouraging, as the area and the delay of VLSI implementations are related to the fan-in of the gates.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot