Feature ArticlesNo Access

Cellular Automata with Random Memory and Its Implementations

Department of Electronics and Communication Engineering, Istanbul Technical University, Istanbul, Maslak, TR-34469, Turkey

E-mail Address: egoncu@itu.edu.tr

Search for more papers by this author

and

Mustak E. Yalcin

Department of Electronics and Communication Engineering, Istanbul Technical University, Istanbul, Maslak, TR-34469, Turkey

E-mail Address: mustak.yalcin@itu.edu.tr

Search for more papers by this author

https://doi.org/10.1142/S0218127417300178Cited by:5 (Source: Crossref)

Abstract

In this paper, a new Cellular Automata (CA) Model, named Cellular Automata with Random Memory, has been introduced. The new model is in fact, constructed by randomizing the choosing memory operation of a Cellular Automata with memory. Therefore, the model has a potential usage for application like Random Number Generators, Physical Unclonable Functions. The introduced model and other CA models are represented in an abstract form. Delay lines comprising sequentially connected logic gates are introduced in the implementation of the memory part of the introduced model. Due to the process of variations and jitter effect, the delay line becomes beneficial in the implementation of the proposed Cellular Automata with Random Memory. The introduced model is implemented on a FPGA using delay lines and also using other alternative methods.

Keywords:

References

Adamatzky, A. [1994] Identification of Cellular Automata (Taylor & Francis), pp. I–X, 1–337. Google Scholar
Alonso-Sanz, R. & Martín, M. [2003] “ Elementary cellular automata with memory,” Compl. Syst. 14, 99–126. Google Scholar
Alonso-Sanz, R. [2004] “ One-dimensional $r = 2$ cellular automata with memory,” Int. J. Bifurcation and Chaos 14, 3217–3248. Link, Web of Science, Google Scholar
Alonso-Sanz, R. & Martín, M. [2005] “ One-dimensional Cellular Automata with memory in cells of the most frequent recent value,” Int. J. Bifurcation and Chaos 15, 203–236. Google Scholar
Alonso-Sanz, R. & Bull, L. [2008] “ Random number generation by cellular automata with memory,” Int. J. Mod. Phys. C 19, 351–367. Link, Web of Science, Google Scholar
Alonso-Sanz, R. & Bull, L. [2009] “ Elementary cellular automata with minimal memory and random number generation,” Compl. Syst. 18, 195–213. Crossref, Google Scholar
Alonso-Sanz, R. & Bull, L. [2010] “ One-dimensional coupled cellular automata with memory: Initial investigations,” J. Cellular Autom. 5, 29–49. Web of Science, Google Scholar
Bassham, L. E., III, Rukhin, A. L., Soto, J., Nechvatal, J. R., Smid, M. E., Barker, E. B., Leigh, S. D., Levenson, M., Vangel, M., Banks, D. L., Heckert, N. A., Dray, J. F. & Vo, S. [2010] “Sp 800-22 rev. 1a. A statistical test suite for random and pseudorandom number generators for cryptographic applications, Tech. Rep., Gaithersburg, MD, United States. Google Scholar
Bucci, M., Germani, L., Luzzi, R., Trifiletti, A. & Varanonuovo, M. [2003] “ A high-speed oscillator-based truly random number source for cryptographic applications on a smart card ic,” IEEE Trans. Comput. 52, 403–409. Crossref, Web of Science, Google Scholar
Dogaru, R., Dogaru, I. & Kim, H. [2009] “ Binary chaos synchronization in elementary cellular automata,” Int. J. Bifurcation and Chaos 19, 2871–2884. Link, Web of Science, Google Scholar
Domany, E. & Kinzel, W. [1984] “ Equivalence of cellular automata to Ising models and directed percolation,” Phys. Rev. Lett. 53, 311–314. Crossref, Web of Science, Google Scholar
Ercsey-Ravasz, M., Roska, T. & Néda, Z. [2006] “ Perspectives for Monte Carlo simulations on the CNN universal machine,” Int. J. Mod. Phys. C 17, 909–922. Link, Web of Science, Google Scholar
Goles, E. [1989] “ Cellular automata, dynamics and complexity, Cellular Automata and Modeling of Complex Physical Systems, eds. Manneville, P., Boccara, N., Vichniac, G. & Bidaux, R. (Springer, Berlin, Heidelberg). Crossref, Google Scholar
Goncu, E. & Yalcin, M. [2014] “ A new cellular automata model with memory and its FPGA implementation,” 14th Int. Workshop on Cellular Nanoscale Networks and Their Applications (CNNA), 2014, pp. 1–2. Google Scholar
Greenberg, J. M., Hassard, B. D. & Hastings, S. P. [1978] “ Pattern formation and periodic structures in systems modeled by reaction–diffusion equations,” Bull. Amer. Math. Soc. 84, 1296–1328. Crossref, Web of Science, Google Scholar
Kaneko, K. & Akutsu, Y. [1986] “ Phase transitions in two-dimensional stochastic cellular automata,” J. Phys. A: Math. Gen. 19, L69. Crossref, Google Scholar
Kinzel, W. [1985] “ Phase transitions of cellular automata,” Z. Phys. B Condens. Matt. 58, 229–244. Crossref, Google Scholar
Kitagawa, T. [1974] “ Cell space approaches in biomathematics,” Math. Biosci. 19, 27–71. Crossref, Google Scholar
Letourneau, P. [2006] Statistical Mechanics of Cellular Automata with Memory, Canadian theses, University of Calgary (Canada). Google Scholar
Lindenmayer, A. [1968] “ Mathematical models for cellular interactions in development I. Filaments with one-sided inputs,” J. Theoret. Biol. 18, 280–299. Crossref, Web of Science, Google Scholar
Maffezzoni, P. & D’Amore, D. [2012] “ Time-domain analysis of phase-noise and jitter in oscillators due to white and colored noise sources,” Int. J. Circuit Th. Appl. 40, 999–1018. Crossref, Web of Science, Google Scholar
Martinez, G. J., Adamatzky, A. & Alonso-Sanz, R. [2013] “ Designing complex dynamics in cellular automata with memory,” Int. J. Bifurcation and Chaos 23, 1330035-1–131. Link, Web of Science, Google Scholar
Pankratz, E. & Sánchez-Sinencio, E. [2014] “ Survey of integrated-circuit-oscillator phase-noise analysis,” Int. J. Circuit Th. Appl. 42, 871–938. Crossref, Web of Science, Google Scholar
Scellato, S., Fortuna, L., Frasca, M., Gòmez-Garden̄es, J. & Latora, V. [2010] “ Traffic optimization in transport networks based on local routing,” Eur. Phys. J. B 73, 303–308. Crossref, Web of Science, Google Scholar
Schiff, J. L. [2007] Cellular Automata: A Discrete View of the World, Wiley Series in Discrete Mathematics & Optimization (Wiley). Crossref, Google Scholar
Sunar, B., Martin, W. J. & Stinson, D. R. [2007] “ A provably secure true random number generator with built-in tolerance to active attacks,” IEEE Trans. Comput. 56, 109–119. Crossref, Web of Science, Google Scholar
Toffoli, T. & Margolus, N. H. [1990] “ Invertible cellular automata: A review,” Physica D 45, 229–253. Crossref, Web of Science, Google Scholar
Valtchanov, B., Aubert, A., Bernard, F. & Fischer, V. [2008] “ Modeling and observing the jitter in ring oscillators implemented in FPGAs, 11th IEEE Workshop Design and Diagnostics of Electronic Circuits and Systems, pp. 1–6. Google Scholar
Valtchanov, B., Fischer, V., Aubert, A. & Bernard, F. [2010] “ Characterization of randomness sources in ring oscillator-based true random number generators in FPGAs, 13th Int. Symp. DDECS (IEEE), pp. 48–53. Google Scholar
Viher, B., Dobnikar, A. & Zazula, D. [1998] “ Cellular automata and follicle recognition problem and possibilities of using cellular automata for image recognition purposes,” Int. J. Med. Inform. 49, 231–241. Crossref, Web of Science, Google Scholar
von Neumann, J. [1963] “ The general and logical theory of automata,” Collected Works 5, 288. Google Scholar
von Neumann, J. [1966] Theory of Self-Reproducing Automata (University of Illinois Press, Champaign, IL, USA). Google Scholar
Wolfram, S. [1983] “ Statistical mechanics of cellular automata,” Rev. Mod. Phys. 55, 601–644. Crossref, Web of Science, Google Scholar
Wolfram, S. [1986] “ Random sequence generation by cellular automata,” Adv. Appl. Math. 7, 123–169. Crossref, Web of Science, Google Scholar
Yalçın, M. E., Vandewalle, J., Arena, P., Basile, A. & Fortuna, L. [2004] “ Watermarking on CNN-UM for image and video authentication,” Int. J. Circuit Th. Appl. 32, 591–607. Crossref, Web of Science, Google Scholar