Journal of Network and Information Security

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

A Survey on Cellular Automata with the Application in Pseudo Random Number Generation


Affiliations
1 Department of Computer Science and Engineering, National Engineering College, Anna University, Tamil Nadu, India
     

   Subscribe/Renew Journal


The Cellular Automata (CA) were invented in the late 1940 by Stanislaw Ulam and John Von Neumann. CA are simple models of computation in which the components act together and exhibit complex behavior. Initially CA are represented as model of self-reproducing organisms. Later they are applied in various areas like Physics, biology and other applications. The self-reproducing behavior is then utilized to construct Universal Turing Machine. This Survey is about the applications of CA closer to Computer Science especially designing Pseudo Random Number Generator.

Keywords

Cellular Automata, CA, Applications of CA , Pseudo Random Number Generator, PRNG, 1D CA Rules.
Subscription Login to verify subscription
User
Notifications
Font Size


  • P. Sarkar, “A brief history of cellular automata,” ACM Computing Surveys (CSUR), vol. 32, pp 80-107, 2000.

  • ALVY RAY SMITH III, “Cellular automata complexity trade-offs,” Information and Control, vol. 18, pp. 466-482, 1971.

  • K. Sutner, “Classification of cellular automata,” Encyclopedia of Complexity and Systems Science, Part 2009.

  • W. Li, and N. Packard, “The structure of the elementary cellular automata rule space,” Complex Systems, vol. 4, pp. 281-297, 1990.

  • W. Li, N. H. Packarda, and C. Langton, “Transition phenomena in cellular automata rule space,” Physica D, vol. 45, pp. 77-94, 1990.

  • Appendix of Theory and Applications of Cellular Automata, S. Wolfram, ed. (World Scientific, 1986).

  • G. Braga, G. Cattaneo, P. Flocchini, and C. Q. Vogliotti, “Fundamental study: Pattern growth in Elementary Cellular Automata,” Theoretical Computer Science, vol. 145, pp. 1-26, 1995.

  • E. Filiol, “A new statistical testing for symmetric ciphers and hash functions,” International Conference on Information and Communications Security, Springer Link 2002.

  • K. Chakraborty, and D. R. Chowdhury, “CSHR: Selection of cryptographically suitable hybrid cellular automata rule,” International Conference on Cellular Automata for Research and Industry, ACRI, Springer, pp. 591-600, 2012.

  • N. H. Packard, and S. Wolfram, “Two-dimensional cellular automata,” Journal of Statistical Physics, vol. 38, pp. 5-6, 1985.

  • D. Eppstein, “Growth and decay in life-like cellular automata,” Game of Life Cellular Automata, Springer Link, 2010.

  • A. Adamatzky, Game of Life Cellular Automata, Springer, 2010.

  • H. Umeo, M. Hisaoka, and T. Sogabe, “A survey on optimum-time firing squad synchronization algorithms for one-dimensional cellular automata,” International Journal of Unconventional Computing, vol. 1, pp. 403-426.

  • K. Culik II, and S. Dube, “An efficient solution of the firing mob problem,” Theoretical Computer Science, vol. 91, pp. 57-69, 1991.

  • A. Beckers, and T. Worsch “A perimeter-time CA for the queen bee problem,” Parallel Computing, vol. 27, pp. 15-25, 2001.

  • Katarzyna Zbiec, “The prisoner’s dilemma and the game of life,” Studies in Logic, Grammar and Rhetoric, vol. 19, pp. 95-100, 2003.

  • N. Ganguly, B. K. Sikdar, A. Deutsch, G. Canright, and P. P. Chaudhuri “A survey on cellular automata,” 2003.

  • V. Sharma, A. Dev, and S. Rai, “A comprehensive study of cellular automata”, International Journal of Advanced Research in Computer Science and Software Engineering, vol. 2, pp. 340-344, 2012.

  • R. J. De Boer, and P. Hogeweg, “Growth and Recruitment in the Immune Network,” In A. F. Perelson and G. Weisbuch, editors, Theoretical and Experimental Insights into Immunology, vol. 66, pp. 223-247, 1992.

  • F. Celada, and P. E. Seiden, “A computer model of cellular interactions in the immune system,” Immunology Today, vol. 13, pp. 56-62, 1992.

  • B. K. Sikdar, and N. Ganguly, and P. P. Chaudhuri, “Fault diagnosis of VLSI circuits with cellular automata based pattern classifier,” IEEE transaction on Computer-Aided design of Integrated Circuits and systems, vol. 24, pp. 1115-1131, 2005.

  • A. R. Khan, “VLSI architecture of a cellular automata machine,” Journal of Computer and Mathematics with applications, vol. 33, 79-94,1997.

  • A. K. Das, “Additive cellular automata: Theory and application as a built-in self-test structure,” PhD thesis, I.I.T. Kharagpur, India, 1990.

  • D. R. Chowdhury, S. Basu, I. S. Gupta, and P. Pal Chaudhuri, “Design of CAECC Cellular Automata based Error Correcting Code,” IEEE Transaction on Computers, vol. 43, pp. 759-764, 1994.

  • S. Wolfran, “Origin of randomness in physical systems,” Physical Review Letter, vol. 55, p. 449, 1985.

  • S. Wolfran , “Cellular automata as models of complexity,” Nature, vol. 311, pp. 419-424, 1984.

  • H. Niesche, “Introduction to Cellular Automata - Seminar,” Organic Computing, SS2006, 2006.

  • C. Burstedde, K. Klauck, A. Schadschneider, and J. Zittartz, “Simulation of pedestrian dynamics using a two-dimensional cellular automaton,” Physica A: Statistical Mechanics and Its Applications, vol. 295, pp 507-525, 2001.

  • A. Kirchner, and A. Schadschneider, “Simulation of evacuation processes using a bionics-inspired cellular automaton model for pedestrian dynamics,” Physica A: Statistical Mechanics and Its Applications, vol. 312, pp. 260-276, 2002.

  • M. Rickert, K. Nagel, and M. Schreckenberg, “Two lane traffic simulations using cellular automata,” Physica A: Statistical Mechanics and its Applications, vol. 231, pp. 534-550, 1996.

  • H. Situngkir, “Exploring ancient architectural designs with cellular automata,” SSRN, 2010.

  • S. Wolfram, “Theory and applications of cellular automata,” World Scientific, Singapore, 1986. ISBN 9971-50-124-4pbk.

  • C. Fontaine, “Linear congruential generator,” Encyclopedia of Cryptography and Security, vol. 1, pp. 721-721, 2011.

  • D. E. Knuth, The Art of Computer Programming: Semi Numerical Algorithms, vol. 2, Adison Wesley, 1981(Book).

  • G. Marsaglia, & L. H. Tsay, “Matrices and structure of random number sequences,” Linear Algebra and Its Application, vol. 67, pp. 147-156, 1985.

  • M. Sahithi, B. MuraliKrishna, M. Jyothi, K. Purnima, A. Jhansi Rani, N. Naga Sudha, “Implementation of random number generator using LFSR for high secured multi purpose applications,” International Journal of Computer Science and Information Technologies, vol. 3, pp. 3287-3290, 2012.

  • S. Wolfram, “Random sequence generation by cellular automata,” Advances in Applied Mathematics, vol. 7, pp. 123-169, 1986.

  • F. Seredynski, P. Bouvry, and A. Y. Zomaya “Cellular automata computations and secret key cryptography,” Parallel Computing, vol. 30, pp. 753-766, 2004.

  • M. Szaban, F. Seredynski, and P. Bouvry, “Collective behavior of rules for cellular automata-based stream ciphers,” IEEE Conference on Evolutionary Computation, pp. 179-183, 2006.

  • P. Ping, F. Xu, and X.-J. Wang, “Generating high-quality random numbers by next nearest-neighbor cellular automata,” Advanced material Research, vol. 765, pp. 1200-1204, 2013.

  • P. D. Hortensius, R. D. Mcleod, W. Pries, D Michael Miller and Howard C. Card, “Cellular Automata- Based Pseudorandom Number Generators for Built-In self-Test,” IEEE transactions on Computer-Aided Design, vol. 8, pp 842-859,1989.

  • M. Tomassini, M. Sipper, and M. Perrenoud, “On the Generation of High-Quality Random Numbers by Two-Dimensional Cellular Automata,” IEEE Transactions on Computers, vol. 49, pp. 1146-1151, 2000.

  • S. U. Guan, and S. K. Tan, “Pseudorandom number generation with self-programmable cellular automata,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, pp. 1095-1101, 2004.

  • S. Ghosh, A. Sengupta, D. Saha, and D. R. Chowdhury, “A scalable method for constructing non-linear cellular automata with period 2n - 1,” International Conference on Cellular Automata, pp. 65-79, 2014.

  • C. J. Etherington, “An Anaysis of Cryptographically Significant Boolean Functions with High Correlation Immunity by Reconfigurable Computer,” 2010 Thesis.

  • S.-U. Guan, and S. Zhang, “Pseudorandom number generation based on controllable cellular automata,” Future Generation Computer Systems, vol. 20, pp. 627-641, 2004.


Abstract Views: 384

PDF Views: 6




  • A Survey on Cellular Automata with the Application in Pseudo Random Number Generation

Abstract Views: 384  |  PDF Views: 6

Authors

I. Gethzi Ahila Poornima
Department of Computer Science and Engineering, National Engineering College, Anna University, Tamil Nadu, India
B. Paramasivan
Department of Computer Science and Engineering, National Engineering College, Anna University, Tamil Nadu, India
K. Mohaideen Pitchai
Department of Computer Science and Engineering, National Engineering College, Anna University, Tamil Nadu, India
M. Bhuvaeswari
Department of Computer Science and Engineering, National Engineering College, Anna University, Tamil Nadu, India

Abstract


The Cellular Automata (CA) were invented in the late 1940 by Stanislaw Ulam and John Von Neumann. CA are simple models of computation in which the components act together and exhibit complex behavior. Initially CA are represented as model of self-reproducing organisms. Later they are applied in various areas like Physics, biology and other applications. The self-reproducing behavior is then utilized to construct Universal Turing Machine. This Survey is about the applications of CA closer to Computer Science especially designing Pseudo Random Number Generator.

Keywords


Cellular Automata, CA, Applications of CA , Pseudo Random Number Generator, PRNG, 1D CA Rules.

References