Gray Codes Generation Algorithm and Theoretical Evaluation of Random Walks in N-Cubes

In previous works, some of the authors have proposed a canonical form of Gray Codes (GCs) inN-cubes (hypercubes of dimension N). This form allowed them to draw an algorithm that theoretically provides exactly all the GCs for a given dimensionN. In another work, we first have shown that any of these...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics (Basel) 2018-06, Vol.6 (6), p.98
Main Authors: Contassot-Vivier, Sylvain, Couchot, Jean-François, Héam, Pierre-Cyrille
Format: Article
Language:English
Subjects:
Algorithms
Chaotic Dynamics
Codes
Computer Science
Cubes
Distributed, Parallel, and Cluster Computing
Generators
Gray Codes
Hamiltonian cycles
Hypercubes
Markov analysis
mixing time
Modeling and Simulation
N-cube
Nonlinear Sciences
PRNG
Pseudorandom
Random walk
Upper bounds
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In previous works, some of the authors have proposed a canonical form of Gray Codes (GCs) inN-cubes (hypercubes of dimension N). This form allowed them to draw an algorithm that theoretically provides exactly all the GCs for a given dimensionN. 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 dimensionN. This offers a large choice of GC to be used in the construction of Choatic 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 inNlog(N), which was anticipated in the previous article, but not proven.
ISSN:2227-7390
2227-7390
DOI:10.3390/math6060098