×

Gray codes generation algorithm and theoretical evaluation of random walks in \(N\)-cubes. (English) Zbl 1454.94007

Summary: In previous works, some of the authors have proposed a canonical form of Gray Codes (GCs) in \(N\)-cubes (hypercubes of dimension \(N\)). This form allowed them to draw an algorithm that theoretically provides exactly all the GCs for a given dimension \(N\). In another work, we first have shown that any of these GC can be used to build the transition function of a Pseudorandom Number Generator (PRNG). Also, we have found a theoretical quadratic upper bound of the mixing time, i.e., the number of iterations that are required to provide a PRNG whose output is uniform. This article, extends these two previous works both practically and theoretically. On the one hand, another algorithm for generating GCs is proposed that provides an efficient generation of subsets of the entire set of GCs related to a given dimension \(N\). This offers a large choice of GC to be used in the construction of Chaotic Iterations based PRNGs (CI-PRNGs), leading to a large class of possible PRNGs. On the other hand, the mixing time has been theoretically shown to be in \(N\log N\), which was anticipated in the previous article, but not proven.

MSC:

94A05 Communication theory
05C45 Eulerian and Hamiltonian graphs
68W40 Analysis of algorithms
82C41 Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics

Software:

CIPRNG; TestU01; Diehard
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lovász, L.; Random walks on graphs; Combinatorics, Paul Erdos Is Eighty: Budapest, Hungary 1993; Volume Volume 2 ,1-46.
[2] Diaconis, P.; Graham, R.L.; Morrison, J.A.; Asymptotic analysis of a random walk on a hypercube with many dimensions; Random Struct. Algorithms: 1990; Volume 1 ,51-72. · Zbl 0723.60085
[3] Lawler, G.F.; Limic, V.; ; Random Walk: A Modern Introduction: Cambridge, UK 2010; Volume Volume 123 . · Zbl 1210.60002
[4] Scoppola, B.; Exact solution for a class of random walk on the hypercube; J. Stat. Phys.: 2011; Volume 143 ,413-419. · Zbl 1219.82097
[5] Levin, D.A.; Peres, Y.; ; Markov Chains and Mixing Times: Providence, RI, USA 2017; Volume Volume 107 . · Zbl 1390.60001
[6] Contassot-Vivier, S.; Couchot, J.F.; Guyeux, C.; Héam, P.C.; Random Walk in a N-Cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations; Int. J. Bifurcation Chaos: 2017; Volume 27 ,18. · Zbl 1358.11090
[7] Suparta, I.; Zanten, A.V.; Totally balanced and exponentially balanced Gray codes; Discrete Anal. Oper. Res.: 2004; Volume 11 ,81-98. · Zbl 1078.94040
[8] Contassot-Vivier, S.; Couchot, J.F.; Canonical Form of Gray Codes in N-cubes; Cellular Automata and Discrete Complex Systems, Proceedings of the 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Milan, Italy, 7-9 June 2017: Milan, Italy 2017; Volume Volume LNCS-10248 ,68-80. · Zbl 1454.94006
[9] Wild, M.; Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion; J. Discrete Algorithms: 2008; Volume 6 ,93-102. · Zbl 1229.05187
[10] Couchot, J.; Héam, P.; Guyeux, C.; Wang, Q.; Bahi, J.M.; Pseudorandom Number Generators with Balanced Gray Codes; Proceedings of the 11th International Conference on Security and Cryptography SECRYPT: ; ,469-475.
[11] Bakiri, M.; Couchot, J.; Guyeux, C.; CIPRNG: A VLSI Family of Chaotic Iterations Post-Processings for F2-Linear Pseudorandom Number Generation Based on Zynq MPSoC; IEEE Trans. Circuits Syst.: 2018; Volume 65 ,1628-1641.
[12] Bahi, J.M.; Couchot, J.F.; Guyeux, C.; Richard, A.; On the Link between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems; Fundamentals of Computation Theory: Berlin, Heidelberg, Germany 2011; ,126-137. · Zbl 1342.37044
[13] Guyeux, C.; Couturier, R.; Héam, P.; Bahi, J.M.; Efficient and cryptographically secure generation of chaotic pseudorandom numbers on GPU; J. Supercomput.: 2015; Volume 71 ,3877-3903.
[14] Bakiri, M.; Couchot, J.; Guyeux, C.; FPGA Implementation of F2-Linear Pseudorandom Number Generators based on Zynq MPSoC: A Chaotic Iterations Post Processing Case Study; Proceedings of the 13th International Joint Conference on e-Business and Telecommunications (ICETE 2016): SECRYPT: Setúbal, Portugal 2016; Volume Volume 4 ,302-309.
[15] Marsaglia, G.; DIEHARD: A Battery of Tests of Randomness; ; .
[16] L’Ecuyer, P.; Simard, R.; TestU01: A C Library for Empirical Testing of Random Number Generators; ACM Trans. Math. Softw.: 2007; Volume 33 ,22. · Zbl 1365.65008
[17] Bakiri, M.; Hardware Implementation of Pseudo Random Number Generator Based on Chaotic Iterations; Ph.D Thesis: Belfort, France 2018; .
[18] L’Ecuyer, P.; ; Handbook of Computational Statistics: Berlin, Germany 2012; ,35-71. · Zbl 1243.62001
[19] L’Ecuyer, P.; History of uniform random number generation; Proceedings of the WSC 2017-Winter Simulation Conference: ; ,202-230.
[20] Robinson, J.P.; Cohn, M.; Counting Sequences; IEEE Trans. Comput.: 1981; Volume 30 ,17-23. · Zbl 0455.94053
[21] Bhat, G.S.; Savage, C.D.; Balanced Gray Codes; Electr. J. Comb.: 1996; Volume 3 ,25. · Zbl 0917.94019
[22] Suparta, I.; Zanten, A.V.; A construction of Gray codes inducing complete graphs; Discrete Math.: 2008; Volume 308 ,4124-4132. · Zbl 1144.05037
[23] Bykov, I.S.; On locally balanced gray codes; J. Appl. Ind. Math.: 2016; Volume 10 ,78-85. · Zbl 1349.94152
[24] Conder, M.D.E.; Explicit definition of the binary reflected Gray codes; Discrete Math.: 1999; Volume 195 ,245-249. · Zbl 0933.94033
[25] Bunder, M.W.; Tognetti, K.P.; Wheeler, G.E.; On binary reflected Gray codes and functions; Discrete Math.: 2008; Volume 308 ,1690-1700. · Zbl 1211.94051
[26] Berestycki, N.; Mixing Times of Markov Chains: Techniques and Examples; Cambridge, UK 2016; .
[27] Norris, J.R.; ; Markov Chains: Cambridge, UK 1998; . · Zbl 0938.60058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.