TY - GEN
T1 - On Kolmogorov's superpositions
T2 - International Joint Conference on Neural Networks, IJCNN 2005
AU - Beiu, Valeriu
AU - Zawadzki, Artur
PY - 2005
Y1 - 2005
N2 - Based on explicit numerical constructions for Kolmogorov's superpositions (KS) linear size circuits implementing arbitrary Boolean functions (BFs) are possible. Because classical Boolean as well as threshold logic (TL) implementations, require exponential size in the worst case, it follows that, size-optimal solutions for implementing arbitrary BFs should rely (at least partly) on KS-inspired gates (KGs). In this paper, we examine BFs of three inputs in detail and show that even the size given by KS can be reduced when Boolean gates (BGs) could be optimally combined with KGs (low precision analog gates). This shows that there is room for improving on the synthesis of BFs. Finally, we will show that the size obtained when optimally combining BGs and KGs can be reduced even further if we are allowed to also use TL gates. Such systematic size reductions could help alleviate the challenging power consumption problem. They advocate for the design of KGs, as well as for the development of the theory, the algorithms, and the CAD tools that could take advantage of optimal combinations of different logic gates and design styles.
AB - Based on explicit numerical constructions for Kolmogorov's superpositions (KS) linear size circuits implementing arbitrary Boolean functions (BFs) are possible. Because classical Boolean as well as threshold logic (TL) implementations, require exponential size in the worst case, it follows that, size-optimal solutions for implementing arbitrary BFs should rely (at least partly) on KS-inspired gates (KGs). In this paper, we examine BFs of three inputs in detail and show that even the size given by KS can be reduced when Boolean gates (BGs) could be optimally combined with KGs (low precision analog gates). This shows that there is room for improving on the synthesis of BFs. Finally, we will show that the size obtained when optimally combining BGs and KGs can be reduced even further if we are allowed to also use TL gates. Such systematic size reductions could help alleviate the challenging power consumption problem. They advocate for the design of KGs, as well as for the development of the theory, the algorithms, and the CAD tools that could take advantage of optimal combinations of different logic gates and design styles.
KW - Boolean logic
KW - Circuit design
KW - Circuit size
KW - Kolmogorov's superpositions
KW - Low power
KW - Threshold logic
UR - http://www.scopus.com/inward/record.url?scp=33745951640&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33745951640&partnerID=8YFLogxK
U2 - 10.1109/IJCNN.2005.1555908
DO - 10.1109/IJCNN.2005.1555908
M3 - Conference contribution
AN - SCOPUS:33745951640
SN - 0780390482
SN - 9780780390485
T3 - Proceedings of the International Joint Conference on Neural Networks
SP - 651
EP - 656
BT - Proceedings of the International Joint Conference on Neural Networks, IJCNN 2005
Y2 - 31 July 2005 through 4 August 2005
ER -