On Kolmogorov's superpositions: Novel gates and circuits for nanoelectronics?

Valeriu Beiu, Artur Zawadzki

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Title of host publicationProceedings of the International Joint Conference on Neural Networks, IJCNN 2005
    Pages651-656
    Number of pages6
    DOIs
    Publication statusPublished - 2005
    EventInternational Joint Conference on Neural Networks, IJCNN 2005 - Montreal, QC, Canada
    Duration: Jul 31 2005Aug 4 2005

    Publication series

    NameProceedings of the International Joint Conference on Neural Networks
    Volume1

    Other

    OtherInternational Joint Conference on Neural Networks, IJCNN 2005
    Country/TerritoryCanada
    CityMontreal, QC
    Period7/31/058/4/05

    Keywords

    • Boolean logic
    • Circuit design
    • Circuit size
    • Kolmogorov's superpositions
    • Low power
    • Threshold logic

    ASJC Scopus subject areas

    • Software
    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'On Kolmogorov's superpositions: Novel gates and circuits for nanoelectronics?'. Together they form a unique fingerprint.

    Cite this