Generation of Finite Inductive, Pseudo Random, Binary Sequences
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
This paper introduces a new type of determining factor for Pseudo Random Strings (PRS). This classificationdepends upon a mathematical property called Finite Induction (FI). FI is similar to a Markov Model in that itpresents a model of the sequence under consideration and determines the generating rules for this sequence. If these rules obey certain criteria, then we call the sequence generating these rules FI a PRS. We also considerthe relationship of these kinds of PRS’s to Good/deBruijn graphs and Linear Feedback Shift Registers (LFSR). We show that binary sequences from these special graphs have the FI property. We also show how such FIPRS’s can be generated without consideration of the Hamiltonian cycles of the Good/deBruijn graphs. The FIPRS’s also have maximum Shannon entropy, while sequences from LFSR’s do not, nor are such sequences FIrandom.
Abstract
This paper introduces a new type of determining factor for Pseudo Random Strings (PRS). This classificationdepends upon a mathematical property called Finite Induction (FI). FI is similar to a Markov Model in that itpresents a model of the sequence under consideration and determines the generating rules for this sequence. If these rules obey certain criteria, then we call the sequence generating these rules FI a PRS. We also considerthe relationship of these kinds of PRS’s to Good/deBruijn graphs and Linear Feedback Shift Registers (LFSR). We show that binary sequences from these special graphs have the FI property. We also show how such FIPRS’s can be generated without consideration of the Hamiltonian cycles of the Good/deBruijn graphs. The FIPRS’s also have maximum Shannon entropy, while sequences from LFSR’s do not, nor are such sequences FIrandom.
참고문헌 (13)
- J. von Neumann, "Collected Works" (1962), Pergamon Press
- C. E. Shannon, "A mathematical theory of communication", The Bell System Technical Journal, 27, pp.623~656 (1948)
- C. Stroud, "Linear Feedback Shift Registers (LFSRs)", Department of Electrical and Computer Engineering, pp.2004
- I. J. Good, "Normal recurring decimals", Journal of the London Mathematical Society, s1-21(3), pp.167~169 (1946)
- N. G. de Bruijn, "A combinatorial problem", Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen, pp.758~764 (1946)
- J. H. Case, "Long-term memory modules", Bulletin of Mathematical Biology, 46(2), pp.295~326 (1984)
- R. G. Busacker, "Finite Graphs and Networks: An Introduction with Applications" (1965), McGraw-Hill
- J. H. van Lint, "Combinatorial Theory Seminar, Eidhoven University of Technology" (1974), Springer
- A. Alhakim, "A recursive construction of nonbinary de Bruijn sequences", Designs, Codes and Cryptography, 60(2), pp.155~169 (2011)
- F. M. Malyshev, "Generalized de Bruijn graphs", Mathematical Notes, 62(4), pp.449~456 (1997)
- W. T. Tutte, "Graph Theory" (2001), Cambridge University Press
- S. W. Golomb, "Shift Register Sequences" (1982), Aegean Park Press
- M. Li, "An Introduction to Kolmogorov Complexity and Its Applications" (2008), Springer