Uso del generador de números aleatorios de Arduino: las funciones Random y RandomSeed. Curso de Arduino - Temporización y generación aleatoria de secuencias de bits aleatorias de Arduino

Al programar Arduino, hay momentos en los que necesita obtener un número que no será conocido de antemano ni por el programador que escribe el boceto ni por el usuario que usará el Arduino con dicho programa. En este caso, un generador de números aleatorios (o más bien pseudo-aleatorios) viene al rescate.

Para activar este generador basta con utilizar las funciones random() o randomSeed(). Este artículo mostrará cómo trabajar con estas funciones, así como también cómo deshacerse de la pseudoaleatoriedad al generar números.

En general, un generador de números pseudoaleatorios imita la aleatoriedad o la aleatoriedad de la apariencia de los números, pero de hecho, si analiza una cantidad de estos números durante un período suficientemente largo, puede notar un cierto patrón.

Por lo tanto, la función aleatoria para generar números pseudoaleatorios puede tener hasta dos parámetros y escribirse como aleatorio (máximo) o aleatorio (mínimo, máximo). Aquí, el parámetro max, que es obligatorio, establece el límite superior del rango de generación de números pseudoaleatorios. Mediante el uso parámetro adicional min se puede utilizar para establecer el límite inferior del rango. Como resultado, la función devolverá un número pseudoaleatorio entre min y max-1.

Es importante comprender que al usar la función random(), se generará exactamente la misma lista de números pseudoaleatorios cada vez. Por ejemplo, si hace una máquina tragamonedas y la primera vez que presiona el mango, aparecerá una combinación ganadora, entonces puede estar seguro de que si reinicia el Arduino y presiona el mango nuevamente, esta máquina tragamonedas mostrará la misma combinación ganadora. combinación. De hecho, en Arduino no es fácil implementar una máquina de juego con una generación de números completamente aleatoria, como, por ejemplo, implementada en las máquinas de juego www.igrovye-apparati-vulcan.com/ , pero puede resolver parcialmente el problema usando randomSeed () función.

Esta función toma un valor (por ejemplo, un número entero) y usa un número para modificar la lista aleatoria generada por la función random(). Puede poner randomSeed() en la función de configuración y usar la función random() en un número infinito. bucle. Pero en este caso, habrá un problema, y ​​es que aunque la secuencia de números aleatorios será diferente cuando se use la función randomSeed(), seguirá siendo la misma cada vez que se ejecute el boceto.

La única solución en este caso puede ser una opción usando periféricos analógicos (ADC) y la función analogRead () correspondiente. Si no conecta la entrada analógica a nada, es decir, la deja "colgando" en el aire, entonces, gracias al ruido en esta línea, puede obtener números realmente aleatorios. Luego, en la configuración de configuración, puede escribir así randomSeed (analogRead (A0)). Siempre que el puerto analógico A0 no esté conectado en ningún lado.

Se ha escrito mucho sobre los generadores de números aleatorios, pero casi siempre, cuando se trata de la implementación, se da a entender (o se declara explícitamente) que estamos hablando sobre x86/x64 y otras arquitecturas "para adultos". Al mismo tiempo, los foros dedicados al desarrollo de dispositivos en microcontroladores están llenos de preguntas "¿cómo genero un número aleatorio en %controllername%?". Además, el rango de respuestas se extiende desde “ver Google/Wikipedia” hasta “usar la función estándar”. Esta "función estándar" está lejos de estar siempre presente y se adapta al desarrollador en todos los aspectos, más a menudo es al revés: o los números están lejos de ser aleatorios, o la velocidad de trabajo es demasiado baja, o el código resultante no encajar en la memoria libre en absoluto.
Intentemos descubrir cuáles son los algoritmos para generar números aleatorios, cómo elegir el correcto y, lo que es más importante, cuáles son las características de la implementación de estos algoritmos en los controladores.

Puntuación de aleatoriedad

Las aplicaciones para RNG pueden ser muy diferentes, desde juguetes hasta criptografía seria. En consecuencia, los requisitos para el generador también varían mucho. Para evaluar la calidad (nivel de "aleatoriedad") del generador, existen pruebas especiales. Aquí están los más básicos:

• prueba de frecuencia Consiste en contar el número de ceros y unos en una secuencia de bits. Unos y ceros deben ser aproximadamente iguales.
• Prueba para una secuencia de bits idénticos. Se buscan filas de bits idénticos, como 000...0 o 111...1. La distribución de frecuencias encontrada por la serie, dependiendo de su longitud, debería corresponder a tal distribución para una señal verdaderamente aleatoria.
• Prueba espectral. La transformada discreta de Fourier se aplica a la secuencia original. El espectro resultante no debe tener picos significativos que indiquen la presencia de propiedades periódicas de la secuencia.
• Prueba de autocorrelación. Se calcula el valor de correlación entre copias de la secuencia desplazadas entre sí. La prueba le permite encontrar secciones repetidas en una secuencia.

Existen kits especiales que incluyen decenas de pruebas similares:
NIST: utilizado en la competencia AES para evaluar algoritmos de cifrado.
DIEHARD es uno de los conjuntos más rigurosos que existen.

algoritmos PRNG

Cualquier secuencia generada de acuerdo con un algoritmo codificado no puede considerarse verdaderamente aleatoria, por lo tanto, cuando se habla de generadores algorítmicos, utilizan el término pseudoaleatorio subsecuencia Cualquier bucle de generador de números pseudoaleatorios (PRNG) tarde o temprano, otra cosa es que este “tarde” puede llegar en unos milisegundos, o tal vez en unos años. La duración del ciclo depende del tamaño del estado interno del generador N (de hecho, esta es la cantidad de memoria que necesita el generador) y varía de 2 (N / 2) a 2 N bits.
Se ha inventado una gran cantidad de algoritmos PRNG, pero no todos son convenientes para la implementación en microcontroladores. Estamos muy limitados en velocidad y memoria disponible, muchos controladores no admiten comandos aritméticos reales e incluso de multiplicación. Con estas limitaciones en mente, veamos algunos algoritmos bien conocidos.

Método lineal congruente

El siguiente miembro de la secuencia se calcula mediante la fórmula
Xi+1 = (aXi + c) módulo m
Número metro especifica el período máximo de la secuencia, enteros a Y C- coeficientes "mágicos". Número metro es razonable elegir igual a la potencia de dos, en cuyo caso la operación de reducción de módulo se reduce a descartar los bits altos. Para obtener el período máximo, se deben cumplir las siguientes condiciones:
- C y m debe ser coprimo,
- a-1 debe ser un múltiplo pag para todos los divisores primos pag números metro,
- Si metro es un múltiplo de 4 (y en nuestro caso será un múltiplo), entonces a-1 debe ser múltiplo de 4.
Hay una sutileza más: sólo se deben tomar como resultado los bits altos de la variable de estado X, ya que los parámetros estadísticos de aleatoriedad son mucho peores para los bits bajos. El algoritmo lineal congruente generalmente se implementa como rand() estándar en muchas bibliotecas.

Ventajas:

• el período máximo posible para un tamaño de variable de estado dado;
• suficientemente rapido;
• a menudo ya implementado en la biblioteca del compilador.

Contras:

• se requiere la operación de multiplicación;
• no todos los bits son igualmente aleatorios.

Resumen: Algoritmo rápido y simple para aplicaciones no muy responsables.

Método de Fibonacci con retrasos

Este algoritmo utiliza la relación
X i \u003d X i-a - X i-b,
donde esta la variable de estado X es un entero sin signo. Valores de retardo a Y b no se toma cualquiera, sino estrictamente definidos, se recomiendan los pares (17.5), (55.24) o (97.33) para lograr la máxima calidad. Cuanto mayor sea el retraso, mayor será el período y mejores serán las propiedades espectrales de la secuencia. Por otro lado, para que el generador funcione, se requiere almacenar max(a,b) de los números anteriores, lo que no siempre es aceptable. Además, para ejecutar el generador, necesita números máximos (a, b), que generalmente se obtienen utilizando un PRNG más simple.

Ventajas:

• no requiere operaciones de multiplicación;
• todos los bits de un número aleatorio son estadísticamente equivalentes.

Contras:

• requiere una gran cantidad de memoria;
• requiere una gran variedad de números para ejecutarse.

Resumen: Algoritmo de muy alta calidad, pero intensivo en recursos.

Registro de desplazamiento de retroalimentación lineal

La variable de estado se almacena en un registro de longitud N. La generación del siguiente estado implica dos pasos:

1. Se calcula el valor del bit C = X i1 xor X i2 xor… X ik, donde i1, i2…ik- registrar números de bits, llamados enfermedad de buzo.
2. El registro se desplaza 1 bit a la derecha, el bit más a la izquierda toma el valor CON.

La salida del generador es el bit más a la derecha (o más a la izquierda, o lo que sea) del registro, lo que significa que la secuencia pseudoaleatoria se genera un bit por iteración. Con números de tomas correctamente seleccionados, el período del generador será 2 N - 1. "Menos uno", ya que hay un estado cero prohibido del registro. Números de sucursal para norte del 3 al 168 se pueden consultar en este documento.
Además de la configuración descrita anteriormente, que, por cierto, se denomina configuración de Fibonacci (¡no debe confundirse con el método PRNG del mismo nombre!), existe el llamado. Configuración de Galois.


En lugar de usar la suma de los bits en la secuencia de toque para generar un nuevo bit más a la izquierda, haga XOR cada bit de la secuencia de toque con el bit más a la derecha, luego gire todo el registro a la derecha. Este esquema es más difícil de entender, pero más fácil de implementar, ya que todas las operaciones XOR se pueden realizar al mismo tiempo. Los esquemas de Fibonacci y Galois son equivalentes en cuanto a la duración del período y la calidad de los números pseudoaleatorios.

Ventajas:

• implementación muy simple, ni siquiera se requiere aritmética, solo operaciones de bits y cambios;
• algoritmo muy rápido (especialmente el esquema de Galois);
• buenas propiedades estadísticas.

Contras:

• necesita verificar el valor inicial para la desigualdad cero.

Resumen: Algoritmo muy rápido y de bastante alta calidad.

Algoritmos criptorresistentes

Para su aplicación en criptografía, PRNG tiene un requisito esencial más: irreversibilidad. Todos los algoritmos enumerados anteriormente no tienen esta propiedad: conociendo varios valores de salida del PRNG, es posible, resolviendo un sistema simple de ecuaciones, encontrar los parámetros del algoritmo (las mismas constantes "mágicas" a B C etc). Y conociendo los parámetros, puede reproducir toda la secuencia pseudoaleatoria.
Cualquier cifrado de bloque suficientemente fuerte puede usarse como un algoritmo PRNG criptográficamente fuerte. Al elegir una clave secreta, se pueden obtener bloques de números pseudoaleatorios aplicando el algoritmo a números naturales consecutivos. Para un cifrado de bloque de N bits, el período será como máximo 2 N . La seguridad de tal esquema depende completamente del secreto de la clave.
Todos los algoritmos criptográficos modernos se prueban para su uso como PRNG, es decir, utilizando un algoritmo certificado, no es necesario prestar especial atención a las propiedades estadísticas y espectrales del flujo de salida. Solo debe preocuparse por la "voracidad" computacional de los algoritmos criptográficos. Si necesita realizar una gran cantidad de operaciones de cifrado, tiene sentido elegir un controlador con bloques criptográficos de hardware. A menudo, en tales controladores también hay un PRNG de hardware criptorresistente muy bueno.

Fuentes de entropía

Como ya se mencionó, usando solo algoritmos deterministas, es imposible generar un número verdaderamente aleatorio. Por lo tanto, generalmente se usa un montón de PRNG + externo fuente de entropía. La fuente de entropía se utiliza para establecer el valor inicial del PRNG, y la tarea de este último es garantizar la pureza espectral y estadística de la secuencia. ¿Qué se puede utilizar como fuente de entropía? Sí, prácticamente cualquier cosa.

Actividad del usuario

Si el dispositivo interactúa con el usuario de alguna manera, es una muy buena idea utilizar al propio usuario como fuente de entropía. Por ejemplo, el tiempo de presionar un botón, medido al microsegundo más cercano (o más bien, sus dígitos menos significativos), es completamente impredecible. Sin embargo, muchas veces el dispositivo debe funcionar de forma autónoma, lo que significa que estamos perdiendo este maravilloso canal de información.

Conversor analógico a digital

Muchos controladores tienen ADC incorporados. Y en muchos controladores son de una calidad muy mediocre, hechos simplemente "para ser". Los bits bajos del resultado del ADC casi siempre contienen un ruido significativo, incluso si se mide el voltaje de CC. Esto se puede usar: conecte la entrada del ADC al voltaje de suministro a través de un divisor, tome algunas docenas de medidas, tome los bits menos significativos: aquí hay un gran número aleatorio para usted. Si el ADC contiene un preamplificador incorporado, enciéndalo, también hace ruido.

Generadores asíncronos

Puede utilizar la diferencia de período de dos relojes no sincronizados. La mayoría de los controladores contienen, por ejemplo, un temporizador de vigilancia. Para mejorar la confiabilidad, se sincroniza desde un oscilador separado que no está conectado de ninguna manera a la señal del reloj principal. Es suficiente contar el número de ciclos de la señal del reloj principal en un período del temporizador de vigilancia. Si elige los períodos para que el contador se desborde muchas veces durante la medición, puede obtener un número bastante aleatorio. La desventaja de este método es que lleva mucho tiempo, hasta varios segundos.

Reloj en tiempo real

Si el esquema tiene reloj en tiempo real, puede usar sus lecturas actuales para inicializar el PRNG. Por ejemplo, al convertir la fecha/hora actual al formato de hora de Unix, obtenemos inmediatamente 32 bits, que nunca no volverá a ocurrir, a menos que tome lecturas más de una vez por segundo. El uso del tiempo real brinda valores únicos, pero no genera imprevisibilidad, por lo que es mejor combinar Por aquí con otros.

circuito RC

Si el controlador no tiene ninguna periféricos, a excepción de los puertos de E / S, puede hacer lo siguiente: una de las patas está conectada a tierra a través de un capacitor y, a través de una resistencia, a la tensión de alimentación. Si las entradas del controlador tienen resistencias pull-up internas, no se necesita ninguna resistencia externa.

Enviamos una señal "0" a este puerto: el condensador está descargado. Cambiamos el puerto al modo de entrada: el condensador comienza a cargarse. Cuando el voltaje alcanza el umbral, la entrada cambiará del estado "0" a "1". El tiempo de carga depende en gran medida de muchos factores: tensión de alimentación, desviación de los parámetros del circuito RC, inestabilidad del umbral, temperatura, fugas, ruido. Al medirlo con suficiente precisión y tomar los bits menos significativos, puede obtener una buena aleatoriedad.

Generador de ruido de hardware

Para muchas aplicaciones serias (principalmente criptografía), se requiere una fuente de entropía más confiable que las enumeradas anteriormente. En tales casos, la señal se digitaliza a partir de un generador de ruido basado en efectos térmicos, de disparo o incluso cuánticos. El elemento ruidoso suele ser un diodo especial o diodo zener, cuya señal se amplifica y alimenta a un comparador que forma un flujo de bits binario.

Para que el umbral de respuesta del comparador no afecte las propiedades estadísticas de la señal recibida, se utilizan dos generadores de ruido que funcionan en un comparador:

Conclusión

Finalmente, les contaré una historia de mi vida. Comenzó con otra pregunta en el foro "¿cómo genero un número aleatorio en el controlador?". El autor de la pregunta explicó qué está haciendo el dispositivo que emula el lanzamiento de un dado como proyecto de curso. Después de varios intentos fallidos de descifrar los algoritmos, el topikstarter compartió su solución: simplemente lanzó un dado real 1000 veces y anotó toda la memoria libre del controlador con los números resultantes. El generador pasó todas las pruebas de "aleatoriedad" con gran éxito, dado que utilizó menos de un tercio de su "reserva" durante la demostración.
Por lo tanto, dicha solución también tiene derecho a la vida, especialmente si se imponen requisitos muy estrictos sobre la aleatoriedad de los números, pero no se requieren con mucha frecuencia. Con los precios de las memorias cayendo en picado, puede ser conveniente almacenar un dispositivo con una unidad flash de "margen del caos" que durará toda la vida útil del dispositivo.
¡Gracias por su atención!

UPD1: Como se señaló correctamente en los comentarios, si se supone un ataque al RNG y el atacante tendrá acceso de hardware al dispositivo, las fuentes de entropía externas deben usarse con mucho cuidado, ya que no es muy difícil reemplazar la señal de fuente externa. Deben utilizarse fuentes internas, posiblemente además de fuentes externas.
También es buena idea acumular la entropía de todo. tiempo libre, y utilícelo cuando necesite generar otro número aleatorio. Por lo general, en tales casos, los llamados. Reserva de entropía- una matriz sobre la que se realiza periódicamente una de las funciones PRNG y donde los datos de las fuentes de entropía se mezclan constantemente.

UPD2: En muchos casos, es útil guardar el contenido del grupo de Entropía (lo siento, no sé la traducción rusa normal) en EEPROM para no acumularlo nuevamente después de apagar y encender el dispositivo. Esto se aplica, en primer lugar, a la obtención de la entropía por el método de los generadores asíncronos: en condiciones suficientemente estables, después de cada encendido, se puede generar la misma secuencia.
Si se espera un ataque, tome precauciones contra la manipulación del contenido de la EEPROM. Si el controlador lo permite, bloquee la lectura/borrado/escritura usando bits de bloqueo, cuando esté encendido, controle la integridad de la EEPROM, al menos usando las sumas de verificación más simples.

Etiquetas:

• rfc
• gpsch
• microcontroladores
• algoritmos

Agregar etiquetas

semilla aleatoria (semilla)

Establece un valor, o semilla, como punto de partida de la función random().

semilla aleatoria (valor); // establece 'valor' como valor aleatorio inicial

Dado que Arduino no puede generar números verdaderamente aleatorios, randomSeed le permite poner una variable, constante u otra función en la función aleatoria, lo que ayuda a generar más números aleatorios.

"números al azar. Hay muchas semillas o funciones diferentes que se pueden usar en esta función, incluyendo millis(), o incluso analogRead() para leer el ruido eléctrico a través de un pin analógico.

aleatorio (máximo)

aleatorio (mín, máx)

La función aleatoria le permite devolver un número pseudoaleatorio dentro del rango dado por los valores mínimo y máximo.

valor = aleatorio (100, 200); // establece 'valor' en aleatorio

// un número entre 100 y 200

Nota: Use esto después de usar la función randomSeed(). El siguiente ejemplo genera un número aleatorio entre 0 y 255 y genera PWM

Señal a salida PWM igual a valor aleatorio:

int randNumber; // variable para almacenar un valor aleatorio

led int = 10; // LED con resistencia en el pin 10

void setup() () // la configuración no es necesaria

semilla aleatoria (milis ()); // establece millis() como semilla

NúmeroAleatorio = aleatorio(255); // numero aleatorio de 0 - 255 analogWrite(led, randNumber); // señal de salida PWM

retraso (500); // pausa medio segundo

Fuente: Gololobov V. - ¿Dónde comienzan los robots? Sobre el proyecto Arduino para escolares (y no solo) - 2011

Artículos Relacionados

Serial.begin (velocidad) Abre el puerto serie y establece la velocidad para la transferencia de datos en serie. La tasa de baudios típica para la comunicación informática es 9600, aunque se admiten otras tasas de baudios. configuración vacía()( Serial.begin…….

Todas las variables deben declararse antes de que puedan utilizarse. Declarar una variable significa definir el tipo de su valor: int, long, float, etc., establecer un nombre de variable único y, además,…….

Bien, hemos instalado este programa. Hemos depurado el "mecanismo" de trabajar con el módulo. Y mira algunos ejemplos. Pero me gustaría crear algo útil yo mismo. Intentemos. Primero cerremos el proyecto anterior. Para esto…….

¡Atención! Cuando trabaje con el módulo Arduino en otros entornos de desarrollo, debe tener cuidado con la configuración del microcontrolador (fusibles). Hasta que sepa exactamente a qué podría conducir el cambio….

Tiempo y al azar. Reacción

Esta vez aprenderemos qué son los valores "Random", y también aprenderemos a trabajar con el tiempo.

Necesitaremos:

• Botón de reloj
• chirriador
• Cables de conexión "PAPA-PAPA"

Reacción

Nuestra tarea de hoy es armar un circuito que nos permita averiguar la velocidad de nuestra reacción.

Cuando presiona el botón izquierdo, se escucha una señal después de un tiempo "aleatorio". Y cuando presiona el botón derecho, se nota cuánto tiempo ha pasado desde que se escuchó el sonido hasta que se presionó el botón derecho.

Quien es hábil, lo prueba él mismo y observamos el esquema.

#define BUZ 8 #define START 9 #define STOP 7 int time; // Variable para sincronización void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Al presionar el botón START.. ( int start_time = millis();// Recuerda el momento de presionar time = start_time; // Escríbelo en una variable global. int Rand = random(0, 4000) ; // Generar un tiempo de retardo "aleatorio" = time + Rand; //Agregar el tiempo de retardo delay(Rand); //Tono de espera(BUZ, 3000, 500); //Beep! ) if(digitalRead(STOP) = = 0 && digitalRead( START) == 1)// Al presionar el botón STOP... ( int stop_time = millis(); //Recordar el tiempo de parada. time = stop_time - time; // Calcular la diferencia horaria. Serial .println("Tiempo: "); // Imprime el tiempo en Serial. Serial. println(time); delay(1000); ) ) // Antes del segundo intento, presiona el botón START nuevamente.

Explicaciones

En t tiempo; Las variables (no todas), cuando se designan, no se les tiene que asignar ningún valor. Usamos esta variable para vincular dos sentencias if.

En C++, las variables declaradas dentro de un bucle no estarán disponibles en otros bucles, ya que solo son válidas dentro de ese bucle. Esto se hace para evitar errores de programación. Cuando el código del programa crezca, entenderás de lo que estoy hablando.

Para que una variable esté disponible para varias declaraciones, debe hacerla global. Aquellos. declarar una variable fuera de las funciones.

milis(); Devuelve el número de milisegundos que han pasado desde que se inició el programa.

Lo necesitamos para medir la cantidad de tiempo transcurrido desde que se indica hasta que se presiona el botón.

aleatorio(minuto,máx.); Es un generador de números "aleatorios". Toma dos valores. Genera un número entre min y max.

Números "aleatorios" porque es una determinada secuencia de valores. Muy largo, pero igual. Para obtener diferentes secuencias, debe usar AleatorioSemilla();

Ella, la función, inicializa el generador. Y si establece el parámetro en aleatorio, obtendremos las secuencias que necesitamos. La misma secuencia será si el parámetro es fijo.

Conclusión

Ahora puedes entrenar tu reacción con la ayuda de tu propio dispositivo. Y puedes seguir.

Lista de elementos de radio

Designación	Tipo	Denominación	Cantidad	Nota	Comercio	mi bloc de notas
	placa arduino	arduino uno	1			Al bloc de notas
	tabla de pan	Protoboard-mitad	1			Al bloc de notas
	Zumbador piezoeléctrico	Pasivo	1			Al bloc de notas
	Botón de reloj	sin retenedor	2			Al bloc de notas
	Cables de conexión	"Papá Papá"	1