Bernstein polynomials and stochastic computing
Abstract
Among the multiples applications of Bernstein polynomials there is one related to the processing of random signals, originally introduced by John von Neumann in 1956. Thanks to advances in technology, some ideas from the late sixties of the last century have been retaken in order to design implementations which allow -in certain cases- a simpler and more efficient processing than the traditional one. In this descriptive review article we will illustrate the use and importance of Bernstein polynomials in solving problems associated with stochastic computing, taking as a starting point the notion of stochastic logic in the sense of Qian-Riedel-Rosenberg.Visitas al artículo
Downloads
References
Alaghi, A., Hayes, J. P.: textit{``Survey of stochastic computing''}. ACM Trans. Embed. Comput. Syst. 12, 2s, Article 92, 19 pages, (2013).
Alaghi, A., Li, Ch., Hayes, J. P.: textit{``Stochastic circuits for real-time image-processing applications''}, Design Automation Conference, DAC'13, Austin, TX, EEUU, May 29 - June 07, 2013.
Alaghi, A., Qian, W., Hayes, J. P.: textit{``The promise and challenge of stochastic computing''}. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 37 (8), 1515-1531, (2018).
Arora, S.: textit{``The mathematics of machine learning deep learning''} [Slides] Plenary Lecture presented at International Congress of Mathematicians 2018. Disponible en: http://www.cs.princeton.edu/$thicksim$arora/.
Farouki, R. T., Goodman, T. N. T.: textit{``On the optimal stability of the Bernstein basis''}. Math. Comp. 65(216), 1553-1566, (1996).
Gaines, B. R.: textit{``Stochastic computing''}. En: emph{Proc. American Federation of Information Processing Societies. Spring Joint Computer Conference}, Vol. 30, 149-156. Books, Inc., New York, (1967).
Gaines, B. R.: textit{``Techniques of identification with the stochastic computer''}. Proceedings IFAC Symposium on The Problems of Identification in Automatic Control Systems, Section 6 Special Identification Instruments. Prague, Czech Republic, 1967. Disponible en https://www.catalog.hathitrust.org.
Gaines, B. R.: textit{``Stochastic computing''}. En: {em Encyclopaedia of Information, Linguistics and Control}, 766-781. Pergamon Press, New York and London, (1968).
bibitem{G1969} Gaines, B. R.: textit{``Stochastic computing systems''}. En: {em Advances in Information Systems Science}. Tou, J. F. (ed), Vol. 2, Chapter 2, 37-172. Springer Science + Business Media, New York. First edition published by Plenum Press, New York, (1969).
Gallager, R. G.: textit{``Discrete Stochastic Processes''}. The Kluwer International Series in Engineering and Computer Science. Communications and Information Theory. Springer Science + Business Media, New York, EEUU. Originally published by Kluwer Academic Publishers, (1996).
Halmos, P.: textit{``The Legend of John Von Neumann''}. Amer. Math. Montly, 80 (4), 382-394, (1973).
Halmos, P.: textit{``Lectures on Boolean Algebras''}. Springer-Verlag, New York, (1974).
Hern'andez, S., Quintana, Y.: textit{``Estructuras booleanas y el c'odigo gen'etico: algunos comentarios''}. Revista de Matem'atica de la Universidad del Atl'antico - MATUA, 2 (2), 12-36, (2015).
} Kschischang, F. R., Frey, B. J., Loeliger, H. A.: textit{``Factors graphs and the sum-product algorithm''}. IEEE Trans. Inform. Theory, 47, 498-519, (2001).
Li, X., Qian, W., Riedel, M. D., Bazargan, K., Lilja, D.: textit{``A reconfigurable stochastic architecture for reliable computing''}. Proceedings of the Great Lakes Symposium on VLSI, 315-320, (2009).
Lorentz, G. G.: textit{``Bernstein polynomials''}. Second edition. Chelsea Publishing Company, New York, EEUU. (1986).
MacKay, D. J. C., Neal, M. R.: textit{``Near Shannon limit performance of low density parity check codes''}. Electron. Lett. 33 (6), 457-458, (1997).
Mc{a}dry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A.: textit{``Towards deep learning models resistant to adversarial attacks''}. ArXiv:1706.06083v3[stat.ML], 2017. Disponible en https://arxiv.org/pdf/1706.06083.pdf.
Maldonado, C. E.: textit{``La web profunda y las din'amicas de la informaci'on''}. En: {em Le Monde diplomatique, edici'on Colombia}, Nro. 179, 34-35, 2018. Disponible en https://www.academia.edu/37039302.
Muguruma, R., Yamashita, S.: textit{``Stochastic number generation with the minimum inputs''}. IEICE Transactions on Fundamentals of Electronics, Communications and Computers Sciences, E100.A, 128-133, (2017).
Parker, K. P., McCluskey, E. J.: {it ``Probabilistic treatment of general combinational networks''}. IEEE Trans. Comput. 24 (6), 668-670, (1975).
Peavons, J., Cohen, D. A., Shawe-Taylor, J.: textit{``Generating binary sequences for stochastic computing''}. IEEE Trans. Inform. Theory, 40, 716-720, (1994).
P'erez, D., Quintana, Y.: textit{``A survey on the Weierstrass approximation theorem''}. Divulg. Mat. 16 (1), 231-247, (2008).
Poppelbaum, W. J., Afuso, C., Esch, J. W.: textit{``Stochastic computing elements and systems''}. En: {em Proc. American Federation of Information Processing Societies, Fall Joint Computer Conference}, Vol. 31, 635-644. Books, Inc., New York, (1967).
Qian, W., Riedel, M. D.: textit{``The synthesis of robust polynomial arithmetic with stochastic logic''}. En: {em Design Automation Conference}, 648-653, (2008).
Qian, W., Riedel, M. D.: textit{``Synthesizing logical computation on stochastic bit streams''}. Library of the Semiconductor Research Corporation (SRC). Publication ID:P059675, 8 pages, 2011. Disponible en https://www.src.org/library/publication/p059675/.
Qian, W., Li, X., Riedel, M. D., Bazargan, K., Lilja, D.: textit{``An architecture for fault-tolerant computation with stochastic logic''}. IEEE Trans. Comput. 60, 93-105, (2011).
Qian, W., Riedel, M. D., Rosenberg, I.: textit{``Uniform approximation and Bernstein polynomials with coefficients in the unit interval''}. European J. Combin. 32, 448-463, (2011).
Quintana, Y.: textit{``Aproximaci'on polinomial y ortogonalidad est'andar sobre la recta''}. Escuela Matem'atica de Am'erica Latina y El Caribe. EMALCA-Colombia. Editorial: Universidad del Atl'antico-Uniatl'antico, Barranquilla, Colombia. (2013).
Quintana, Y.: textit{``Concerning multivariate Bernstein polynomials and stochastic logic''}. Manuscript in progress, (n.d.).
Ribeiro, S.: textit{``Random-pulse machines''}. IEEE Trans. Electron. Comput. V EC-16 No. 3, 261-276, (1967).
Saha, A., Manna, N.: textit{``Digital Principles and Logic Design''}. Infinity Science Press LLC., Hingham, MA, EEUU. (2007).
Shannon, C. E.: textit{``A Mathematical Theory of Communication''}. Reprinted with corrections from The Bell System Technical Journal, 27, 379-423, 623-656, July, October, (1948).
Toral, S. L.: textit{``An'alisis y s'{i}ntesis de circuitos digitales estoc'asticos para la realizaci'on de sistemas anal'ogicos}. Tesis Doctoral, Universidad de Sevilla, Espa~na, 1999.
Turing, A.: textit{``On computable numbers, with an application to the Entscheidungsproblem''}. Proc. Lond. Math. Soc. (2), 42, 230-265, (1936). Errata appeared in 43, 544-546, (1937).
von Neumann, J.: textit{``Various techniques used in connection with random digits''}. National Bureau of Standards Applied Mathematics Series, 12, 36-38, (1951).
von Neumann, J.: textit{``Probabilistic logics and synthesis of reliable organisms from unreliable components''}. Automata Studies, 43-48. Princeton University Press, New Jersey, (1956).
Zhakatayev, A., Kim, K., Choi K., Lee, J.: textit{``An efficient and accurate stochastic number generator using even-distribution coding''}. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 11 pages, (2018). DOI: 10.1109/TCAD.2018.2789732.
Zhang, Ch., Bengio, S., Hardt, M., Recht, B., Vinyals, O.: textit{``Understanding deep learning requires re-thinking generalization''}. ArXiv:1611.03530v2[cs.LG], 2017. Disponible en https://arxiv.org/pdf/1611.03530.pdf.
