Skip to main content

Using Kolmogorov Inspired Gates for Low Power Nanoelectronics

  • Conference paper
Computational Intelligence and Bioinspired Systems (IWANN 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3512))

Included in the following conference series:

  • 2568 Accesses

Abstract

Based on explicit numerical constructions for Kolmogorov’s superpositions (KS) linear size circuits are possible. Because classical Boolean as well as threshold logic implementations require exponential size in the worst case, it follows that size-optimal solutions for arbitrary Boolean functions (BFs) should rely (at least partly) on KS. In this paper, we will present previous theoretical results while examining the particular case of 3-input BFs in detail. This shows that there is still room for improvement on the synthesis of BFs. Such size reductions (which can be achieved systematically) could help alleviate the challenging power consumption problem, and advocate for the design of Kolmogorov-inspired gates, as well as for the development of the theory, the algorithms, and the CAD tools that would allow taking advantage of such optimal combinations of different logic styles.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Nechiporuk, E.I.: The synthesis of networks from threshold elements. Prob. Kiber. 11, 49–62 (1964); Autom. Express 7 27–32, 35–39 (1964)

    Google Scholar 

  2. Lupanov, O.B.: On circuits of threshold elements. Dokl. Akad. Nauk SSSR 202, 1288–1291 (1971); Sov. Phys. Dokl. 17 91–93, (1972)

    Google Scholar 

  3. Muroga, S.: Threshold Logic and Its Applications. John Wiley, New York (1971)

    MATH  Google Scholar 

  4. Beiu, V.: Constructive threshold logic addition: A synopsis of the last decade. In: Kaynak, O., Alpaydın, E., Oja, E., Xu, L. (eds.) ICANN 2003 and ICONIP 2003. LNCS, vol. 2714, pp. 745–752. Springer, Berlin (2003)

    Chapter  Google Scholar 

  5. Beiu, V., Quintana, J.M., Avedillo, M.J.: VLSI implementation of threshold logic: A comprehensive survey. IEEE Trans. Neural Networks 14, 1217–1243 (2003)

    Article  Google Scholar 

  6. Myhill, J., Kautz, W.H.: On the size of weights required for linear-input switching functions. IRE Trans. Electr. Comp. EC-10, 288–290 (1961)

    Article  Google Scholar 

  7. Håstad, J.: On the size of weights for threshold gates. SIAM J. Discr. Math. 7, 484–492 (1994)

    Article  MATH  Google Scholar 

  8. Haring, D.R.: Multi-threshold threshold elements. IEEE Trans. Electr. Comp. EC-15, 45–65 (1966)

    Article  MATH  Google Scholar 

  9. Diep, T.A.: Capacity of multilevel threshold devices. IEEE Trans. Inform. Th. 44, 241–255 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  10. Hurst, S.L.: Multiple-valued logic: Its status and its future. IEEE Trans. Comp. 33, 1160–1179 (1984)

    Article  Google Scholar 

  11. Smith, K.C.: Multiple valued logic: A tutorial and appreciation. IEEE Comp. 21, 17–27 (1988)

    Google Scholar 

  12. The International Technology Roadmap for Semiconductors (2004), http://public.itrs.net/

  13. Beiu, V., Rückert, U., Roy, S., Nyathi, J.: On nanoelectronic architectural challenges and solutions. Proc. IEEE Conf. Nanotech. Munich Germany, 628–631 (2004)

    Google Scholar 

  14. Hilbert, D.: Mathematische probleme. Nachr. Akad. Wiss. Göttingen, 253–297 (1900); Bull. Amer. Math. Soc. 8, 437–479, (1902)

    Google Scholar 

  15. Kolmogorov, A.N.: On the representation of continuous functions of several variables by superposition of continuous functions of fewer variables. Dokl. Akad. Nauk SSSR 108, 179–182 (1956); Amer. Math. Soc. Transl. 17, 369–373, (1961)

    MathSciNet  MATH  Google Scholar 

  16. Arnol’d, V.I.: On functions of three variables. Dokl. Akad. Nauk SSSR 114, 679–681 (1957); Amer. Math. Soc. Transl. 28, 51–54, (1963)

    MathSciNet  MATH  Google Scholar 

  17. Kolmogorov, A.N.: On the representation of continuous functions of many variables by superpositions of continuous functions of one variable and addition. Dokl. Akad. Nauk SSSR 114, 953–956 (1957); Amer. Math. Soc. Transl. 28, 55–59, (1963)

    MathSciNet  MATH  Google Scholar 

  18. Sprecher, D.A.: On the structure of continuous function of several variables. Trans. Amer. Math. Soc. 115, 340–355 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  19. Lorenz, G.G.: Representation of functions of several variables by function of one variable. Chp. 11 in Approximations of Functions. Holt, Rinehart, and Winston, New York (1966)

    Google Scholar 

  20. Sprecher, D.A.: On the structure of representations of continuous functions of several variables as finite sums of continuous functions of one variable. Proc. Amer. Math. Soc. 17, 98–105 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  21. de Figueiredo, R.J.P.: Implications and applications of Kolmogorov’s superposition theorem. IEEE Trans. Autom. Control 25, 1227–1231 (1980)

    Article  MATH  Google Scholar 

  22. Hecht-Nielsen, R.: Kolmogorov’s mapping neural network existence theorem. Proc. Intl. Conf. Neural Networks. San Diego CA 3, 11–14 (1987)

    Google Scholar 

  23. Girosi, F., Poggio, T.: Representation properties of networks: Kolmogorov’s theorem is irrelevant. Neural Computation 1, 465–469 (1989)

    Article  Google Scholar 

  24. Kůrková, V.: Kolmogorov’s theorem is relevant. Neural Computation 3, 617–622 (1991)

    Article  Google Scholar 

  25. Kůrková, V.: Kolmogorov’s theorem and multilayer neural networks. Neural Networks 5, 501–506 (1992)

    Article  Google Scholar 

  26. Lin, J.N., Unbehauen, R.: On realization of a Kolmogorov network. Neural Computation 5, 18–20 (1993)

    Article  Google Scholar 

  27. Nakamura, M., Mines, R., Kreinovich, V.: Guaranteed intervals and Kolmogorov’s theoerem (and their possible relation to neural networks). Interval Computations 3, 183–199 (1993)

    MathSciNet  Google Scholar 

  28. Sprecher, D.A.: A universal mapping for Kolmogorov’s superposition theorem. Neural Networks 6, 1089–1094 (1993)

    Article  MATH  Google Scholar 

  29. Katsuura, H., Sprecher, D.A.: Computational aspects of Kolmogorov’s superposition theorem. Neural Networks 7, 455–461 (1994)

    Article  MATH  Google Scholar 

  30. Nees, M.: Approximative versions of Kolmogorov’s superposition theorem, proved constructively. J. Comp. Appl. Math. 54, 239–250 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  31. Sprecher, D.A.: A numerical implementation of Kolmogorov’s superpositions. Neural Networks 9, 765–772 (1996)

    Article  Google Scholar 

  32. Sprecher, D.A.: A numerical construction of a universal function for Kolmogorov’s superpositions. Neural Network World 6, 711–718 (1996)

    Google Scholar 

  33. Sprecher, D.A.: A numerical implementation of Kolmogorov’s superpositions II. Neural Networks 10, 447–457 (1997)

    Article  Google Scholar 

  34. Brattka, V.: A computable Kolmogorov superposition theorem. In: Blanck, J., Brattka, V., Hertling, P., Weihrauch, K. (eds.) Computability and Complexity in Analysis. Informatik Berichte, vol. 272, pp. 7–22. Informatik Berichte (2000)

    Google Scholar 

  35. Neruda, R., Štědry, A., Drkošová, J.: Towards feasible learning algorithm based on Kolmogorov theorem. Proc. Intl. Conf. AI. Las Vegas USA, 915–920 (2000)

    Google Scholar 

  36. Köppen, M.: On the training of a kolmogorov network. In: Dorronsoro, J.R. (ed.) ICANN 2002. LNCS, vol. 2415, pp. 474–479. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  37. Beiu, V.: Optimization of circuits using a constructive learning algorithm. In: Bulsari, A.B., Kallio, S. (eds.) Neural Networks in Engineering Systems, Åbo Akademis Tryckeri, pp. 291–294 (1997)

    Google Scholar 

  38. Beiu, V.: Neural inspired parallel computations require analog processors. Proc. Intl. Parallel Comp. and Electr. Eng. Conf. Bialystok Poland, 39–53 (1998)

    Google Scholar 

  39. Beiu, V.: On Kolmogorov’s superposition and Boolean function. In: Proc. Brazilian Symp. Neural Networks, Belo Horizonte Brazil, pp. 55–60 (1998)

    Google Scholar 

  40. Beiu, V., Makaruk, H.E.: Deeper sparser nets can be optimal. Neural Proc. Lett. 8, 201–210 (1998)

    Article  Google Scholar 

  41. Sarpeshkar, R.: Analog versus digital: Extrapolating from electronics to neurobiology. Neural Computation 10, 1601–1638 (1998)

    Article  Google Scholar 

  42. Sarpeshkar, R., O’Halloran, M.: Scalable hybrid computation with spikes. Neural Computations 14, 2003–2038 (2002)

    Article  MATH  Google Scholar 

  43. Beiu, V.: A novel highly reliable low-power nano architecture: When von Neumann augments Kolmogorov. In: Proc. Appl.-specific Sys., Arch. and Proc., Galveston USA, pp. 167–178 (2004)

    Google Scholar 

  44. Avedillo, M.J., Quintana, J.M.: A threshold logic synthesis tool for RTD circuits. In: Proc. Euromicro Symp. Digital Sys. Design. Rennes, France, pp. 624–627 (2004)

    Google Scholar 

  45. Zhang, R., Gupta, P., Zhong, L., Jha, N.K.: Threshold network synthesis and optimization and its application to nanotechnologies. IEEE Trans. CAD 24, 107–118 (2005)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Beiu, V., Zawadski, A., Andonie, R., Aunet, S. (2005). Using Kolmogorov Inspired Gates for Low Power Nanoelectronics. In: Cabestany, J., Prieto, A., Sandoval, F. (eds) Computational Intelligence and Bioinspired Systems. IWANN 2005. Lecture Notes in Computer Science, vol 3512. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494669_54

Download citation

  • DOI: https://doi.org/10.1007/11494669_54

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-26208-4

  • Online ISBN: 978-3-540-32106-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics