Saturday , April 27 2024

On the Selection of Cellular Automata based PRNG in
Code Division Multiple Access Communications

Arnab MITRA
Adamas Institute of Technology,
Kolkata-700126, India
mitra.arnab@gmail.com, arnab.mitra@etti.tuiasi.ro

Abstract: The main contribution of this article is to investigate the application suitability of Cellular Automata based pseudo-random noise generator in Code Division Multiple Access Communications. New dynamics in group Cellular Automata were explored. Extensive analysis for two classes of group Cellular Automata (maximum length Cellular Automata and equal length Cellular Automata) were carried out. The analysis and comparison results for these classes of group Cellular Automata demonstrate the advantages of equal length Cellular Automata over maximum length Cellular Automata in view of code division multiple access applications.

Keywords: Pseudo-Random Noise Generator, Linear Feed Back Shift Register, Coupled Map Lattice, Cellular Automata, Code Division Multiple Access.

>>Full text >>
 CITE THIS PAPER AS:
Arnab MITRA, On the Selection of Cellular Automata based PRNG in Code Division Multiple Access Communications, Studies in Informatics and Control, ISSN 1220-1766, vol. 25(2), pp. 217-226, 2016. https://doi.org/10.24846/v25i2y201609

  1. Introduction

Pseudo-random noise generators (PRNGs) are used in engineering applications such as in built-in self-test (BIST) circuits applications and in the validation of design and manufacturing control. In data security, strength of the crypto-system depends on the quality of PRNGs. In communications, multiple equal length random keys are required in view of code division multiple access (CDMA), where the keys in CDMA should be independent (de-correlated) between them. Application specific requirements resulted in numerous approaches for PRNGs, for example, PRNG designs are available based on Coupled Mapped Lattices (CMLs) [42], Cellular Automata (CAs) [5, 27, 38], and Linear Feed Back Shift Register (LFSRs) [9, 12, 17]. CAs were suggested for potential uses in BISTs and data security applications with advantages of having low cost physical implementation and support for easy incorporation in very-large-scale integration (VLSI) architecture [5, 27].

CAs evolve in discrete space and time. Elementary CAs (ECAs) are 1-dimensional, 3-neighbourhood CAs with fixed or periodic boundary condition [38]. ECA evolutions are dependent on binary values of the CA cells and CA transition functions (total 256 rules, also known as Wolfram CA rules). The next state function (CA rule) of the  cell at time  is  of the present states of ,  and  cell at time t [27]. A CA rule is additive when it involves only XOR and XNOR logic.

A special class of ECAs always producing cycles is referred as group CA. Additive rules play an important role in generation of group CAs. Uses of group CAs as PRNGs were described in [27].

The main purpose of this article is to compare PRNGs based on CAs, LFSRs, and CMLs aiming CDMA applications and to show that a class of ECAs, Equal Length Cellular Automata (ELCAs) is well suited for CDMA applications.

The article is organized as follows: PRNGs based on LFSRs, CMLs, and CAs are compared in Section 2; Section 3 introduces the analysis of CA based PRNGs in all fixed boundary conditions; while properties related to CA based PRNGs are discoursed in Section 4. Discussion and conclusions are followed in Section 5 and Section 6 respectively.

REFERENCES

  1. ADAMATZKY, A. I., Hierarchy of Fuzzy Cellular Automata, Fuzzy Sets and Systems, vol. 62, no. 2, 1994, pp. 167-174.
  2. ADAMATZKY, A., C. J. MARTINEZ, On Generative Morphological Diversity of Elementary Cellular Automata, Kybernetes, Emerald Group Publishing, vol. 39, 1, 2010, pp. 72-82.
  3. BETEL, H., P. FLOCCHINI, On the Relationship Between Boolean and Fuzzy Cellular Automata, Journal of Electronic Notes in Theoretical Computer Science (ENTCS), vol. 252, 2009, pp. 5-21.
  4. CECCONI, F., R. LIVI, A. POLITI, Fuzzy Transition Region in a One-dimensional Coupled-stable-map Lattice, Physical Review E, vol. 57(3), 1998, pp. 2703-2712.
  5. CHAUDHURI, P. P., D. R. CHOWDHURY, S. NANDI, S. CHATTOPADHYAY, Additive Cellular Automata: Theory and Applications, vol. 1, Wiley-IEEE Computer Society, 1997.
  6. CHEN, R.-J., J.-L. LAI, Image Security System using Recursive Cellular Automata Substitution, Pattern Recognition, vol. 40, 2007, pp. 1621-1631.
  7. CHO, S.-J., et al., Computing Phase Shifts of Maximum-length 90/150 Cellular Automata Sequences, Cellular Automata, Springer, 2004, pp. 31-39.
  8. COMPAGNER, A., A. HOOGLAND, Maximum-length Sequences, Cellular Automata, and Random Numbers, Journal of Computational Physics, vol. 71, no. 2, 1987, pp. 391-428.
  9. CROUCH, A. L., D. P. MATTHEW, Self Re-seeding Linear Feedback Shift Register (LFSR) Data Processing System for Generating a Pseudo-random Test Bit Stream and Method of Operation, U.S. Patent No. 5, 383, 143, 17 Jan., 1995.
  10. FLOCCHINI, P., F. GEURTS, A. MINGARELLI, N. SANTORO, Convergence and Aperiodicity in Fuzzy Cellular Automata: Revisiting Rule 90, Physica D: Nonlinear Phenomena, vol. 142, no.1-2, 2000, pp. 20-28.
  11. GHOSH, S., T. BACCHAR, N. S. MAITI, I. MITRA, P. P. CHAUDHURI, Theory and Application of Equal Length Cycle Cellular Automata (ELCCA) for Enzyme Classification, 9th International Conference Cellular Automata for Research and Industry (ACRI 2010), Italy, Sep 21-24, 2010, pp. 45-57.
  12. HELLEBRAND, S., J. RAJSKI, S. TARNICK, S. VENKATARAMAN, B. COURTOIS, Built-in Test for Circuits with Scan Based on Reseeding of Multiple-polynomial Linear Feedback Shift Registers, IEEE Computers, vol. 44, no. 2, 1995, pp. 223-233.

  1. HORTENSIUS, P. D., R. D. MCLEOD, W. PRIES, D. M. MILLER, H. C. CARD, Cellular Automata-based Pseudorandom Number Generators for Built-in Self-test, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 8, no.8, 1989, pp. 842-859.
  2. JIN, J., An Image Encryption based on Elementary Cellular Automata, Optics and Leasers in Engineering, vol. 50, 2012, pp. 1836-1843.
  3. KARI, J., Theory of Cellular Automata: A Survey, Theoretical Computer Science, vol. 334, 2005, pp. 3-33.
  4. KHALID BUKHARI, S. U., R. BRAD, C. BĂLĂ–ZAMFIRESCU, Fast Edge Detection Algorithm for Embedded Systems, Studies in Informatics and Control, vol. 23, no. 2, 2014, pp. 163-170.
  5. KIM, H.-C., Linear Feedback Shift Register, Multiple Input Signature Register, and Built-in Self-test Circuit using Such Registers, U.S. Patent No. 5,938,784, 17 Aug, 1999.
  6. KOKOLAKIS, I., I. ANDREADIS, P. TSALIDES, Comparison between Cellular Automata and Linear Feedback Shift Registers based Pseudo-random Number Generators, Microprocessors and Microsystems, vol. 20, no. 10, 1997, pp. 643-658.
  7. KONISHI, T., K. KUNIHIKO, Clustered Motion in Symplectic Coupled Map Systems, Journal of Physics A: Mathematical and General, vol. 25, no. 23, 1992, pp. 6283-6296.
  8. KRASNIEWSKI, A., P. SLAWOMIR, Circular Self-test Path: A Low-cost BIST Technique for VLSI Circuits, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 8, no. 1, 1989, pp. 46-55.
  9. LI, C.-Y., J.-S. CHEN, T.-Y. CHANG, A Chaos-based Pseudo Random Number Generator using Timing-based Reseeding Method, IEEE Int. Symp. Circuits and Systems (ISCAS 2006), Greece, May 21-24, 2006, pp. 1-4.
  10. MARTINEZ, G. J., A Note on Elementary Cellular Automata Classification, Cellular Automata, vol. 8, no. 3-4, 2013, pp. 233-259.
  11. MITRA, A., A. KUNDU, M. CHATTOPADHYAY, S. CHOTTOPADHYAY, An Analysis of Equal Length Cellular Automata (ELCA) generating Linear Rules for Applications in Distributed Computing, Cellular Automata, vol. 10, no. 1-2, 2015, pp. 95-117.
  12. MITRA, A., A. KUNDU, Analysis of Sequences Generated by ELCA-type Cellular Automata targeting Noise Generation, 19th International Conference on System Theory, Control and Computing (ICSTCC 2015), Romania, Oct 14-16, 2015, pp. 883-888.
  13. MITRA, A., H.-N. TEODORESCU, Detailed Analysis of Equal Length Cellular Automata with Fixed Boundaries, Journal of Cellular Automata, Old City Publishing, 2016, accepted.
  14. MITRA, A., H.-N. TEODORESCU, Detailed Analysis of CAs with Fixed Boundaries (Submitted), pp. 1-74, http:// iit.academiaromana-is.ro/papers/iit_art16.ht ml (accessed on 24.02.2016).
  15. NANDI, S., B. K. KAR, P. P. CHAUDHURI, Theory and Application of Cellular Automata in Cryptography, IEEE Trans. Computers, vol. 43, no. 12, 1994, pp. 1346-1357.
  16. SUTNER, K., Classification of Cellular Automata, Encyclopedia of Complexity and Systems Science, Springer, 2009, pp. 755-768.
  17. TANG, K. W., W. K. TANG, K. F. MAN, A Chaos-based Pseudo-random Number Generator and Its Application in Voice Communications, International Journal Bifurcation and Chaos, vol. 17, no. 3, 2007, pp. 923-933.
  18. TEODORESCU, H.-N., Self-organizing Uncertainty-based Networks, In: Systematic Organisation of Information in Fuzzy Systems. Computer and Systems Science, NATO Science Series, vol. 184, 2003, pp. 131-159.
  19. TEODORESCU, H.-N., Pattern Formation and Stability Issues in Coupled Fuzzy Map Lattices, Studies in Informatics and Control, vol. 20, no. 4, 2011, pp. 345-354.
  20. TEODORESCU, H.-N., Characterization of Nonlinear Dynamic Systems for Engineering Purposes – A Partial Review, International Journal of General Systems, vol. 41, no. 8, 2012, pp. 805-825.
  21. TEODORESCU, H.-N., Iterated Maps with Exponential Slopes for Nonlinear Dynamics Generation, 2014 IEEE International Conference on Applied Electronics (AE 2014), Pilsen, Sep 9-10, 2014, pp. 293-296.
  22. TEODORESCU, H.-N., Generalized Binary Tent-maps for Built-in Self-test for Wearable Medical Devices, 5th IEEE E-Health and Bioengineering Conf. (EHB 2015), Romania, Nov 19-21, 2015, pp. 1-4.
  23. TEODORESCU, H.-N., Type-D Fuzzy CAs for Medical and Social Sciences, 5th IEEE E-Health and Bioengineering Conf. (EHB 2015), Iasi, Romania, Nov 19-21, 2015, pp. 1-4.
  24. TEODORESCU, H.-N., On the Regularities and Randomness of the Dynamics of Simple and Composed CAs with Applications, Romanian Journal of Information Science and Technology, Romanian Academy, vol. 18, no. 2, 2015, pp. 166-181.
  25. TOFFOLI, T., Cellular Automata as an Alternative to (rather than an approximation of) Differential Equations in Modeling Physics, Physica D, vol. 10, no. 1, 1984, pp. 117-127.
  26. WOLFRAM, S., Theory and Applications of Cellular Automata, World Scientific Press, 1986.
  27. WUENSCHE, A., M. LESSER, The Global Dynamics of Cellular Automata, Addison-Wesley, 1992.
  28. XIAOYANG, Y., S. YANG, Y., YANG, Y. SHUCHUN, C. HAO, G. YANXIA, An Encryption Method for QR Code Image Based on ECA, J. Security and Its Applications, Science & Engineering Research Support Society, vol. 7, no. 5, 2013, pp. 397-406.
  29. YE, R., W. ZHOU. A Chaos-based Image Encryption Scheme using 3D Skew Tent Map and Coupled Map Lattice, Int. J. Computer Network and Information Security, vol. 20, no. 4, 2012, pp. 38-44.
  30. YIN, R., J. YUAN, Q. YANG, X. SHAN, X., WANG, Gemstone: A New Stream Cipher using Coupled Map Lattice, 5th Conf. Information Security and Cryptology (Inscrypt 2009), China, Dec 12-15, 2009, pp. 198-214.
  31. https://home.ubalt.edu/ntsbarsh/business-stat/otherapplets/Randomness.htm (accessed on 26.02.2016).
  32. http://www.real-statistics.com/non-parametric-tests/one-sample-runs-test/ (accessed on 26.02.2016)
Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved