Algoritmo de generación de códigos Gray y evaluación teórica de caminatas aleatorias en n-cubos
Autores: Contassot-Vivier, Sylvain; Couchot, Jean-François; Héam, Pierre-Cyrille
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
Algoritmo de generación de códigos Gray y evaluación teórica de caminatas aleatorias en n-cubos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Forma canónica
Códigos Gray
Hipercubos
Algoritmo
PRNG
Tiempo de mezcla
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 35
Citaciones: Sin citaciones
En trabajos anteriores, algunos autores han propuesto una forma canónica de Códigos Gray (GCs) en -cubos (hipercubos de dimensión N). Esta forma les permitió desarrollar un algoritmo que teóricamente proporciona exactamente todos los GCs para una dimensión dada. En otro trabajo, primero hemos demostrado que cualquiera de estos GC puede ser utilizado para construir la función de transición de un Generador de Números Pseudoaleatorios (PRNG). Además, hemos encontrado un límite superior cuadrático teórico del tiempo de mezcla, es decir, el número de iteraciones que se requieren para proporcionar un PRNG cuya salida sea uniforme. Este artículo extiende estos dos trabajos previos tanto práctica como teóricamente. Por un lado, se propone otro algoritmo para generar GCs que proporciona una generación eficiente de subconjuntos de todo el conjunto de GCs relacionados con una dimensión dada. Esto ofrece una amplia selección de GC para ser utilizados en la construcción de Generadores de Números Pseudoaleatorios basados en Iteraciones Caóticas (CI-PRNGs), lo que lleva a una gran variedad de posibles PRNGs. Por otro lado, se ha demostrado teóricamente que el tiempo de mezcla está en , lo cual fue anticipado en el artículo anterior, pero no demostrado.
Descripción
En trabajos anteriores, algunos autores han propuesto una forma canónica de Códigos Gray (GCs) en -cubos (hipercubos de dimensión N). Esta forma les permitió desarrollar un algoritmo que teóricamente proporciona exactamente todos los GCs para una dimensión dada. En otro trabajo, primero hemos demostrado que cualquiera de estos GC puede ser utilizado para construir la función de transición de un Generador de Números Pseudoaleatorios (PRNG). Además, hemos encontrado un límite superior cuadrático teórico del tiempo de mezcla, es decir, el número de iteraciones que se requieren para proporcionar un PRNG cuya salida sea uniforme. Este artículo extiende estos dos trabajos previos tanto práctica como teóricamente. Por un lado, se propone otro algoritmo para generar GCs que proporciona una generación eficiente de subconjuntos de todo el conjunto de GCs relacionados con una dimensión dada. Esto ofrece una amplia selección de GC para ser utilizados en la construcción de Generadores de Números Pseudoaleatorios basados en Iteraciones Caóticas (CI-PRNGs), lo que lleva a una gran variedad de posibles PRNGs. Por otro lado, se ha demostrado teóricamente que el tiempo de mezcla está en , lo cual fue anticipado en el artículo anterior, pero no demostrado.