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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Nechiporuk, E.I.: The synthesis of networks from threshold elements. Prob. Kiber. 11, 49–62 (1964); Autom. Express 7 27–32, 35–39 (1964)
Lupanov, O.B.: On circuits of threshold elements. Dokl. Akad. Nauk SSSR 202, 1288–1291 (1971); Sov. Phys. Dokl. 17 91–93, (1972)
Muroga, S.: Threshold Logic and Its Applications. John Wiley, New York (1971)
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)
Beiu, V., Quintana, J.M., Avedillo, M.J.: VLSI implementation of threshold logic: A comprehensive survey. IEEE Trans. Neural Networks 14, 1217–1243 (2003)
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)
Håstad, J.: On the size of weights for threshold gates. SIAM J. Discr. Math. 7, 484–492 (1994)
Haring, D.R.: Multi-threshold threshold elements. IEEE Trans. Electr. Comp. EC-15, 45–65 (1966)
Diep, T.A.: Capacity of multilevel threshold devices. IEEE Trans. Inform. Th. 44, 241–255 (1998)
Hurst, S.L.: Multiple-valued logic: Its status and its future. IEEE Trans. Comp. 33, 1160–1179 (1984)
Smith, K.C.: Multiple valued logic: A tutorial and appreciation. IEEE Comp. 21, 17–27 (1988)
The International Technology Roadmap for Semiconductors (2004), http://public.itrs.net/
Beiu, V., Rückert, U., Roy, S., Nyathi, J.: On nanoelectronic architectural challenges and solutions. Proc. IEEE Conf. Nanotech. Munich Germany, 628–631 (2004)
Hilbert, D.: Mathematische probleme. Nachr. Akad. Wiss. Göttingen, 253–297 (1900); Bull. Amer. Math. Soc. 8, 437–479, (1902)
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)
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)
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)
Sprecher, D.A.: On the structure of continuous function of several variables. Trans. Amer. Math. Soc. 115, 340–355 (1965)
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)
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)
de Figueiredo, R.J.P.: Implications and applications of Kolmogorov’s superposition theorem. IEEE Trans. Autom. Control 25, 1227–1231 (1980)
Hecht-Nielsen, R.: Kolmogorov’s mapping neural network existence theorem. Proc. Intl. Conf. Neural Networks. San Diego CA 3, 11–14 (1987)
Girosi, F., Poggio, T.: Representation properties of networks: Kolmogorov’s theorem is irrelevant. Neural Computation 1, 465–469 (1989)
Kůrková, V.: Kolmogorov’s theorem is relevant. Neural Computation 3, 617–622 (1991)
Kůrková, V.: Kolmogorov’s theorem and multilayer neural networks. Neural Networks 5, 501–506 (1992)
Lin, J.N., Unbehauen, R.: On realization of a Kolmogorov network. Neural Computation 5, 18–20 (1993)
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)
Sprecher, D.A.: A universal mapping for Kolmogorov’s superposition theorem. Neural Networks 6, 1089–1094 (1993)
Katsuura, H., Sprecher, D.A.: Computational aspects of Kolmogorov’s superposition theorem. Neural Networks 7, 455–461 (1994)
Nees, M.: Approximative versions of Kolmogorov’s superposition theorem, proved constructively. J. Comp. Appl. Math. 54, 239–250 (1994)
Sprecher, D.A.: A numerical implementation of Kolmogorov’s superpositions. Neural Networks 9, 765–772 (1996)
Sprecher, D.A.: A numerical construction of a universal function for Kolmogorov’s superpositions. Neural Network World 6, 711–718 (1996)
Sprecher, D.A.: A numerical implementation of Kolmogorov’s superpositions II. Neural Networks 10, 447–457 (1997)
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)
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)
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)
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)
Beiu, V.: Neural inspired parallel computations require analog processors. Proc. Intl. Parallel Comp. and Electr. Eng. Conf. Bialystok Poland, 39–53 (1998)
Beiu, V.: On Kolmogorov’s superposition and Boolean function. In: Proc. Brazilian Symp. Neural Networks, Belo Horizonte Brazil, pp. 55–60 (1998)
Beiu, V., Makaruk, H.E.: Deeper sparser nets can be optimal. Neural Proc. Lett. 8, 201–210 (1998)
Sarpeshkar, R.: Analog versus digital: Extrapolating from electronics to neurobiology. Neural Computation 10, 1601–1638 (1998)
Sarpeshkar, R., O’Halloran, M.: Scalable hybrid computation with spikes. Neural Computations 14, 2003–2038 (2002)
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)
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)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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)